《Ad Hoc网络中的区域划分和资源分配问题第五组》由会员分享，可在线阅读，更多相关《Ad Hoc网络中的区域划分和资源分配问题第五组（37页珍藏版）》请在金锄头文库上搜索。
1、Ad Hoc网络中的区域划分和资源分配问题1 问题重述随着人们对摆脱有线网络束缚、随时随地进行自由通信的渴望，近几年来无线网络通信得到了迅速的发展。为了能够在没有固定基站的地方进行通信， Ad Hoc网络技术应运而生。Ad Hoc网络不需要有线基础设备的支持，通过移动主机自由的组网实现通信。就其特点，在给定一些限制条件下，本文提出了关于如何合理划分 Ad Hoc网络中的区域和分配资源问题。具体内容如下：对一个指定10001000(面积单位)的正方形区域内构建一个Ad Hoc网络，需解决以下问题：(1) 以圆的形式对正方形区域进行覆盖，在满足所给定的限制条件下，通过建立最小半径和模型，求得圆的最
2、少个数。若给每个圆分配一个信道，使得有公共部分的圆拥有不同的信道，在此条件下合理分配信道。改变公共面积部分的限制条件，重复上述问题。再根据条件，提出合理假设，讨论网络的抗毁性问题。(2) 设正方形区域中有一满足给定条件的椭圆形湖泊。由限制条件：节点仅能设置在地面上，以及假设条件：一跳覆盖区圆的半径可以在75100间随意选择，两个面积不等的圆相交，它们之间的公共面积应不小于大圆面积的5%，建立最小半径和模型，研究合理的区域分划和信道分配方案。(3) 在假设一个较短的时间间隔内，网络的连通性可能并未变化的情况下，采用基于节点的划分方式，在某一时刻将正方形区域内的节点（用户）分成若干个簇。给出簇与一
3、跳覆盖区的定义，并根据给定条件结合数据，建立半径最小和模型，研究一跳覆盖区划分和信道分配方案，找出区域连通的充分、必要条件，并讨论网络抗毁性。(4) 在问题3的基础上作进一步假设，根据所给的条件，考虑在动态情况下，通过建立模型，考虑网络连通性问题。(5) 基于前面（3）中所给办法，从节能角度出发，根据所给条件，建立能量消耗与其所处位置关联的求极值模型，找到比较节能的区域分划方式，使出现第一个退出网络的节点的时间尽量长。并通过对该网络的运行状况进行分析，对组网方式提出改进意见。(6) Ad Hoc网络中针对如何保证通信的质量问题，根据所给条件，建立相关模型，对上一题中的通信质量进行定量评价。2
4、模型假设(1) 节点可看作质点，其所占的面积可忽略不计；(2) 节点与其自身通信所消耗的能量为0；3 符号说明：邻接矩阵；：抗毁性的量化值；：网络损毁概率；、：分别表示为总能量、发射能量、接收能量、备用能量；、：分别表示为发送、接收、备用功率；、：分别表示为发送、接收、备用时间；：第个节点对所有的点发射信息的距离；、：第个节点的坐标；：第个节点对所有的点发射信息所持续的时间；、：分别表示为一断时间内总的发射次数、总的时间；：发射时所消耗的能量；：在某一段时间内因发射所消耗的能量；：节点与个节点的距离之和；F： 能量中心点；：置信区间；：表示每一次发射的起始时刻与下一次发射的起始时刻之间的时间间
5、隔；：节点在时间 及位置 时的概率密度；D：速度的期望值；P：簇内某点最后距起始点距离超过100的概率；4 模型建立与求解4.1 问题1的解决4.1.1 相邻圆的距离相邻圆的半径均为100，根据平面几何的相关知识可以算出当相邻圆的公共面积不小于圆面积的5%时，两圆间距为175.66；当相邻圆的公共面积不小于圆面积的18%时，两圆间距为141.75。4.1.2 相邻圆的连接关系及区域划分显然，当圆以蜂窝状分布时，有最小覆盖，以下的图1给出最简构造。图1以上给出的是临界情况，则连接三个圆心的封闭折线为正三角形，根据本题给出的条件100，易得此正三角形的边长为。当然，在实际情况中圆心间距是不固定的，
6、因此分以下两种情况进行讨论：(1) 圆心间距：此时，若以为边长构成正三角形结构，则在正三角形中心位置会出现小的空隙（见图2中的阴影部分），这对于最小覆盖来说是极其不利的。图2因此，必须将最上方的圆心位置下移，使得此圆的最低点恰好通过下方两圆交点中y方向数值较大的点(如图2中y点所示)，显然连接此三个圆圆心构成的封闭折线为顶角大于60的等腰三角形。就本题来说，当相邻圆的公共面积不小于圆面积的5%时，两圆间距s为175.66，满足此条件。由于等腰三角形顶角大于60，则两腰长度小于底边长度，即上下两层相邻的圆的圆心间距小于175.66，显然此时两圆之间的公共部分更大，符合题目要求。按照此方案，则如图
7、3所示，MATLAB程序见附录程序二（注：其中调用circle函数见附录程序一）。图3通过计算可知，长度 为1000的边至少需要6个圆才能完整覆盖。最下面一层中相邻圆交点中 轴方向数值较小的点与 轴相交，则最有利于最小覆盖。由基础的平面几何知识可求出最下面一层圆的圆心 坐标为47.81，再根据上述“等腰三角形”的理论可得各层间圆的圆心 坐标间距Sy为152.126，这样按层级6、7、6、7间杂排列，就可以得到结果。而 轴方向有空间富余，若发现在边界区域有部分空隙未能覆盖，则可通过在 轴方向的坐标平移来修正。最后检验四条边界及四个顶点，均可落在所有圆覆盖的区域里，则如图3，当相邻圆的公共面积不小
8、于圆面积的5%时可用45个半径 为100的圆覆盖此区域。 (2) 圆心间距 ：此时，若以s为边长构成正三角形结构，则在正三角形中心位置会出现重叠部分（见图4阴影部分）。.图4就直观而言似乎可以将上层圆的位置上移，但结合本题来说是不符合要求的。如：当相邻圆的公共面积不小于圆面积的18%时，两圆间距为141.75，符合此情况。如果上移圆的位置，则连接此三圆圆心构成的封闭折线为顶角小于60的等腰三角形，两腰长度就大于底边长度，即上下两层相邻的圆的圆心间距大于141.75，同时当相邻圆的公共面积就会小于圆面积的18%。因此，本情况只能以边长为圆心间距的正三角形为基础架构可得出区域划分方案（如图5）。M
9、ATLAB程序见附录程序三（注：其中调用circle函数见附录程序一）。图5与上面类似，通过计算可知，长度 为1000的边至少需要7个圆才能完整覆盖，则以边长 为141.75的正三角形为基本构架，即各层间圆心在y轴方向间距 为122.759，按层级7、8、7、8间杂排列，可得到结果。最后检验四条边界及四个顶点，最下层的7个圆为了使交点与 轴重合，所能覆盖的 方向长度不到994，而在此情况中最上层与最下层中相邻圆交点在 轴方向上间距 为1000.3，几乎没有在 轴方向上做坐标平移的可能，所以只好再补一个圆，即图5中右下角的圆。则当相邻圆的公共面积不小于圆面积的18%时可以用61个半径为100的圆
10、覆盖此区域。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,
11、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;
12、将所有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中圆按序编号进行改造
13、，也可以得到满足相邻圆的公共面积不小于圆面积的18%条件的信道划分结果也为4个，其示意图见图7。图6图74.1.4 抗毁性讨论在通信中，抗毁性的定义是在网络有故障时的通信能力，在本题中可以理解为位于圆心的节点在有与外界进行通信的需求时，即使在此圆所覆盖的区域内有部分节点不能正常工作，依然有与外界进行通信的能力；而处于两圆公共部分的节点在这两个圆的圆心节点被抽取时就不具备通信能力了。根据以上的理解可以认为，当相临圆心的节点被抽掉以及一个圆周围的所有与其它圆联通的节点都被抽掉的时候，就会影响整个网络的连通性。针对以上的分析，分以下两种情况进行讨论：(1) 当抽取圆公共部分节点时情况比较复杂，于是考
14、虑将问题简化为抽出特定的一组不在圆心的节点后，网络可能被毁。表3表示这种特定点的分组情况抽取特定点数5的情况18的情况2033106481354662333表3由古典概型的定义可以得出抗毁性的量化标准，但由于计算繁琐，可近一步简化。将以上两组数据加权平均后可得其值都近似等于5，故可以认为特定的5个不位于圆心的节点为抗毁性的基本单位，只要此特定的5点不同时被抽取则可认为网络正常。(2) 当抽取圆中心节点时，若节点数小于2则不影响网络连通；若节点数等于2时，则根据上面的结构可得出公共面积为5%时网络损毁概率为，公共面积为18%时网络损毁概率为；而若节点数大于2时，因为根据题意，在三圆公共部分没有节
15、点，故可近似看作先取两相邻圆在任意取其它圆，则损毁概率与等于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
