Ad Hoc网络中的区域划分和资源分配问题第五组.doc

Ad Hoc网络中的区域划分和资源分配问题1 问题重述随着人们对摆脱有线网络束缚、随时随地进行自由通信的渴望，近几年来无线网络通信得到了迅速的发展。为了能够在没有固定基站的地方进行通信， Ad Hoc网络技术应运而生。Ad Hoc网络不需要有线基础设备的支持，通过移动主机自由的组网实现通信。就其特点，在给定一些限制条件下，本文提出了关于如何合理划分 Ad Hoc网络中的区域和分配资源问题。具体内容如下：对一个指定10001000(面积单位)的正方形区域内构建一个Ad Hoc网络，需解决以下问题：(1) 以圆的形式对正方形区域进行覆盖，在满足所给定的限制条件下，通过建立最小半径和模型，求得圆的最少个数。若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，在此条件下合理分配信道。改变公共面积部分的限制条件，重复上述问题。再根据条件，提出合理假设，讨论网络的抗毁性问题。(2) 设正方形区域中有一满足给定条件的椭圆形湖泊。由限制条件：节点仅能设置在地面上，以及假设条件：一跳覆盖区圆的半径可以在75100间随意选择，两个面积不等的圆相交，它们之间的公共面积应不小于大圆面积的5%，建立最小半径和模型，研究合理的区域分划和信道分配方案。(3) 在假设一个较短的时间间隔内，网络的连通性可能并未变化的情况下，采用基于节点的划分方式，在某一时刻将正方形区域内的节点（用户）分成若干个簇。给出簇与一跳覆盖区的定义，并根据给定条件结合数据，建立半径最小和模型，研究一跳覆盖区划分和信道分配方案，找出区域连通的充分、必要条件，并讨论网络抗毁性。(4) 在问题3的基础上作进一步假设，根据所给的条件，考虑在动态情况下，通过建立模型，考虑网络连通性问题。(5) 基于前面（3）中所给办法，从节能角度出发，根据所给条件，建立能量消耗与其所处位置关联的求极值模型，找到比较节能的区域分划方式，使出现第一个退出网络的节点的时间尽量长。并通过对该网络的运行状况进行分析，对组网方式提出改进意见。(6) Ad Hoc网络中针对如何保证通信的质量问题，根据所给条件，建立相关模型，对上一题中的通信质量进行定量评价。2 模型假设(1) 节点可看作质点，其所占的面积可忽略不计；(2) 节点与其自身通信所消耗的能量为0；3 符号说明：邻接矩阵；：抗毁性的量化值；：网络损毁概率；、：分别表示为总能量、发射能量、接收能量、备用能量；、：分别表示为发送、接收、备用功率；、：分别表示为发送、接收、备用时间；：第个节点对所有的点发射信息的距离；、：第个节点的坐标；：第个节点对所有的点发射信息所持续的时间；、：分别表示为一断时间内总的发射次数、总的时间；：发射时所消耗的能量；：在某一段时间内因发射所消耗的能量；：节点与个节点的距离之和；F： 能量中心点；：置信区间；：表示每一次发射的起始时刻与下一次发射的起始时刻之间的时间间隔；：节点在时间 及位置 时的概率密度；D：速度的期望值；P：簇内某点最后距起始点距离超过100的概率；4 模型建立与求解4.1 问题1的解决4.1.1 相邻圆的距离相邻圆的半径均为100，根据平面几何的相关知识可以算出当相邻圆的公共面积不小于圆面积的5%时，两圆间距为175.66；当相邻圆的公共面积不小于圆面积的18%时，两圆间距为141.75。4.1.2 相邻圆的连接关系及区域划分显然，当圆以蜂窝状分布时，有最小覆盖，以下的图1给出最简构造。图1以上给出的是临界情况，则连接三个圆心的封闭折线为正三角形，根据本题给出的条件100，易得此正三角形的边长为。当然，在实际情况中圆心间距是不固定的，因此分以下两种情况进行讨论：(1) 圆心间距：此时，若以为边长构成正三角形结构，则在正三角形中心位置会出现小的空隙（见图2中的阴影部分），这对于最小覆盖来说是极其不利的。图2因此，必须将最上方的圆心位置下移，使得此圆的最低点恰好通过下方两圆交点中y方向数值较大的点(如图2中y点所示)，显然连接此三个圆圆心构成的封闭折线为顶角大于60的等腰三角形。就本题来说，当相邻圆的公共面积不小于圆面积的5%时，两圆间距s为175.66，满足此条件。由于等腰三角形顶角大于60，则两腰长度小于底边长度，即上下两层相邻的圆的圆心间距小于175.66，显然此时两圆之间的公共部分更大，符合题目要求。按照此方案，则如图3所示，MATLAB程序见附录程序二（注：其中调用circle函数见附录程序一）。图3通过计算可知，长度 为1000的边至少需要6个圆才能完整覆盖。最下面一层中相邻圆交点中 轴方向数值较小的点与 轴相交，则最有利于最小覆盖。由基础的平面几何知识可求出最下面一层圆的圆心 坐标为47.81，再根据上述“等腰三角形”的理论可得各层间圆的圆心 坐标间距Sy为152.126，这样按层级6、7、6、7间杂排列，就可以得到结果。而 轴方向有空间富余，若发现在边界区域有部分空隙未能覆盖，则可通过在 轴方向的坐标平移来修正。最后检验四条边界及四个顶点，均可落在所有圆覆盖的区域里，则如图3，当相邻圆的公共面积不小于圆面积的5%时可用45个半径 为100的圆覆盖此区域。 (2) 圆心间距 ：此时，若以s为边长构成正三角形结构，则在正三角形中心位置会出现重叠部分（见图4阴影部分）。.图4就直观而言似乎可以将上层圆的位置上移，但结合本题来说是不符合要求的。如：当相邻圆的公共面积不小于圆面积的18%时，两圆间距为141.75，符合此情况。如果上移圆的位置，则连接此三圆圆心构成的封闭折线为顶角小于60的等腰三角形，两腰长度就大于底边长度，即上下两层相邻的圆的圆心间距大于141.75，同时当相邻圆的公共面积就会小于圆面积的18%。因此，本情况只能以边长为圆心间距的正三角形为基础架构可得出区域划分方案（如图5）。MATLAB程序见附录程序三（注：其中调用circle函数见附录程序一）。图5与上面类似，通过计算可知，长度 为1000的边至少需要7个圆才能完整覆盖，则以边长 为141.75的正三角形为基本构架，即各层间圆心在y轴方向间距 为122.759，按层级7、8、7、8间杂排列，可得到结果。最后检验四条边界及四个顶点，最下层的7个圆为了使交点与 轴重合，所能覆盖的 方向长度不到994，而在此情况中最上层与最下层中相邻圆交点在 轴方向上间距 为1000.3，几乎没有在 轴方向上做坐标平移的可能，所以只好再补一个圆，即图5中右下角的圆。则当相邻圆的公共面积不小于圆面积的18%时可以用61个半径为100的圆覆盖此区域。4.1.3 信道分配可将图3中圆按序编号进行改造，如表1：相邻圆的距离示意图s=175.6601 02 03 04 05 0607 08 09 10 11 12 1314 15 16 17 18 1920 21 22 23 24 25 2627 28 29 30 31 3233 34 35 36 37 38 3940 41 42 43 44 45表1以下根据表1，提出邻接矩阵M4545的概念：当i和j邻接时：Mij=1；当i和j不邻接时：Mij=0。具体的矩阵形式参见附录程序五中的MVNVN定义。此后的问题就转化为子集的划分问题，即已知集合A=a1,a2,an，A中关系R=(ai,aj)|ai,ajA,ij，(ai,aj)表示ai与aj间存在关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无关系，同时要求子集个数尽可能少。在此可通过编写子集划分程序来实现，简要的算法描述如下： 集合A进Q；result和work全部置0；当前组号group=1； 依次出队列得e，若worke=0（只考查关系未定的元素），则在work中，标记e的冲突关系。即： 若Mei=1 & worki=0，则worki=1； （避免改写worki为-1的单元） 若worki=0，则resulti=group; worki=-1; 若worki=1，则worki=0; 将所有worki=0的元素，再进队列； group+； 转，直至Q为空。具体的程序见附录程序五(注：程序所需Division.h文件见附录程序四)。由此可得出满足相邻圆的公共面积不小于圆面积的5%条件信道划分结果，见表2：信道1信道2信道3信道41,3,5,13,14,16,18,26,27,29,31,39,40,42,442,4,6,7,15,17,19,20,28,30,32,33,41,43,458,10,12,21,23,25,34,36,389,11,22,24,35,37表2由此可知道要使公共部分的圆拥有不同的信道，最少需要4个信道，示意图见图6。同理，将图5中圆按序编号进行改造，也可以得到满足相邻圆的公共面积不小于圆面积的18%条件的信道划分结果也为4个，其示意图见图7。图6图74.1.4 抗毁性讨论在通信中，抗毁性的定义是在网络有故障时的通信能力，在本题中可以理解为位于圆心的节点在有与外界进行通信的需求时，即使在此圆所覆盖的区域内有部分节点不能正常工作，依然有与外界进行通信的能力；而处于两圆公共部分的节点在这两个圆的圆心节点被抽取时就不具备通信能力了。根据以上的理解可以认为，当相临圆心的节点被抽掉以及一个圆周围的所有与其它圆联通的节点都被抽掉的时候，就会影响整个网络的连通性。针对以上的分析，分以下两种情况进行讨论：(1) 当抽取圆公共部分节点时情况比较复杂，于是考虑将问题简化为抽出特定的一组不在圆心的节点后，网络可能被毁。表3表示这种特定点的分组情况抽取特定点数5的情况18的情况2033106481354662333表3由古典概型的定义可以得出抗毁性的量化标准，但由于计算繁琐，可近一步简化。将以上两组数据加权平均后可得其值都近似等于5，故可以认为特定的5个不位于圆心的节点为抗毁性的基本单位，只要此特定的5点不同时被抽取则可认为网络正常。(2) 当抽取圆中心节点时，若节点数小于2则不影响网络连通；若节点数等于2时，则根据上面的结构可得出公共面积为5%时网络损毁概率为，公共面积为18%时网络损毁概率为；而若节点数大于2时，因为根据题意，在三圆公共部分没有节点，故可近似看作先取两相邻圆在任意取其它圆，则损毁概率与等于2时相同。综合两种情况，再利用古典概型的定义，可近似得出抗毁性的量化值k，罗列如下：公共面积5%的情况抽掉2%（3点）： 抽掉5%（8点）： 抽掉10%（15点）： 抽掉15%（23点）： 公共面积18%的情况抽掉2%（4点）： 抽掉5%（11点）： 抽掉10%（21点）： 抽掉15%（32点）： 4.1.5 问题1总结经过上述四个步骤的计算、编程、求解，我们可以得出，将此正方形区域用若干个半径都是100的圆完全覆盖，在相邻两个圆的公共面积不小于一个圆面积的5%的情况下，最少需要45个圆；相邻两个圆的公共面积不小于一个圆面积的18%的情况下，则最少需要61个圆。分别考虑在公共面积不小于一个圆面积的5%和18%两种情况下，若给每个圆分配一个信道使得有公共部分的圆拥有不同的信道，最少需要的信道数都为4个。若每个公共部分中心和相应圆心各恰有一个节点，在节点集合中，随机地抽掉2%、5%、10%、15%等数量的节点，在公共面积不小于5%和18%的两种情况下，网络的抗毁性可以定量分析得出。对于问题1各问的结果，我们汇总如表4。公共面积5情况公共面积18情况覆盖圆的个数4561所需信道个数44抗毁性抽掉288.8991.69%抽掉588.87%91.6%抽掉1088.8%91.51%抽掉1587.02%88.57%表44.2 问题2的解决4.2.1 替代圆规则为了更好的表述改进后的情况，首先作出相应的图形（见图8）。图8又由于最关心的数据为所有圆的半径和，表5给出部分半径分别为100和75的圆的各自的半径和。圆的个数半径75圆的半径和半径100圆的半径和1751002150200322530043004005375500表5由上表可以直观的看出我们可以接受的替换：1个小圆替换1个大圆，2个小圆替换2个大圆，4个小圆替换3个大圆，6个小圆替换5个大圆而4个小圆可覆盖面积为22500，3个大圆可覆盖面积为30000；6个小圆可覆盖面积为33750，5个大圆可覆盖面积为50000。显然，由于面积与半径为平方关系，需要覆盖多个大圆面积就需要更多的小圆，因此除去大圆覆盖大面积无效的情况，最实惠的做法是用1个小圆去替换1个大圆。显然，在图8中间位置与湖面相交的圆可以用半径为75的小圆代替，左右两边界各有3个大圆可用小一些的圆替代。根据相邻圆之间的公共面积不小于大圆面积的5%，及以我们的方案进行区域划分时相邻两层圆的圆心距不得小于152.126的条件，可以得出这6个圆最小半径约为80。改动后的区域划分如图9所示，其半径和为4355。图94.2.2 信道分配这里的原理与1.3相同，因此直接给出结果示意图，见图10。图104.3 问题3的解决4.3.1 区域的划分首先根据所给的数据画出这些点在正方形区域内的分布散点图，如图11所示。图11显而易见，这些大量的点的分布是杂乱无章的，可由如下思想对此进行分簇：(1) 通过定义一组起始簇中心进行分簇，初始簇中心可随机产生。(2) 根据输入数据把每个数据分到与其最相似的簇。(3) 在分完所有的数据后，更新簇中心以反映分到每一个簇的新的数据情况。(4) 再次检查记录，以确定是否将其重新分到别的簇。(5) 进行递归，直到达到最大递归次数或者前后两次递归之间的差异不超过指定阀值。可以方便地利用统计软件SPSS对这些数据进行分簇，只需满足条件：每个簇中的所有节点到簇中心的最大距离小于等于100即可。其结果见附录表一，示意图见图12。图12此图所示各圆所包含的节点使用相同的信道，由于Ad Hoc网络一跳覆盖区的圆心、半径在不断变化，以上仅是区域划分示意图。当区域中有湖时，编写程序先剔除位于湖中的节点，具体程序见附录程序六。再利用SPSS进行分簇，具体图示见图13。图13图14图15但仅仅以上的结论并不一定能够满足有转发任务的公共面积不小于较大一跳覆盖区面积的5%，因此需要对得到的数据进行修正。为此我们设计了“自适应修正算法”，此算法由两个子程序组成，分别附于附录程序七和程序八。通过程序七可初步检验出所有不满足公共面积5%条件的圆心对，但根据题意，没有转发任务的公共区域并没有5%的要求，显然当公共区域中没有节点时就可以认为没有转发任务。将程序七得出的数据再传入程序八，可进一步判断出有转发任务且不满足5%条件的公共区域。将与这些公共区域相关的圆的半径稍作放大（始终让其不大于100）后得到新的数据重新传入程序七进行迭代，并在此过程中记录下不满足条件的节点数最少时的状态。经过一定次数的迭代后，若仍然存在不满足条件的节点，则调出先前的最佳记录，通过微调圆心位置使所有节点满足要求。修正后的示意图分别见图14和图15。此时，得到的在无湖和有湖状态下全部一跳覆盖区的半径和分别为4670.42672与4361.02504。4.3.2 信道分配方案信道划分的方法如前所述，这里不再赘述，仅给出示意图：图16、图17。图16图174.3.3 区域连通的充分、必要条件由于这里的组网方式是基于簇的，所以在同一簇里的节点既可以作为一跳覆盖区的中心节点，也可以作为公共部分的节点。当一个簇里有节点处在工作状态下，则所处区域也出于连通状态，这就是区域连通的充分条件；反之，当区域连通时，所在簇中至少有一个节点出于工作状态，这即为必要条件。4.3.4 网络的抗毁性对于网络的抗毁性，可借鉴问题1的思路，并根据以上充分、必要条件加以讨论。无湖时的分簇情况有湖时的分簇情况组号 包含点个数组号 包含点个数114.000217.000315.000420.000514.000620.000717.000817.000920.0001016.0001118.0001225.0001315.0001419.0001513.0001618.0001714.0001815.0001915.0002020.0002118.0002216.0002313.0002418.0002517.0002620.0002719.0002816.0002920.0003019.0003117.0003214.0003318.0003419.0003515.0003616.0003720.0003817.0003919.0004017.0004111.0004217.0004314.0004411.0004518.0004619.0004722.0004813.0004920.0005019.0005121.0005218.0005311.0005422.000116.000215.000315.000422.000517.000618.000717.000817.000917.0001020.0001111.0001220.0001319.0001420.0001513.0001616.0001720.0001821.0001914.0002023.0002116.0002223.0002316.0002417.0002517.0002620.0002714.0002817.0002915.0003021.0003119.0003214.0003317.0003417.0003516.0003615.0003714.0003818.0003917.0004018.0004121.0004218.0004311.0004418.0004519.0004613.0004723.0004818.0004919.0005014.000根据以上表格可认为在无湖与有湖状态下的最小抗毁单位均为17。由于节点的大量增多，及运算越来越复杂，甚至导致计算机出现数据溢出的现象，在此给出定性分析。两种情况在抽取2节点时网络毁灭概率的计算公式分别为和，几乎近似等于零，远比第一种划分方式要好。而当抽取比例越来越大时，抗毁性不断衰减，且开始时衰减速度较慢，当到达某一临界值时衰减速率急剧增加。4.4 问题4的解决4.4.1 模型建立在上一问的基础上这里引入了十个以方向角服从0,2均匀分布，速度服从0,2均匀分布的随机变量，其运动方式与物理学中的布朗运动性质相似。因此借助布朗运动的结论，若 以节点在t=0时的位置为原点，则节点在时间 t 及位置 x 时的概率密度可表达为：其中D表示一正常数，在本题中D即为速度的期望值，即D1。由于原本此点在某一簇内，故其最后距起始点不超过100则其联通性不受影响。而当t=400时，距离超过100的概率为：4.4.2 模型验证根据以上结论可认为若节点作布朗运动则几乎不影响网络联通性。当然本题中节点运动所不同的是运动状态不是时时改变，而是间隔30个单位，为了更好地验证这一随机过程，可通过编写程序来模拟此过程，具体程序见附录程序九。再将最终的状态作出直观图，见图18。图18经过程序仿真后所得的结果也可以直观地看出此例中的Ad Hoc网络在400单位时间后是连通的，4.5 问题5的解决4.5.1 理论模型由于节点退出是因为能量耗尽，可见本问题的关键是找出节点能量消耗与起所处位置的关系。为了说明方便，引入如下符号：由于能量E由发射能量、接收能量和备用能量三部分组成，若发射、接收、备用三种状态所对应的功率和时间分别为、和、，则：由于: : =11 : 10 : 1，上式可转换为：其中为常量，显然，要使工作时间尽可能的大，则的值要尽可能的大；反之，要使工作时间t尽可能的小，则的值要尽可能的小。由于两节点之间原始（不是转发）的平均通信次数大致与它们之间的距离的平方成反比，可将发射状态和接收状态归结为通信状态，则可认为节点处于通信状态时其发射和接收状态为等概率事件。根据题目要求，问题转化为找出所有节点中处于备用状态时间最短或处于通信状态时间最长的节点。根据题意，分下列两类情况讨论：(1) 任取一节点，讨论其发射一次所消耗的能量：在给出的所有数据点中任取一点，其坐标为(,)，若此点对所有的点发射信息，则将其距离记为，持续时间记为。根据发射功率近似地与最大传输距离的三次方成正比以及两节点之间原始（不是转发）的平均通信次数大致与它们之间的距离的平方成反比的条件，可以得到如下等式：上式中、为常量，根据题意服从期望为4的指数分布，而所有点的坐标已知，则，已知。由于样本容量为926，足够大，则根据独立同分布的中心极限定理可以得到当=0.05时，其置信区间上下限值约为0.25。由此可见，对的影响可近似看作与呈一次线形关系。(2) 任取一节点，讨论其在某一段时间内对所有点的发射次数：在给出的所有数据点中任取一点，其坐标为(,)，若此点对所有的点发射信息，则将其距离记为。根据两节点之间原始（不是转发）的平均通信次数大致与它们之间的距离的平方成反比的条件，可以得到如下等式：为避免讨论于分母的情况并简化计算，提出每一次发射的单位时间的概念，即每一次发射的起始时刻与下一次发射的起始时刻之间的时间间隔t。则可以得到下式：显然，这里N的变化可看作受的影响，且越小，越大。综合上面的两种情况，在某一段时间内因发射所消耗的能量即为，其改变趋势主要受影响，即方向与相反，趋势与相同。所以要得出处于发射状态时间最长的节点只要找出使有最大值的节点位置即可。而接收状态与发射状态一致，故整个问题可转换为找出使有最大值的节点位置。以下给出推导过程：由于与为常量，使与取得最大值的点坐标为(,)，可以定义此点为能量中心点F。节点离F点越近，则用于通信的能量占总能量的比例越大，耗尽能量而退出网络的时间越早；节点离F点越远，则用于通信的能量占总能量的比例越小，耗尽能量而退出网络的时间越迟。因此，以F点为圆心作圆，其半径越大，此区域内节点能量耗尽而退出网络的时间就越晚，即出现第一个退出网络的节点的时间尽量长。4.5.1 具体实现根据本题所提供的数据可以得到，F点坐标为(493.913,499.031)，以F点为圆心，100为半径，此区域内的节点即为一簇，剩余的节点可按照第3问中有湖的情况进行划分即可。具体的区域划分的方案如图19所示。图19然后再调用程序七、程序八对一跳覆盖区的覆盖范围进行修正，使其满足有转发任务的相邻一跳覆盖区的公共面积不小于较大一跳覆盖区面积5%的条件，并得出在此情况下全部一跳覆盖区的半径和为4549.70887。具体分布见图20。图20根据第3问中区域连通的充分条件，以及本问题中提出的能量中心理论，则在一段时间后，此正方形区域中央的一跳覆盖区首先毁灭，随之其周围的一跳覆盖区相继毁灭，直至最后。所以如果要对组网方式进行改进，可以考虑在能量中心附近多分布一些一跳覆盖区以分担其通信任务。4.6 问题6的解决4.6.1 问题分析本问题要讨论的是一个动态过程，比前面的问题要复杂的多。再加上Ad Hoc特殊的网络拓补结构，以及题目所提供的大量节点使得问题更为复杂。解决复杂的问题自然需要简化，一种方法是对Ad Hoc网络复杂的路由进行等效的分割，通过对部分节点的研究来推导出全局节点的总体特征；另一种方法是在众多影响结果的条件中先着重考虑影响最显著的条件，然后再逐步加入其它条件，使之接近于题设情况。如本题所要讨论的通信质量，可依照以上两条途径寻找解决方案。一条途径是先找出节点与节点之间通信质量的关系，再找到簇与簇之间通信质量的关系，最后归结到整个局域网的通信质量。另一条途径是首先考虑丢包（即重发或延时）的因素，再考虑因节点能量耗尽而退出的因素，最后归纳出所有的因素。当然，将两条途径综合考虑也许更正确，但是由于时间的限制，无法更深一步进行探讨，谨在此提出一些初步的想法。参考文献1 蒋杰，方力，张鹤颖，窦文华 无线传感器网络最小连通覆盖集问题求解算法 Journal of Software Vol.17,No.2,February 2006,pp.175-184.2 潘丽君 战场通信网战时抗毁性初探 装甲兵工程学院学报 2006，4，Vol.20 ,No.2,pp:21-25.3 陈建国 基于管理技术的ATM网络抗毁性研究 信息系统网络 2006，Vol.36,No.4,pp:8-11. 4 张宜华 精通SPSS 清华大学出版社，2002.5 郝黎仁，樊元 SPSS使用统计分析 中国水利水电出版社， 2003.6 张森 张正亮 MATLAB仿真技术与实例应用教程 机械工业出版社， 2004.7 王纪林，贺才兴等 概率论与数理统计 科学出版社， 2000.8 陈华生，张岳新 Visual C+程序设计基础 苏州大学出版社， 2000.9 寿纪麟 数学建模方法与范例 西安交通大学出版社， 1995.附录程序一function h=circle(r,x0,y0,C,Nb) % r 圆的半径。 % x0,y0 圆心座标。% C圆的顏色，不说明时，由指令依序指定。% Nb绘圆时所用点数，若不指定，则以300点为预设值。% the axes ColorOrder property. For several circles C may be a vector. switch nargin case 0 r=;x0=;y0=;C=;Nb=; case 1 x0=;y0=;C=;Nb=; case 2 y0=zeros(1,length(x0);C=;Nb=; case 3 C=;Nb=; case 4 Nb=; end if length(x0)=length(y0), if length(y0)=1, y0=ones(1,length(x0)*y0; elseif length(x0)=1, x0=ones(1,length(y0)*x0; else error(The lengths of x0 and y0 must be identical); end; end; if isempty(r),r=1;end; if isempty(x0),x0=0;end; if isempty(y0),y0=0;end; if isempty(Nb),Nb=300;end; if isempty(C),C=get(gca,colororder);end; if isstr(C),C=C(:);end; x0=x0(:); y0=y0(:); r=r(:); Nb=Nb(:); if length(r)=length(x0) maxk=length(r)*length(x0); else maxk=length(r); end; route=0; if length(x0)=1, route=1; end if length(r)=1, route=2; end if length(x0)=length(r), route=3; end for k=1:maxk switch route case 1 xpos=x0; ypos=y0; rad=r(k); case 2 xpos=x0(k); ypos=y0(k); rad=r; case 3 xpos=x0(k); ypos=y0(k); rad=r(k); otherwise rad=r(fix(k-1)/size(x0,1)+1); xpos=x0(rem(k-1,size(x0,1)+1); ypos=y0(rem(k-1,size(y0,1)+1); end; theta=linspace(0,2*pi,Nb(rem(k-1,size(Nb,1)+1,:)+1); h(k)=line(rad*cos(theta)+xpos,rad*sin(theta)+ypos); set(h(k),color,C(rem(k-1,size(C,1)+1,:); end;程序二x=67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13y=47.8100 47.8100 47.8100 47.8100 47.8100 47.8100 199.9360 199.9360 199.9360 199.9360 199.9360 199.9360 199.9360 352.0620 352.0620 352.0620 352.0620 352.0620 352.0620 504.1880 504.1880 504.1880 504.1880 504.1880 504.1880 504.1880 656.3140 656.3140 656.3140 656.3140 656.3140 656.3140 808.4400 808.4400 808.4400 808.4400 808.4400 808.4400 808.4400 960.5660 960.5660 960.5660 960.5660 960.5660 960.5660 circle(100,x,y)hold on;plot(0:0.1:1000,0)plot(0,0:0.1:1000)plot(0:0.1:1000,1000)plot(1000,0:0.1:1000)程序三x=70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 1063.0000 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500y=70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 316.0580 316.0580 316.0580 316.0580 316.0580 316.0580 316.0580 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 561.5760 561.5760 561.5760 561.5760 561.5760 561.5760 561.5760 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 807.0940 807.0940 807.0940 807.0940 807.0940 807.0940 807.0940 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530circle(100,x,y)hold on;plot(0:0.1:1000,0)plot(0,0:0.1:1000)plot(0:0.1:1000,1000)plot(1000,0:0.1:1000)程序四#define VN 45 / 13 /6 / 结点数#define QSIZE VN+1 / 队列大小：最多存放VN个顶点的下标struct Queue int baseQSIZE; int front,rear;void QueueInit(Queue &Q) Q.front =Q.rear =0; bool QueueEmpty(Queue &Q) if(Q.front=Q.rear) return(true); else return(false);void QueueEnter(Queue &Q, int e) Q.baseQ.rear=e; Q.rear=(Q.rear +1) % QSIZE; int QueueLeave(Queue &Q) int e=Q.baseQ.front; Q.front=(Q.front+1) % QSIZE; return(e);void Division(int MVN, int result) for(int i=0; iVN; i+) resulti=0; int group=1; int e; int workVN; for(i=0; iVN; i+) worki=0; Queue Q; QueueInit(Q); for(i=0; iVN; i+) QueueEnter(Q, i); while(QueueEmpty(Q)=false) while(QueueEmpty(Q)=false) e=QueueLeave(Q); if(worke=0) for(i=0; iVN; i+) if(Mei=1 & worki=0) worki=1; for(i=0; iVN; i+) if(worki=0) resulti=group; worki=-1; if(worki=1) worki=0; for(i=0; iVN; i+) if(resulti=0) QueueEnter(Q, i); group+; 程序五#include iostream.h#include Division.hvoid main() int MVNVN= 0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,