AdHoc网络连通度的研究综述

第 36 卷 � 第 2 期 2008 年 3 月 � � � � � � � 河南师范大学学报(自然科学版)Journal of H enan N ormal Univ er sity (N atural Science) � � � � � � � Vol . 36 � N o. 2 Mar. 2008 � � 文章编号: 1000- 2367( 2008) 02- 0039- 04 Ad H oc网络连通度的研究综述 王亚丽a ,袁培燕b ,张俊娜a (河南师范大学 a. 计算机与信息技术学院; b. 物理与信息工程学院,河南 新乡 453007) 摘 � 要:对于 Ad Hoc网络的连通度问题, 目前的研究主要以概率论为理论基础, 讨论节点临界的传输范 围以及节点的平均度在什么情况下,保持网络的 k连通. 主要对 Ad H oc网络连通度目前的研究进展进行了综 述,并对将来的研究方向进行了展望. 关键词:连通度; 渗透理论; Ad Hoc网络;无线传感器网络 中图分类号: T P393. 01 � � � � � � � � � � � � � � 文献标识码: A 连通度是 Ad Hoc网络的根本属性.保持网络的连通性对于提高网络的吞吐量至关重要. 对于 Ad Hoc 网络连通度的研究, 目前主要以图论和连续渗透理论[ 1- 5] 作为理论基础, 以移动节点服从泊松分布为前提条 件,以 N 维空间为研究背景, 考察节点在什么样的传输范围下[ 6- 9] 或节点的最小平均度[ 10- 12] 在什么范围内, 整个网络拓扑是 k连通的.这里,假设网络的拓扑结构为一无向图 G(V, E ) ,其中 V 是节点的集合, E 是边的 集合( v i , v j ) , v i , v j � V.如果对于图中任意两个顶点 v i , v j , v i 和 v j 之间至少存在一条路径, 则称 G 是连通 图, 如果存在 k条路径,则称 G是 k 连通的.一般地,当发射功率满足 r � c1 ( ln n + c2) /�n,或节点的度 d满足d � c3 log ( n) ,则网络拓扑是连通的.目前在理论方面存在的开放区域是当N � 2, k � 2时, 关键 的 r, d和 �c 难以界定.这里, 节点的度 d 指节点邻居节点的个数.上述二种研究方法的侧重点刚好相反, 在 CT R问题中,每个节点的 r是固定的, d是变化的; 而在最小平均度问题中, 每个节点的 r 是变化的, d是固定 的,这种差异性的根本原因在于 Ad Hoc网络的移动特性, 因为正是这种移动特性, 造成了局部节点密度 density ( t)的不同. 本文是这样安排的: 第一部分对渗透理论目前的研究进展进行了总结,第 2部分讨论了临界传输范围对 Ad Hoc网络连通度的影响,第 3部分对节点的平均度进行了分析,最后对全文进行了总结并对未来的发展 趋势进行了展望. 1 � 渗透理论 渗透理论[ 1- 7] 是在长期的社会实践中形成的.当人们在研究气体和液体通过一个多孔的媒介时, 它作为 一种统计学的方法首先由 Broadbent 和 Hammersley[ 1] 提出. 渗透理论是揭示状态变化的最简单的模型之 一,当这种关键现象(状态变化)发生时,我们就说发生了渗透.现实生活中, 渗透理论已被广泛应用: 比如油 层在水面上的扩展过程, 检测集成电路是否合格, 森林里面的虫灾和火灾的扩展情况等等. 从数学的观点来 看,渗透理论的迷人之处在于它揭示了概率论与图论拓扑结构的内在关系. 一般地, 说一条边是 p open(信 息流可以通过)的或( 1�p ) closed(信息流不能通过) . 一条路径是 open的当且仅当它的任意一条边都是 open 的.这种模型称之为 bond�percolat ion.类似地,还有一种模型称之为 site�perco lat ion,在这种模型内, 所有的 各边都是 open的, 而每一条边的两个端点是 p open的或( 1�p ) closed.在状态变化的临界处,存在一个概率 p c, 称之为关键概率.当 p < p c 时,网络中的每个集群(由连通的节点组成的集合称为集群,集群的阶是节点 收稿日期: 2006- 12- 27;修回日期 : 2007- 05- 12 基金项目:河南省自然科学基金( 0511012400) ;河南师范大学新引进硕士科研项目( 522204) 作者简介:王亚丽( 1979- ) , 女,河南三门峡人, 河南师范大学讲师,研究方向: 计算机网络. 集合中节点的个数)的大小都是有限的,称网络系统处于 sub�critical状态(不连通状态) ,当 p > p c 时,网络 中可能存在着几个规模为无限大的集群,这时,称网络系统处于 sup�crit ical状态(近似连通状态) .如图 1所 示[ 2] . 这里, ( p ) : = Pp {0 ! } = P p { | C(0) | = ! } , (1) p c: = p c( G ) = sup{ p : ( p ) = 0} . (2) H. KESTEN 证明在二维空间内, bond�per colat ion的关键参数恰好等于1/ 2[ 3] . 即: p bond c ( Z 2 ) = p site c ( T) = 1/ 2. (3) � � 在以后的叙述中, 用 Zd 示 d 维的立方体格子空间, 用 L 或G 表示在上述空间内的一个网络模型. 当 p= p c 时, H . KEST EN研究了二维空间上的无限大集群的初始情况, V an der Hofstad和 Jarai研究了高维空间上的相应情况, 结果表明在 sup�crit ical状态下,无限大集群呈现亚漫射现象, 也就是说经过 n步执行,格子的平均置换次数为 n1- !(!> 0) . 当对上述的网络模型进行修改,允许部分格子可以移动,渗 透现象仍然发生. Benjamini和 Schramm [ 5]提出了下面的概率事 件: p u : = inf { p : Pp (N = 1) = 1} � p c. (4) � � 问题在于当 0 < p c < p u < 1时以及 p u < p < 1时,无限大集群的个数的界定. Peres[ 4] 给出了证明,前 者有无限多个无限大的集群, 而后者只有一个. 这个结论非常重要,因为它否定了随着 p 的增加, 无限大的 集群的个数随之增加的猜测. 除了上述的网络模型之外, Sapoval等人 [ 6]提出了 p 与位置有关的梯度渗透, 以及 Hammer sley 等提出的 p 与时间有关的第一通路渗透,此外还有揭示基因遗传现象的接触过程以及入 侵渗透等等. 上述文献在研究过程中, 主要运用占位理论作为其研究方法.在占位理论中, n 个球独立地放入 C 个格 子中,球放入格子中的放法由描述格子的某些属性的随机变量确定.占位理论的目标是确定当 n和 C 趋近 无穷时这些变量的概率分布(极限概率分布) .占位理论可以用于分析 A d Hoc网络的连通性,可以抽象为把 区域 R分割成相同大小的 n个小区域(格子) ,确定在这种情况下每个格子中至少有一个节点(球)的概率. 同时,上述文献中假定,网络中的某个区域内的节点个数以 Poisson 密度 �分布在二维平面中,如果节 点间距离小于 r 则两个节点相连.已经证明,对于 �> �c,至多以大概率存在一个或多个无限阶的集群.但是, 只存在一个无限阶的集群有时不能保证网络的连通性.事实上, 可能存在许多(无限多)节点不属于这个大集 群,这样就导致不连通的网络拓扑图.因此,连通性与属于大集群的节点占所有节点的比例相关,这个比例又 与渗透概率相关.但是,目前还没有关于渗透概率的显式表达式(如上面所述) . 由于连续渗透理论的模型与 Ad Hoc的网络模型基本吻合,因此连续渗透理论被广泛用于分析 A d Hoc网络的连通性. 下面从节点的临 界传输范围和节点最小平均度两个方面说明渗透理论在研究 Ad Hoc网络连通度方面的应用. 2 � 临界传输范围 研究连通度的重要问题之一是临界传输范围( CTR)问题, 即假定节点都是同构的, 传输范围相同,使网 络保持 k 连通的最小传输范围是多少. 研究这个问题的原因在于在无线传感器网络中,廉价的无线通信部件 不可能动态调整传输范围.在无线传感器网络中, 只能把所有节点的传输范围设为相同的值. 减少功耗、增加 网络容量的惟一办法是把传输范围设为保持网络连通的最小值.最适合解决 CT R问题的概率理论是几何 随机图理论.因为临界传输范围就是 MST 中的最长边[ 6] ,从最长 MST 边的概率分布中可以推导出 CTR的 概率解.但几何随机图理论只适用于密集的 Ad Hoc 网络.因为理论假设放置节点的空间是固定的, 当节点 个数趋于无穷时,节点的密度也趋于无穷.但在实际情况中,网络的密度不可能很大.因为当一个节点进行传 输时,在它通信范围内的其他节点必须保持沉默. 如果节点密度非常大,当一个节点传输时,许多节点都必须 40 河南师范大学学报(自然科学版) � � � � � � � � � � � � � � � � 2008 年 保持沉默,将降低整个网络的容量,当节点的个数 n ∀ ! 时,网络中每个节点可用的带宽为 0. P. Gupta 和 P. R. Kumar [ 7]首先研究了无线网络保持近似连通的临界传输范围问题. 在一个为圆形区 域的单位面积上,当 c( n) ∀ + ! 并且 r= ( ln n+ c( n) ) /�n, 则网络拓扑近似 1连通. P . Gupta 和 P. R. Kumar 是在一个静态拓扑结构下考虑问题的,没有分析不同的移动模型对 CTR的影响,也没有分析在静态 拓扑结构下保持 k连通的问题. Paolo Sant i[ 8]研究了在一定的移动模型下, Ad Hoc 网络保持 1 连通的 CTR, 得出当 r= c ( ln n) / �n 时, Ad Hoc网络近似保持 1连通,并且得出在 Random Waypo int 移动模型下保持 1连通的 r 的表达式为: ( p+ 0. 521 405/ v ) / p ( ln n) /�n.这里 p 表示停留时间, v 表示移动速率.同文献[ 11]一样, Pao lo Sant i没 有研究 k 连通的问题. 上述两篇文献主要研究的是稠密网络,没有考虑稀疏网络下的相关问题. P. Santi和 D. M . Blough [ 9]研 究了稀疏网络下的 k 连通问题,并且得出当 r n � ∀ ( llog l) ,在 1维空间内是连通的,当 r n � O( l) ,在 1维 空间内是不连通的. 这里的 l是指 1 维空间内的区间长度. 在 2 维和 3 维空间内, 当 k � kd 并且 r = r( l ) > > 1时,网络近似为1连通的,这里 k d = 2ddd / 2, d = 2, 3. P. Sant i和 D. M . Blough 没有研究在d 维 空间内的 k 连通问题,也没有研究移动模型对稀疏网络 k连通的影响,即他们是在静态拓扑下考虑问题的. 3 � 节点平均度 研究连通度问题的另一个重要切入点是考察节点的平均度与连通度之间的关系. C. Bet tstet ter [ 10- 11]假 定节点服从均匀分布,研究了移动模型下 r 保持 1连通的节点平均度问题.得出: 当 0 ! r ! 1- r 0 时, #p ( x ) = nr 20 , (5) 当 1- r0 < r ! 1时, #p ( x ) = n/�( r20 arccos ( r 2 + r20 - 1) / 2 rr 0 + arccos ( r 2 - r20 + 1) / 2 r - s/ 2) , (6) 当 0 ! r ! 1- r 0 时, #m( x ) = n(- 2 r20 r2 + 2 r 20 - r 40) , (7) 当 1- r 0 < r ! 1, #m ( x ) = n/ 4�[ 4 r20 (2 r 2 + r 20 - 2) ar csin ( r 2 + r 20 - 1) / 2 rr 0 - 4arcsin ( r 2 - r 20 + 1) / 2 r + s( r2 + 5 r 20 - 3) + 2�(- 2 r 20 r2 + 2 r 20 - r 40 + 1) ] . (8) 则: #( x ) = q#p ( x ) + (1 - q)#m ( x ) . (9) 这里, s = sqrt ( ( r + r 0 + 1) (- r + r0 + 1) ( r - r0 + 1 ) ( r + r 0 - 1) ) , #p ( x ) 和 #m( x ) 分别表示静止节 点和移动节点关于节点度的密度函数, r 和r 0 表示规格化后的节点覆盖范围.并且给出了 #和r 0 的具体值: # # nr 20 / 3( (4 - 2q+ q2) - 4/� q2 - 3(1 - q) r 20) , (10) r0 ! 0. 3. (11) � � Bettstet ter 没有考虑节点之间相互干扰的影响, 也没有考虑节点发射功率不同时的影响. O. Dousse等 人[ 14]研究了节点之间的相互干扰对 Ad Hoc网络连通度的影响, 并且得出了保持 K连通的节点平均度的一 个上限值: 1 + 1/ ( ∃%) .这里%反比于系统的增益,∃为信噪比. F . Xue 和 P. R. Kumar [ 12]利用格子模型和 占位理论研究了不同发射功率下节点的平均度与连通度的关系,得出当 d= 0. 074log n时,网络近似为不连 通的,当 d= 5. 177 4log n时,网络近似为 1连通的. 4 � 结论与今后的工作 本文从 3个方面对 Ad Hoc网络的连通性进行了综述.由上面的分析可知,相关文献大多是在静态拓扑 结构下考虑 1连通的问题,并且假定节点之间是独立的,很少考虑移动模型对 k 连通度的影响,几乎没有分 析节点在不相互独立的情况下能量模型对 k连通度的影响,如何对基于能量的 Ad Hoc网络连通度进行数 学建模与分析, 是我们目前研究的内容之一. 目前国内还没有连通度方面的相关工作, 希望本文能起到一个 抛砖引玉的作用. 41第 2 期 � � � � � � � � � � � � � 王亚丽等: Ad H oc网络连通度的研究综述 参 � 考 � 文 � 献 [ 1] � BROADBENT S R, HAMMERSLEY J M. Percolat ion processes, I and II[ C] . London: Cambridge Philos Soc, 1957: 629- 645. [ 2] � Vincent Bef fara. Percolat ionTh eory[ EB/ OL] . [ 2005- 07- 12] . ht tp: / / w ww . umpa. en s- lyon. f r/ ~ vbef fara/ fil es/ E nc�Perco. pdf . [ 3] � KEST EN H. The crit ical probabi lit y of b on d percolat ion on the squ are lat t ice equals 1/ 2[ J] . Comm Math Phys, 1980, 74: 41- 59. [ 4] � PERES Y. Probabilit y on t rees: an in t rodu ctory clim b, in Lectures on probabili ty th eory and stat ist ics [ C] , Berlin : Springer, 1999: 193- 280. [ 5] � SAPOVAL B, ROSSO M , GOUYET J. T he f ractal natu re of a dif fusion f ront and the r elat ion to percolation [ J] . J Phys Let t, 1985, 46: 146- 156. [ 6] � Pen rose M . A s tr on g law for the longest edge of the min imal spann ing t ree[ J ] . Ann Probab, 1999, 27( 1) : 246- 260. [ 7] � Gupta P, Kumar P R. Crit ical Pow er for Asymptot ic Connectivity in Wireless Netw orks[ M ] . Boston: Birkh�user, 1998: 547- 566. [ 8] � Sant i P. Th e Crit ical Transm itt ing Range for Connect ivity in Mobile Ad H oc Netw orks[ J] . IEEE T rans . on M ob ile Comput in g, 2005, 4( 3) : 310- 317. [ 9] � Sant i P, Bloug h D M . Th e Crit ical T ran smit t ing Ran ge for Conn ect ivity in Sparse Wireless Ad H oc Network s[ J] . IEEE T ran s on Mobile Comput ing, 2003( 2) : 25- 39. [ 10] � Bet t stet ter C. T opology pr opert ies of Ad H oc netw ork s w ith random w aypoint mobil ity[ M ] . ACM MobiH oc Annapol is MD: IEEE Com� puter Society Press, 2003. [ 11] � Douss e O, Baccell i F, T hiran P. Impact of interferences on connectivity in ad�hoc netw or ks [ M ] . CA: IEEE Computer Society Pr ess , 2003: 1724- 1733. [ 12] � Xue F, Kumar P R. Th e Number of Neig hbors n eed ed for Connect ivity of W ireless Netw orks [ J ] . Wireless Network s, 2004, 10: 169- 181. The Survey on Connectivity of Ad Hoc Networks WANG Ya�lia, YUAN Pei�yanb , ZHANG Jun�naa ( a. C ol lege of Com puter and Informat ion T echnology; b. C ol lege of Ph ysical and Informat ion Engin eering, H enan Normal Univer sity, Xinx iang 453007, China) Abstract: For the connectiv ity o f Ad H oc netwo rks, mainly based on the method o f t he probability , the most liter atures focus on t he cr itical tr ansmission range ( CTR ) and the averaged minimum node degr ees in w hich the Ad H oc netw orks could be k�connect ivity. This paper summar izes the present pro cess on the connectiv ity and makes a pr ospect for the futur e r esear ch are� as. Key words: connectiv ity; per colat ion theor y; Ad H oc netw orks; wireless senso r netwo rk 42 河南师范大学学报(自然科学版) � � � � � � � � � � � � � � � � 2008 年