AdHoc网络中的区域划分和资源分配问题第二组

1、全国第三届研究生数学走栈丸拳题冃ad hoc网络中的区域划分和资源分配问题摘要：近年来无线网络通信得到了迅速的发展，而ad hoc网络做为一 种无线通信的载体发展迅速。木文首先建立了 ad hoc网络一跳覆盖 区的基k模型，充分的论证了k取不同值时效果的优劣，得出问题1 结论：5%时采用基6模型，3信道，需45个圆；18%时采用基4模 型，2信道，需60个圆。对于问题2,采用基6模型，得出圆半径之 和最小为4450o论文主要对问题3进行了详细分析，捉出漫路分簇算法，将节点 进行分簇，建立基于模拟退火的圆心漂移模型和最小覆盖圆模型，去 除圆心位置兀余和半径长度兀余，同时进行限制性条件检验，得到无

2、 湖、有湖最小半径之和分别为3925、3625o基于问题3的讨论，对问题4、5、6进行了进一步阐述。（由组委会填写）参赛密码参赛队号10422007一、问题的描述随着人们对摆脱有线网络束缚、随时随地可以进行自由通信的渴望，近儿年 来无线网络通信得到了迅速的发展，无线网络的设计成为当前网络和通信技术研 究的热点本题ad hoc网络的通信设计问题就是在这样一个背景下提出的。 ad hoc网络的出现推进了人们实现在任意环境下的自出通信的进程，同吋它也 为军事通信、灾难救助和临吋通信提供了有效的解决方案。该题讨论的是对一个特定的正方形区域（1000x1000）,采用有一定半径范 围耍求的圆冇重叠的全部

3、覆盖或者对正方形区域屮特定位置的节点进行覆盖。问题有如卜几个方面：在满足一定条件下，如何找到最小数目的覆盖圆？如 何找到所冇半径和最小的覆盖圆的区域分划？在特定的区域分划下，如何确定信 道的数口？如何讨论网络拓扑结构的抗毁性？当正方形区域屮存在一个湖泊吋， 如何改变以上设计寻求最优？当正方形区域中有一定数目固定节点和运动节点 时，如何实现圆覆盖？并讨论其连通性和抗毁性。当把能量、功率、时间等实际 网络运行因素考虑进來后，如何实现i员i覆盖？并提出口己的网络设计观点。二、问题的简化（模型假设）我们针对不同的问题，捉出了下列假设：针对问题（1）,假设覆盖i员i的i员i心位置坐标可以精确定位，在正方

4、形区域内 地形是完全相同的，不考虑地形因索带来的影响；覆盖圆的半径大小也是相同的, 都为100；节点位于圆心或者公共部分的屮心。针对问题（2）,假设覆盖圆的半径可以在75-100之间随意选择；两个面积 不等的圆相交，公共部分的而积不小于大圆而积的5%。针对问题（3）,假设在一个较短的时间间隔内，网络的连通性不变；有转发 任务的相邻圆的公共部分面积不小于较大圆的5%；覆盖圆的半径不大于100o针对问题（4）,假设数据文件给出的前十个数据只做折线运动，每30个单 位时间可能改变一次运动的方向和速度，运动的方向角、速度是分别服从在0, 2ti、0, 2上均匀分布的随机变量；-其他节点不移动；节点到达

5、正方形区域边 界后只能向区域内运动。针对问题（5）假设发射功率与最大传输距离的三次方成正比；网络运行期, 节点保持静止；在a、b两个节点通信时，不存在同吋收发的问题；两节点平均 通信次数与距离的平方成反比；发射、接收和备用状态z间的转换时间以及为获 取网络结构、路曲等公共信息所花的时间和其他资源忽略不计。针对问题（6）假设通信过程屮，重发3次或者延吋30个吋间单位就可能丢 包。三、模型的分析定理1：若干半径为r的圆完全覆盖正方形区域的充分条件是这些圆的内接 正多边形完全覆盖了正方形区域。证明：假设正n边形&覆盖了正方形区域中的色，所有4（i=l，2,， m）,覆盖的区域包含了正方形区域

6、即所有色覆盖的区域包含了正方形区域乩 因为对于由4形成的外接圆q,必包含区域色，所以，所冇q （i=l, 2, m）覆盖的区域必包含了正方形区域b。定理2：四色定理对于一幅地图，最多使用4种颜色，就可以时任意相邻的区域涂上不同颜色, 其等价命题为：没有割边的三正则平面图的边可以三色着色。简单的说明如下：根据“拓扑学”原理，任何复杂形状的每一块区域都可看 成是一个点的集合，两块区域之间相互有交界的可看成这两点之间有连线，只要 证明在一个平而内，相互z间都冇连线的点不会超过四个，也就证明了“四色问 题”。推论：对于1000x1000的正方形平面区域内的任意一跳覆盖区划分，最多 使用4种信道，就可以

7、保证相邻的一跳覆盖区拥有不同的信道。定理3：在两等半径的i员i相交的时候，若两交点夹的劣弧所对的i员i心角e 固定，则相交面积'与整个圆面积s的比值与圆半径r无关，为常数。证明：如图1,两圆的圆心分别为q,勺，半径均为心两交点为a, bo相交面积为sr辭宀押讪色生fsin.今上= _smstir1180 7i由知，k值与圆的半径r无关，定理1得证。 将sin&屮的夕化为数量sin空180.071dk d 0 sin 1801ottde de iso 7i一 (1 ov)=(1-cos)>0180180所以随着&增大，k的值是单调增加的并且增k速度满足正弦形式。两半

8、径相等圆相交，以公共而积中心为坐标原点，圆心距d = 2o。则两圆方程分别为(x-a)2 + y2=r2(x + 6z)2 + y2 = r2公共面积s° = 4叮尺ylr2-(x-a)2dx 令 x-a = t x = t +a50=4*fv/?2-r26/r厂 arcsin仝 99s*” kr2cos20d02s° = tir1 - 2r2 arcsin 一 2ajw = hjir1r针对问题中的相交面积5%, 18%两种情况，由上面公式计算出£亠=5% 时，& = 57.1°sr 亠= 18% 时，& = 89.7°s对于

9、基6模型， = 60 >57.1°,此时k二乞= 5.77%,所以，基6模型可以很好 s的解决公共面积不小于5%的要求。£同理，对于基4模型0 = 90°89.7。，此时，= = 18.17%所以，基4模型可以 s很好的解决公共面积不小于18%的要求。定理4：在保证两圆相交面积不小于两个圆中较大的圆面积的£%时，当两圆半径相等时，公共而积占两个圆总而积的百分比最小。证明：如图两圆，半径/?, > r2 o因为 /?. > /?2,所以soi >so2又因为訂所临纲£=l > 2k%（当且仅当s,】=s°2

10、即r产&时取等）。s°1 + s°2 + 沁s°考虑在一个无限大的平面内采用两种半径k, r2的圆相交完全覆盖平面。定义圆的有效利用率77 =实际两圆在平面内占的面积两圆总而积k%s。 +s°2 _r%s°1s°1 + s°2（当且仅当s。严so2即r= r2时取等）。推论：两i员i相交，满足相交面积不小于一个整i员i面积的£%的条件下，当两 圆半径相等时，圆冇效利用率最高。由定理4及推论，在采用的基k模型当屮，我们选用圆半径相同的情况。定理5：网络拓扑结果中任一节点a不能实现自身对外通信的充要条件为a 节

11、点所在的一跳覆盖区内无其他节点。四、模型建立和求解4.1基k模型算法要将边长为1000的正方形区域用若干各半径为100的圆完全覆盖，圆与圆 z间必然相互交叠，从大止方形和圆的几何形状综合考虑，我们提出基k模型 算法，來实现使用圆对正方形的完全覆盖。算法思想：画出每个圆的内接正k边形，使用正k边形替代圆对正方形区 域进行覆盖。这样便可以使正k边形之间不发生重叠。满足正k边形之间无缝 连接时，只要 10002 （m：正k边形个数，sj 个正k边形的面积），即 可实现全覆盖，当然此时要考虑正k边形超出正方形的面积。所以实际操作吋, 只要实现无缝拼接时沿水平垂直两个方向每个正k边形的有效贡献乘以个数大

12、 于等于1000,即可实现全覆盖，所需正k边形个数即为两个方向上的个数乘积, 也就是所需闘的个数。不难得知，正k边形无缝拼接充要条件：正k边形的角能够整除36（7。下而针对不同k的取值，给出算法的具体实现：（1）当k=3时，即为圆内接止三角形，如图所 示。圆半径为100,可知正三角形边长为iooa/3 ,正 三角形内角为6（/,所以，可以实现无缝拼接。一个三 角形沿水平垂宜两个方向的有效贡献分别为503 , 150 （其中处在两次边界的三角形水平贡献为，另一半处于三角形外）。可以得出水平方向需正三角形个数为卩啤+ 1 = 13个，垂直方向需要的个数为50v3=7个。所以，若用i员i内接正三角形

13、无缝无重叠覆盖正方形所需的个数为13x7 = 91个。(2) 当k=4时，即为圆内接正方形，如图所示。其边t为100v2 ,内角为9(t,也可实现无缝拼接。止方形若正放，沿两个方向上的有效贡献皆为 100血，个数为単1=8个，所以两个方向上都需| 100v2 |要8个，总数为8x8 = 64个。所以垂直方向需要11个止方形，水平方向：第1,3, 5, 7, 9, 11 行需要5个，第2, 4, 6, 8, 10行需要6个，一共是60个。(3) 当k = 5时，即为圆内接正五边形，其内角为108无法整除360。，所以无缝实现无缝拼接。(4) 当k=6吋，即为圆内接正六边形，如图所示。其内角为12

14、0。，可以实现无缝连接，边长为100o垂直 方向贡献150 (其中处于边界的一个止六边形仅贡献 100),水平方向：奇数行有效贡献为100命，偶数行， 首尾两个六边形有效贡献为50的。所以垂直方向需要正六边形的个数为器+匸7,水平方向共7行，奇数行每行需要6个,偶数行每行需要1000 100-150+ 1=7,所以总共需要正六边正方形若与水平成45。放置，垂直方向的有效贡献: 处于边界的两个正方形共贡献100,其余屮间部分每个 正方形贡献100,水平方向的贡献：奇数行贡献200； 偶数行两个边界的正方形各贡献100,其余贡献200。形个数为45个。(5) 当27时，圆内接正k边形的内角必然大于

15、120。且小于1妙,可知无法整除360“。所以，只要圆内接止k边形边数大于等于7,就无法时间无缝拼接了。基k模型的优点：（1）基k模型有效的解决了使用圆形完全覆盖正方形的问题，实现了无缝 拼接。（2）一个正k边形对应一个圆，可以方便的计算出对任意区域不同方式全 覆盖时所需耍的i员i的个数。（3）圆内接正k边形的一条边与圆围成的弓形，即为相邻两个圆的公共面 积的一半，可以方便解决不同公共面积大小的需求。4.2基6模型分析（满足相交面积不小于5%的要求）我们选用如下图所示的基6模型小单元，4.2.1垂直方向如果只有一行，覆盖矩形区域的高为以后每增加一行，其步进距离为 h=i.5r,所以当水平有加行

16、时，能够覆盖的有效矩形高度为y = hi（m_v）r + r = 1.5m/?-0.5/?4.2.2水平方向如果只有一列，其覆盖矩形长度为術/?（从上向下每行鬪个数依次上 12121.）,以后每増加一列（每行圆数壇加1）,能步进距离也r,所以当 竖值有h行时，能够覆盖的有效矩形长度为x = hn-l）r + y/3r = y/3nr4.2.3基6单元排布（正方形区域）正方形区域x = y = 1000j x = y/3nr则由两式y = l,5mr-0.5/?又因为/?只能取75100 z间的数值，加，取正整数。我们采用两种方案寻找较优的加，n以及r方案（1）：固定式的血值，计算出再代入式计算

17、值，对n向上取 整，然后再由m, n的值，计算出所需圆的个数。mnr所需圆个数半径总和761004545008786.96605217.69876.92765845.9方案（2）：固定式的弘计算出/?,再代入式计算加值，对加向上取整, 然后再由加，川的值，计算出所需i员i的个数，再由个数乘以半径得到半径总和, 计算结果如下表。nmr所需圆个数半径总和6896.26525005.57982.48675526.24.2.4结论:由上面两种方案分析可以看出，/?在75100之间随意变动时，半径总和随 着/?的增大而变小，两者成反比。所以，对于问题2建立的目标函数使全部圆半径z和为最小，总体上采用/?

18、 = 100的基6模型进行区域分划。4.2.5信道分配方案给上图红、绿、蓝三种颜色的圆分别赋予不同的信道，由于相同颜色的圆没 有相交的情况。故使用3种信道即可以保证通信。4.2.6基6模型网络抗毁性分析定义：网络的抗毁性，即从节点集合中随机的抽取若干数量的节点后网络是 否仍然连通。由定理5,网络拓扑结构屮任一节点依靠与之相邻的若干节点（即一跳覆盖区中的节点）中转从而实现对外通信。对于基6模型，任一节点a的一跳覆盖区中的其余节点个数m可以取3, 4, 5等数值。一旦同时抽取了 a的这m个节点，a将无法通信。对应于m,我们 计算出图1屮符合条件的a的节点数n,见下表。a相邻节点 个数m3456 符

19、合条件的a的个数n1012845 根据基6模型，我们做出了全部155个节点的网络拓扑结构图，如图7所示。半径为100的圆覆盖正方形下面分析随机的从基6模型网络小抽取k个节点后网络的连通性。观察上面两图即可发现，因为m最小值为3,即某些节点当抽取其周围仅有的m = 3个节点后，该节点即失去其连通性。而符合这个最坏情况的节点a共冇n= 10个。我们采用概率统计的方法对网络抗毁性进行分析。当抽取节点数为k的时 候，对满足m<k的节点，都冇口j能因一跳覆盖区的m个节点被抽取而脱离网 络。对于这样的节点a,我们计算其脱离网络的概率。(1) k=3：154(2) k=4：154154(3) k=5：

20、x 晋+护+*c154c154c154(4) k=6：门ioc；12c：8c；45r = + + +6厂3广4厂5厂6c154c154c154c154(5)当k的值取得比较大时，影响概率的主要是前几项，这里取前三项。几乎+护+兽c154c154c154用matlab计算出相应的k值与人之间的关系曲线图如下所示。因为网络的节点个数为155个，随机抽取2%, 5%, 10%, 15%的点的个数依次为4个，8个，16个，24个。由上面分析，其导致网络不连通的概率如卜表所示。网络随机抽取比例2%5%10%15%抽取节点个数（k）481624导致网络不连通的概率以0.00662%0.00957%1.02

21、%3.96%当抽取60个节点，即抽取比例为38.71%时，网络变的一定不连通。4.3基4模型分析（满足相交面积不小于18%的要求）我们选用如下图所示的基4模型小单元，4.3.1垂直方向主要考虑要覆盖住正方形区域的上下边界。我们用红圆來实现，至少需要5 列，6行。水平跨度为800,垂直跨度为1000。4.3.2水平方向主要考虑要覆盖住正方形区域的左右边界。我们用绿圆来实现，至少需要5 行，6列。水平跨度为1000,垂直跨度为800o这样采用了双色圆如上图排列，垂直方向和水平方向互相弥补，覆盖住了正 方形所有的区域，实现了最有覆盖。所用圆个数为：5x6x2 = 60。4.3.3信道分配方案给上图红

22、、绿两闘分别赋予不同的信道，由于相同颜色的i员i相切没有公共的 区域，不同颜色的圆恰好满足18%的公共面积，所以使用两种信道即可保证通 信。444基4模型网络抗毁性分析根据分析基6模型的思想，我们同样统计了基4模型（图6）的节点个数共计 160 个。对于基4模型，任一节点a的一跳覆盖区中的其余节点个数m可以取3, 4, 5等数值。一旦同时抽取了 a的这m个节点，a将无法通信。对应于m,符合 条件的a的节点数记为n,两者关系见下表。a相邻节点 个数m3456 符合条件的a的个数n1012845 用matlab计算出相应的k值与pk之间的关系曲线图如下所示。因为网络的节点个数为160个，随机抽取2

23、%, 5%, 10%, 15%的点的个数依次为4个，8个，16个，24个。由上面分析，其导致网络不连通的概率如下表所示。网络随机抽取比例2%5%10%15%抽取节点个数（k）481624导致网络不连通的概率人1.37%6.41%27.97%66.52%当抽取29个节点，即抽取比例为18.12%时，网络变的一定不连通。4.5问题1的解答采用半径为100的圆对正方形区域进行完全覆盖（1）若耍求相邻两个圆的公共部分而积不小于一个圆而积的5%,最少需要45个 圆。若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，最少 需要3个信道，信道分配见下图。使用了 3种信道（如图用红、绿、蓝三种 颜色代

24、替），可以保证有公共部分的一跳覆盖区使用不同的信道进行通信。从节点集合中随机抽掉2%、5%、10%、15%的节点后，导致网络不连通的 概率依次为:0.00662%、0.00957%、1.02%、3.96%。（2）若要求相邻两个圆的公共部分面积不小于一个圆面积的18%,最少需要60 个圆（见下图）。若给每个圆分配一个信道，使得有公共部分的圆拥有不同 的信道，最少需要2个信道，信道分配见下图。使用了 2种信道（如图用红、 绿网种颜色代替），可以保证有公共部分的一跳覆盖区使用不同的信道进行 通信。从节点集合屮随机抽掉2%、5%、10%、15%的节点后，导致网络不 连通的概率依次为：1.37%、6.4

25、1%、27.97%、66.52%。4.6问题2的解答4.6.1引理一：在半径范围为7510（）的i员i相交后，如杲半径大的i员i满足相交弦 所对的圆心角大于57.1度（或者大于60度），那么无论小圆的半径是多少，都 满足相交后面积大于大圆面积的5%o证明：如下图，显然，当大圆与小圆相交的时候，同样的相交弦，大圆所对 应的弓形而积a必然小于小圆所对应的弓形而积b。当两个大圆相交时，如果 圆心角都是57度的时候，相交的面积刚好为大i员i面积（两个都是大i员i）的5%； 现在一个换成了小圆，相交的面积会增大，即a + b的面积会大于大圆面积的 5%。所以大圆与小圆相交的时候，只需要注意大圆的圆心角在

26、57.1度以上，就 可以保证相交面积大于大圆面积的5%。57.1根据这个引理，我们可以计算出两个不同半径的圆的圆心距，本题我们先用 半径为100的大圆覆盖整个1000x1000的正方形，遇见湖而后，去掉湖里而的 闘心，这样必然会使一部分湖周围的面积不在覆盖区内，需要向那些面积中投放 新的比较小的半径的圆。其中的极限情况是加入了半径为75的小圆，这样的话, 计算出来的圆心距为162.5207,所以当小圆半径在75100之间活动的吋候，圆 心距在162.5207173.2之间活动。所以加入小圆的时候，只需要保证加入的小 圆与大圆z间的圆心距大于162.5207,则可以保证相交而积为大圆而积的5%。

27、 4.6.2湖泊的处理椭圆形湖泊中心在（550, 550）,长轴与正方形水平的成30度角。长轴为 410,短轴为210,其与用半径为/?=100的圆进行区域分划后的相对位置图像如 下图所示：可以看到将湖泊屮的节点（圆）去掉后，湖泊周围出现了几块未能覆盖的区 域。因为 /?=100, m = 7, /2 = 5.77 （取整后 =6）。所以覆盖了止方形区域的基6模型，在水平方向存在冗余，在竖直方向布存 在。即在水平方向可以轻微的左右移动。我们利用matlab进行水平微调处理后，使圆心未被覆盖的区域面积尽量少。 这样，我们对未被覆盖的区域再用半径较小的圆进行覆盖，并满足公共相交面积 不小于大圆而积

28、的5%的要求，最后做出的区域分划图如下，半径总和为4450。信道分配方案仍采用3信道。4.7问题3的解答：前面两问分析了采用基6模型的静态区域分划方案。静态区域分划方案虽然 可以保证处于正方形区域的节点在任意位置都可以实现通信，但由于其未考虑吋 间节点的分别情况，因而覆盖圆的个数及半径存在冗余。对于附件1给岀的数据作为静止节点，我们采用基于节点的划分方式。（-）无湖情况分析我们给出如下分析步骤：第一步：采用漫路分簇算法，将正方形区域内的926个节点进行分簇；第二步：建立基于模拟退火的圆心飘移模型，对整个分簇之后的圆一跳覆盖区域 进行圆的位置调整，去除位置冗余；第三步：建立最小圆覆盖模型，对于每

29、一个一跳覆盖区进行半径调整，去除半径 冗余；第四步：对调整之后的一跳覆盖区，检验是否满足两个限制条件：节点的连通性 和有转发任务的节点面积不小于大圆面积的5%。若满足，转向第五步；若不满 足，增大半径进行再次检验；第五步：计算岀每个一跳覆盖区对应的圆的半径、圆的个数，求出全部一跳覆盖 区半径之和。(1)针对第一步：我们提出如下漫路分簇算法。算法： 对附录中926个节点，首先按横坐标的大学进行排序，形成926x2的节点矩 阵a。 初始化生成50x2的零矩阵b和926x2的零矩阵c。 将a的笫一个节点a (1)放到b中，b中节点的重心o为b (l)o 依次取a中第k个节点a (k), k = 2,

30、 3,，926,比较a (k)与重心o之 间的距离d,若dw200,则将a (k)放到矩阵b中并重新计算b中所有节点 重心o；若d>200,则将a (k)放到c中。 若矩阵c全为0,则程序停止，若c非0,则将矩阵c全部赋给矩阵a,重新 进行的计算。采用漫路分簇算法后的节点划分图如下：原始图02004006008001000由48个大圆组成，大圆半径为100,半径z和为4800。可以看到，分簇后都采用半径为r=100的圆覆盖是不合理的，并且簇与簇 之间覆盖圆存在圆位置的冗余和圆半径长度带来的冗余。因此，我们采取下面处 理方式除掉这两块兀余。（2）基于模拟退火的圆心漂移模型保持一跳覆盖区的半

31、径r=100不变，对于某一个一跳覆盖区m,其圆心坐 标为（兀"儿），内部的节点为加个（分别为，灯）。我们随机产生一个小 的增量込”,a）；”，使覆盖区m的圆心坐标移至（兀“+心加儿+ay），以此圆心 做半径为r=100的圆，计算其内部所包含的节点的个数叫。若新形成的圆不能 包含原来的加个节点«,心，,匕，则放弃此次调整；若新形成的i员i包含了原來的 m个节点，则进行下一步分析m与s的关系。若加（）m ,将圆心依一个小概率移至（，九+儿）处；若叫 m ,则令叫=m ,并将圆心依一个较大概率移至（兀” +, ym + avw ）。无湖全大圆情况结果如下图所示：100090080

32、0700600500400300200100002004006008001000图中只需要40个大圆，圆半径为100,半径之和为4000o可以看击，基于 模拟退火的圆心漂移模世冇效的去除了由丁圆的位置兎叠带来的兀余。（3）建立最小圆覆盖模型在本步骤中我们主要去除曲于某些一跳覆盖区半径r过人引起的冗余。分析某一跳覆盖区m,圆心q”为（兀”九），半径为r,连接圆心乙与节点处,交圆于弘记 = 0“£一0北=r-臥建立口标函数求使得d为最小的圆心（乙，儿）和半径心。;=1（4）对于限制条件的解决限制条件1：由转发任务的相邻一跳覆盖区公共面积不小于较大一跳覆盖 区而积的5%；限制条件厶所有节点

33、连通。对于某一跳覆盖区m,记其周围相邻的一跳覆盖区有刃个，分别为（/=1,，n） o定义两个集合：d=被包含的节点；d, = 被m包含的节点 o若经过（1）（2）（3）的处理后，dm o d ,则将一跳覆盖区m去掉;若dm a d , 则保留mo分别记冏（j=l,，m）的圆心坐标为q （i=l,，）,m的圆心为q”。下而分析如何满足限制条件1：大圆半径为r,小圆半径为门记 s（）=5%r2 极限条件下为小圆面积2=s°=5%临f,则- = v05o即当两不等圆半r径z比（小的比大的）73厉时，限制条件1不能满足。若- = voi）5,小r圆被大圆完全包围，小圆的作用完全消失，如图。

34、卜面分析小圆远离大圆运动，远离过程中口身半径变大，当两圆心z间距离 为侖/?时，小圆半径r等于大圆半径r,如图所示。恰为前面讨论的基6模 型的一个小单元。 当两圆圆心之间距离d满足(l-vo05)/?<j<v3/? dt,小圆的弦相对的圆心角为20,大圆为2a,弦长一半为仁a = arcsin r0 = arcsin r-r22a-r2sn2a + -r226-r2sn23 = 5%7rr22 2 2 2r2 arcsin -ljr，一卩 + r arcsin-llr2 -i2 = 5%7tr2rr由可得r, r与/的关系，由式可以求出/的值。/已知，则可以求出圆心距d = v/?

35、2-/2+vr2-/2所以对于一跳覆盖区m周围的n个相邻覆盖区找出至少有一个d = °” -q满足式的关系。下而分析如何满足限制条件2：设一跳覆盖区m与周围的斤个覆盖区m, (z=l, n)相交区域为4 (i =1,，m),定义bj=4中的节点数。若bub2uub”h0则可满足条件2；若不满足，则采取扩大m半径的方式来寻求式的满足。若扩大m半径至100仍不满足式，则随机抽取扩大其半径直至式满 足。无湖大小圆情况经过上述步骤处理后，我们得到了无湖情况卜全部一跳覆盖半径z和为最小 的一跳覆盖区划分方案。如下图所示。1000900800700600500400300200100其中半径为1

36、00的圆30个，半径为98、95、85、77的圆分别为2个，半径 为83、72、60各1个，总共41个圆，半径之和为3925。其相应圆的圆心处标 见附录。信道分配仍采用3信道通信。（-）有湖情况有湖时，节点数目由926个变为866个。具体实现算法和无湖时大致相同， 只是在对节点进行分簇之前，首先要将落在湖中的节点去掉，再进行类似于无湖 情况的处理：基于漫路算法的分簇处理；基于模拟退火的圆心漂移模型的去除圆 位置兀余；基于最小圆覆盖模型的去除圆的半径长度兀余；限制条件的检验等， 在此不再赘述。侑湖泊）大小圆情况处理z后的结果如21000900800700600500400300200100其中半

37、径为100的圆32个，半径为90、80的圆各2个,半径85的圆1个, 总共37个圆,半径之和为3625o4.8问题4的解答:（1）节点运动一次概率分布对任一运动的节点分析其一次运动后的情况，以运动前位置为坐标原点。 因为节点£运动方向角，速度服从0,2刃，0, 2上的均匀分布，所以一次运动 后p必落在半径为60的圆内，并11对于固定的环环宽度d, pj落在两个圆环%内的概率相等。设p沿原点向外分布的概率密度为p(r) r 0,6060贝|j f(厂)=>(/)(/+ &)2_尸=«(/)*2伽0 0i f(0) = 0f(60) = 1 所以，p(t) = -

38、9 2cr =,得出 c =一，t60120c1所以p(r) = - =re 0,60r 120rf(厂)=右 y0,604.9问题5的解答：(1)能量与传输距离关系设节点处于发射、接收和备用三种状态下功率分别为片,£，人，月.人：£：£ =11:10:1。令人=1 比肝，则p2=10kd39 p3=kd3o节点在r= 100发送状态下工作总时间为400个时间单位，节点总能量e为e = pt = l r,/?3 *400 = 4.4 *109则节点总能量e与传输距离d的关系为e = pxt = kxd3,(2) 通信次数与传输距离的关系节点i与节点j的原始通信次数

39、设为® ,令代吟每个节点平均产生25次呼出，必然对应平均25次呼入。926 925©=25*2*926z=1 jw=l解上述两个方程可得込=30273027no =(3) 网络节点运行能力与一跳覆盖区半径关系对于r=100,发送状态下工作总时间为400个时间单位，取e = 400o在平 均意义上，每个节点平均产生25次呼出必有25次接收，每次通信时间平均为4 个单位时间。w3=p3t3 = p3(1200-t-t2) =1000tt=91h*100 = 91wj +w2+w3 =282 <400故r=100的圆作为一跳覆盖区在平均意义下网络可以运行1200个时间单 位

40、。下面分析半径r减小到任一节点可以保持在最高功率工作1200个时间单位 的状况。对于节点其中为中转。因为中转时既需要接收也需要发射，故中转节点工作时其功率&)=(11 + 10)你/3=2比夕，所以全部工作持续时间为*400,所以若想其工21作1200个时间单位，其最远发射距离为21任(心a j * 100 = 2 比 * 100? * 耳 * 400解得尺杯=55.9所以当圆半径/?<55.9时，可以保证网络中任一节点在任何条件下运行1200 个单位吋间。(4) r,网络节点平均距离7与中转点个数的关系:926 926厂 527.86计算网络中926个节点的平均距离所以在7长度

41、下，屮转点个数m考虑到时间传送绕路,d0rrr+血r+血r + 2血 屮转点n012 1(925)2/=1 >1考虑在一排平行圆排列情况可以看出每增加的/?长度，其中转点个数增1。取"=备。节点m,实现对目标忆一次通信消耗的网络能量为£, =(ll + 10+21n)/?3f = 84(/? +1* r3两节点z间平均通信次数列=务嘤dij dij3027m,通信一次引起的网络的总能量消耗e = e、nff = 84代+ 1肿 °2784 g-yr疋+ 3027咖嗚r3总能耗e取值越少，则整个网络的能耗越少。(5) 网络节点退出分析t（t） =926 926

42、 一 /? l一亍离 j= 252.55平均每个中转点 e“.261200 e25（ v + 仔）+ （彳 + 停）* 5.26 + 出（1200 - 50f -10.52/）1200e当/一时，° = 0 k其中：k = 2.0872e a = 2.08724.10问题6的解答在问题(5)中，已经计算出了网络中存在转发任务的节点大约是46个，每 个节点在整个网络运行时间内在平均的转发任务是5.26个。因为网络屮任务最为繁忙的是有转发任务的节点，因此网络屮其它节点相对 于转发节点的通信也最不容易满足，即最容易丢包。两节点z间平均通信次数®=¥=攀,%5取 n.=3

43、027在平均距离下一次通信引起的转发点个数:n = l-v3/?所以由通信概率加权后的一次通信引起的转发点个数为:_ _ 3027 d _ 3027可见，因为d为常数，所以通信一次引起平均转发点的个数与使用的一跳覆 盖区的半径成反比。五. 模型评价及改进模型优点： 在对正方形区域进行节点划分过程中，针对所有圆半径最小的目标要求，我 们的模型建立了完善的算法（漫路分簇算法、模拟退火的圆心漂移算法和最 小覆盖圆算法），这是木模型的第一大特色。 该模型冇严格的理论基础，在模型分析中，将本题实际和经典的数学理论结 合在一起是该模型的又一一大特色。在严格的数学定理、定律的支持下，下 面的讨论变得充分有力

44、。 模型充分论证了基k模型，通过分析计算，从k的取值屮挑选出适合5%要 求的基6模型和适合18%要求的基4模型，并且反面说明了其它基k模型存 在的不足。通过正反对比，得出基k （k=4、6）是较优的解决该问题的工具。模型不足：我们的模型仍然存在很大的不足，主要体现在一下儿个方面： 最大的不足是在用模拟退火进行寻找半径z和最小时，无法证明结论达到全局最优。这也是该类模型最大的一个理论证明上的不足。 对问题4、5、6的论证不是很充分。下面我们对模型进行少许的改进：根据移动通讯的蜂窝模型，针对相交面积比例是5%的要求，我们提出了圆 心为顶点的正六边形排列方式，绘制出了如下的图，如图1,这种方法排列需

45、要 45个半径为100的圆，圆心距为巧计算其每两个相交圆之间的比例占圆面 积的5.5%,符合题意。当相交面积的比例由5%增大到18%的时候，我们提出 了正四边形的排列方式，如图2,这种方法排列需要60个半径为100的圆，圆 心距为血尺。这种排列口j以是相交面积比例可以达到18.2%,也刚好满足要求。推广：我们看到第二幅图中有49个图完全占据了大多数的正方形面积，只 剩下两个1000x10的窄矩形窗口，如果再用半径为100的圆覆盖，是非常浪费 的，于是我们考虑，是否能将圆心距稍微增大（即犬于近r）,这样所有的圆就有可能全部覆盖住止方形区域。鉴于时间的原因，在此未能做进一步的分析和讨 论。图1图2

46、有窄图3曲于时间的原因，论文还冇很多值得改进的地方，恳请老师批评改正。参考文献：1 姜启源，谢金星，叶俊.数学模型(第三版)，高等教育出版社。2 杨中华.平面点列最小覆盖圆的计算方法，北京工业大学学报, 2000,vol.26(2).3 蔡锁章.数学建模原理与方法，海军出版社。附录部分程序清单：1无湖泊半径为100的圆所截节点图(x,y为附录中节点坐标)plot(x；yjb);axis equal;axis(0 1000 0 1000);山1*(无湖泊)半径为10()的圆所截节点图jhold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot( 100*cos(

47、t)+500)+100*sqrt(3)*k-50*sqrt(3)*m,( 100*sin(t)+500)+150*m,t)endend2. 冇湖泊半径为100的関所截节点图t=0:(pi/100):2*pi;a=550+205*cos(t);b=550+105*sin(t);c=cos(-pi/6)*205*cos(t)+sin(-pi/6)* 105*sin(t)+550;d=-sin(-pi/6)*205 *cos(t)+cos(-pi/6) * 105 *sin(t)+550;% c;d=lcos(pi/6),sin(pi/6);-sin(pi/6),cos(pi/6)*la;bj;pl

48、ot(c,d,k);for i= 1:926讦(sqrt(3)*(x(i)-550)/2+(y(i)-550)/2).a2/205.a2+(-(x(i)-550)/2+sqrt(3)*(y(i)-550)/2).a2/105.a2-l<0 plot(x(i),y(i)；w/);elseendendtitlcc(冇湖泊)半径为100的圆所截节点图)hold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot(100*cos(t)+500)+ 100*sqrt(3)*k-50*sqrt(3)*m,( 100*sin(t)+500)+150*m,t)endend

49、hold ont=0:pi/200:2*piplot( 100*cos(t)+500,100*sin(t)+500,'w.')t=0:pi/200:2*piplot( 100*cos +500+50*sqrt(3), 100*sin(t)+500+150,'wj)t=0:pi/200:2*pi plot(sqrt(3)*50*cos(t)4-50()4-50*sqrt(3),50*sqrt(3)*sin(t)4-500+200,'g')3. 网络抗毁分析程序：for k= 1:62y=10*k*(k-l)*(k-2)/(155*154*153)+12*k

50、*(k-l)*(k-2)*(k-3)/(155*154*153*152)+8*k*(k-l)*(k- 2)*(k-3)*(k-4)/(155*154*153*152*151)+45*k*(k-l)*(k-2)*(k-3)*(k-4)*(k-5)/(155*154*153*152*151*150)plot(k,y；r.')hold onend4. 有湖时补圆程序：t=0:(pi/100):2*pi;a=550+205*cos(t);b=550+105*sin(t);c=cos(-pi/6)*205*cos(t)+sin(-pi/6)*105*sin(t)+550;d=-sin(-pi/6

51、)*205 *cos(t)+cos(-pi/6) * 105 *sin(t)+550;% c;d=cos(pi/6),sin(pi/6);-sin(pi/6),cos(pi/6)*a;b;plot(c,d,k);axis equal;axisdo 1000 0 1000j);hold onfor i= 1:926讦(sqrt(3)*(x(i)-550)/2+(y(i)-550)/2).a2/205.a2+(-(x(i)-550)/2+sqrt(3)*(y(i)-550)/2).a2/105.a2-l<0 plot(x(i),y(i)；w?);elseendendhold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot( 100*cos(t)+50)+300*k+150*m,( 100*sin(t)+50*sqrt(3)+100*sqrt(3)*m,'r*)endendhold onplot( 100*cos(t)+