0	动态Ad Hoc网络抗毁性研究 所投刊社及刊社评论 | 作者个人资料
	投票	1条评论 收藏  推荐本文 博客引用 作者:蒋文涛 李连 谢勇    所属分类: IT/互联网/数码

本文章所配附件:

动态Ad Hoc网络抗毁性研究.doc

摘要 摘要：针对动态Ad Hoc网络的特性，提出了抗毁率这一新的网络抗毁性评价指标，在动态网络模型中建立了刻画网络节点连通性状的关联矩阵。在此基础上提出了基于广度优先搜索法的网络连通判定算法和抗毁率计算方法，通过随机试验模拟了动态Ad Hoc网络节点受毁的情况，并定量计算了与时间相关的网络抗毁率，验证了动态Ad Hoc网络的高抗毁性。 正文 字体大小：大 中 小

１　引言 Ad Hoc网络是一组带有无线收发装置的移动通信节点组成的多跳自治系统，具有无需基站、无需特定交换和路由节点、随机组建、灵活接入、移动方便等特点，因而在战场通信、紧急救援、偏远地区通信及其它的一些特殊商业领域中具有极大的吸引力和应用价值。在Ad Hoc网络中，当两个移动节点在彼此通信覆盖范围内时，它们可以直接通信，但由于移动节点通信覆盖范围有限，如果相距较远的两个节点要实现通信，则需要通过它们之间的移动节点转发来实现。Ad Hoc网络相对常规通信网络而言，最大的区别就是可以在任何时刻、任何地点不需要硬件基础网络设施的支持，快速的构建起一个移动通信网络。它的建立不依赖于现有的网络通信设施，具有一定的独立性。此外，Ad Hoc网络中通信节点可以在网中随意移动。节点的移动会导致节点之间的链路增加或消失，节点之间的关系不断发生变化。在自组网中，节点可能同时还是路由器，节点移动会使网络拓扑结构不断发生变化，而且变化的方式和速度都是不可预测的。在Ad Hoc网络中没有中心控制节点，节点通过分布式协议互联，一旦网络的某个或某些节点发生故障，其余的节点通过自由组合仍然能够正常工作，具有很强的抗毁性，很适合恶劣的通信环境。本文建立一种新的评估模型对动态Ad Hoc网络的抗毁性进行了定量研究。 2 抗毁性评价指标 传统的网络抗毁性定义[2,3]为：对于一个网络，网络的抗毁性是指至少需要破坏几个节点或几条链路才能中断部分节点之间的通信，即指出破坏一个网络的困难程度。抗毁性通过两个确定测度—粘聚度和连通度来表示。 粘聚度（Cohesion）： 对于一个连通网络，定义 为断开一对节点 ， 之间所有通路所需去掉的最少链路数，则网络的粘聚度为： 　　连通度（Connectivity）： 　　对于一个连通网络，定义 为断开一对节点 ， 之间所有通路所需去掉的最少节点数，则网络的连通度为： 但这一定义并不适用于动态Ad Hoc网络，因为该网络的拓扑结构是随时间动态变化的，对于网络中任意一对节点，要中断它们之间的通信需要破坏的节点或链路数并不确定，即网络的粘聚度和连通度无法定量求出，这给动态Ad Hoc网络的抗毁性评估带来了困难。为此，需要提出一种更确切的评价指标来表征动态Ad Hoc网络的抗毁性。实质上动态Ad Hoc网络的抗毁性是与时间 密切相关的，并且它应该通过概率值来表征。基于以上分析，提出了抗毁率这一新的评价指标来表征动态Ad Hoc网络的抗毁性。 定义2.1：网络中两节点 ， 不需要通过中间节点转发就能实现通信，则称这两个节点直接连通。 定义2.2：网络中两节点 ， 需要通过中间节点转发才能实现通信，则称这两个节点间接连通。 定义2.3：网络中任意两个节点 ， 都直接或间接连通，则称网络连通。实际应用中当网络节点数很大时，可以接受少量节点不连通的情形，称之为网络弱连通。以连通指数 （即网络中有效连通的节点比率）来表征网络弱连通性状， =1时表示网络连通。 定义2.4：网络中部分节点受到破坏后剩余节点通过重新组织拓扑结构依然实现网络连通的概率，称之为网络抗毁率，以符号 表示。 依据实际情形，可以按一定比例 随机从网络中抽掉部分节点来模拟网络中部分节点受到破坏而退出网络的情况。设随机抽掉节点的总试验次数为 ，其中网络连通的次数为 ，不连通的次数为 ，则网络抗毁性可用抗毁率 来度量。 3 网络模型与计算方法 3.1网络模型 为定量研究动态Ad Hoc网络的抗毁性，给出如下网络模型：设在一个给定区域内存在一个节点数为 的Ad Hoc网络，每个节点 （ ）的初始坐标为 、移动方位角 、移动速度 均给定，网络中每个节点通信范围为半径是 的圆，即当两节点之间距离 不大于 时可直接通信，否则需要由中间节点转发来实现通信。 时刻，网络中节点 （ ）的坐标为： 则 时刻网络中任意两节点 ， 的欧氏距离为： ，其中： 由此可得到刻画网络中节点直接连通性状的关联矩阵 ： 其中 ，( )， 表示 时刻节点 和 直接连通， 表示 时刻节点 和 不直接连通， 实际上为 阶0-1对称矩阵。 3.2网络连通判定算法 动态Ad Hoc网络的连通判定可转化为一个无向图的遍历问题来解决。从无向图的任一顶点出发按广度优先搜索法（Breadth First Search）进行遍历，若得到的广度优先生成树覆盖无向图的所有顶点，则称无向图是连通图。依据上述方法，得出网络连通判定算法如下： 　步骤1：按一定比例 随机从 个节点的网络中抽掉部分节点，剩余的 个节点重新组合成一个新的拓扑网络，节点集为 { ， ， … }； 步骤2：任取新网络中某一节点 为起始点，按广度优先搜索法搜索与 直接连通的节点，如果不能找到这样的节点直接转步骤4；如果能找到，不妨设它们为 ， ， …，扩展它们后组成的节点子集为 ｛ ， ， ， …｝； 步骤3：分别以上一次搜索过程中新扩展的节点为起始点进行广度优先搜索，将本次搜索到的节点扩展到已有节点子集中。设搜索 次后得到新的节点子集为 ，如果 中节点数不大于 ，且 中节点数小于 ，转步骤4；否则重复步骤3； 步骤4：搜索结束，如果最终得到的节点子集 与 中节点数相同，则判定网络连通，否则判定网络不连通。 3.3抗毁率计算方法 1）设网络节点数为 ，按给定的节点初始坐标和运动参数计算出 ，其中 ， ，由此确立网络节点直接联通的关联矩阵 ； 2）按给定的节点抽取比例 确定随机抽取节点数 ，在区间[0，1]中随机产生 个值的序列 ， ，… ，由此可生成随机抽取节点的序号 ， ，… ； 3）将关联矩阵 对应于2）中随机抽取节点序号的行和列的所有元素都置为0，得到新的关联矩阵 ； 4）依据3.2中确立的网络连通判定算法判断网络的连通性，具体方法是：Ⅰ）将 对角线上元素 全部置为0；选取 任一不为0的元素 ，其对应于节点 ；Ⅱ）在第 列中找出值为1的元素的行标，不妨设为 ， ， ，则节点 ， ， 为与 直接联通的节点，得到节点集 ={ ， ， ， }；Ⅲ）将第 行元素全部置为0，然后分别在第 ， ， 列中搜索值为1的元素，并记录其行标号，它们对应于与节点 ， ， 直接联通的节点，剔除重复的节点后得到节点集 ；Ⅳ）重复步骤Ⅲ）直至节点集中节点不再增加，得到最终节点集 ，如果 中节点数 则判定网络连通，否则判定网络不连通； 5）适当选取试验次数 ，重复２）至４）进行多次试验，记录网络连通的次数 ，计算抗毁率 ； 6）计算出对应不同时刻 的 值，绘制抗毁率随时间变化的 曲线。 4 仿真实验 4.1参数设定 在不影响问题实质的前提下，可以自行设定实验参数。设初始时刻网络中节点数 =100，均匀分布于1000×1000（单位 ）的区域内，节点通信半径 =100，各节点运动的方向角 ，速度 是分别服从在[0， ]、[0，2]（单位 ）上均匀分布的随机变量，随机抽取节点数的比例分别取为 ， ，对应每一时刻随机抽取节点试验次数 =1000，取连通指数 =1。为方便计算，进一步限定当节点移动到区域边界时自动反方向运动。 4.2仿真结果 上图是每间隔25s计算一次得到的，从仿真曲线图可以看出，动态Ad Hoc网络具有很高的抗毁率，当 ， 时网络抗毁率分别在0.97和0.955上下浮动，浮动范围分别为[0.967，0.974]和[0.962，0.946]。需要说明的是：1）在网络弱连通情况下连通指数 可取小于1的值，此时网络抗毁率将会更高；2）对应每一时刻 ，随机试验次数 取值越大越好，为控制计算量故取 =1000；3）动态Ad Hoc网络在节点自由移动的情况下，即使不抽取节点也可能出现网络不连通的情况，限于篇幅这里不作深入讨论。 5 结束语 Ad Hoc网络是当前网络和通信技术研究的热点之一，其主要优点在于无需基站、组网灵活、抗毁性好。针对Ad Hoc网络的研究方向主要有以下几种[5,6]：路由协议，MAC（媒体接入控制），QoS，传输协议改进，安全（路由安全、密钥管理）等，其中研究路由协议和MAC的居多，而对动态Ad Hoc网络抗毁性的研究相对较少。本文针对动态Ad Hoc网络的特性，提出了一种新的网络抗毁性评价指标，并构建适当的评估模型对这一特殊网络的抗毁性进行了定量研究。值得说明的是，本文建立的抗毁性评估模型也适用于静态网络，应用时只需将静态网络节点运动的方向角和速度设为0值即可。 参考文献 [1] 罗鹏程，金光，周经伦，刘琦.通信网可靠性研究综述[J].小型微型计算机系统，2002，10(1):1073-1077. [2] 吴俊，谭跃进.复杂网络抗毁性测度研究[J].系统工程学报，2005，20(2)：128-130. [3] 潘勇.通信网络可靠性指标研究[J].电子产品可靠性与环境试验，2006，24(1)：1-5. [4] 陈建国，张永静.通信网络拓扑抗毁性评估算法研究[J].通信系统与网络技术，2006，32(1):6-8 [5] Carbunar B，Grama A,，Vitek J，Carbunar O .Coverage preserving redundancy elimination in sensor networks. In：Znati T，Raghavendra CS，eds．Proc．of the 1st IEEE Conf．on Sensor and Ad Hoc Communications and Networks．Santa Clara：IEEE Press，2004．377−386． [6]FENG K T,LU T E.Velocity and Location Aided Routing for Mobile Ad Hoc Networks[C].Piscataway,NJ:IEEE VIS,2004:2789-2793. 蒋文涛：男，1982年生，硕士生，主要研究方向为网络理论与数据库技术． 李连：男， 1965年生，博士，教授，硕士生导师，主要研究方向为无线传感器网络． 谢勇：男，1982年生，硕士生，主要研究方向为无线传感器网络

备注: 新投稿，正文中公式和图表贴不上去，见附件1

我来说两句