论文研究-P2P分域网络动态负载均衡调度的抗脆弱性策略.pdf

所需积分/C币:5 2019-09-12 19:10:12 679KB .PDF

干扰是严重影响Ad hoc网络的网络吞吐率主要原因之一。已有的基于网络链路和路径的局部干扰优化算法并未考虑网络中准瓶颈节点对网络干扰的影响,准瓶颈节点不仅影响网络的吞吐率,还可能破坏网络的连通性。利用分布式算法找出准瓶颈节点,构建链路干扰度的本地最小生成树,提出一种新的干扰优化拓扑控制算法(Quasi-bottleneck node-based Interference-optimization Algorithm,QIA),有效地降低准瓶颈节点对网络的干扰。仿真实验结果表明,QIA算法在保证网络连通性的前提下,降低了网络干扰。该算法同经典干扰优化拓扑控制算法相比,网络吞吐率提高了约10%~3
64 2011,47(24) Computer Engineering and Applications计算机工程与应用 (12)节点u通过Hell通告方式告知相应节点,使其改变 功率设置保证所加边的建立。 (13)若 UnConnected(Gn),转(11)。 (14)Eo=E+E;若v⑧,算法结東;反之,转(2) 节点u通过邻居信息通告,获取两跳范围内拓扑信息(2 (3)),以链路十扰度为权值构建本地最小生成树((4)~(7) 图2准瓶颈节点刈网络影响 判定节点是否为准瓶颈节点(9)-(10)),若是,则依据(11) 节点,则其干扰度I(u(G))为: (13)消除网络准瓶颈节点。 3.2算法分析和拓扑结构性质分析 mc T(u), nc T(u).ec sP.( (() 网终中的每个节点独立异步地运行QA算法,在算法的 SPG ,V为准瓶颈节点(4) V,V为瓶颈节点 第(3)步每对邻近节点之间交互两次,第(9)步交互一次,第 (12)步交互一次。虽然节点异步执行,但由于每个节点仅仅 其中,SPn(G")为拓扑结构G′=(V-,E-e(u)中满足m 只需与各自邻近节点进行消息交互而无需转发,利用MACA 的最短路径,l(e)为边e∈E的链路下扰度。 冲突避免机制,所有节点可以在一个常数时间区间内完成消 为了分析各拓扑算法对网络干扰效果,从准瓶颈节点角 息交互操作。 度给出网络干扰模型,对于网络拓扑图G,定义其网络干扰 交互消息的主要目的是使得每个节点获取局部信息,用 度r(G)为图G中准瓶颈节点的平均干扰度与平均路径干扰度以构建一个仅由邻近节点构成的拓扑子图,图3给出了QA拓 之和 ∑ 扑图和UDG拓扑图,从图3可知子图(a)中的节点数m和边数 (u(G) l(e mc,nC,≠n,ecSP(G e远小于图(b),这使得每个节点在第四步运行最小生成树算 (G)= B(G) SPm(G) (5) 法O( eloge)的实际运行时间代价很小。由此叮见QIA算法具 有分布式、基于局部信息、算法简单、消息开销小和收敛快的 基于准瓶颈节点的干扰优化拓扑控制算法 特点。并且对于原拓扑图G,QIA算法生成的拓扑结构能够保 QIA算法主要由两部分构成。首先,在原始拓扑结构G证网络连通性。 中,节点u以链路干扰度为权值构造最小生成树,此时所构建 中的网络拓扑结构G具有局部干扰最小的特性。其次QA算 法依据准瓶颈节点定义在拓扑结构T(u)中判定节点u是否为 准瓶颈节点,其中,7(u)=(V-u,En-e(u)),若是,则在r(u) 屮选择具有最小干扰度的链路e(u,ν)加入边集。 31算法伪代码 QIA算法伪代码如下: (a)Ql (bUDG 图3QIA、UDG拓扑图 输入原始网络拓扑图G(V,E)。 输出执行QIA算法后的拓扑图Go(Vo,Eau)。 引理1对于任意节点对(u,ν),u,y∈V,若d(u,y)≤Rms, (1)初始化集合VA=V,EoA=②。 则台v成立。 (2)当⑧,对节点∈V构造其Rm内QIA拓扑子图 证明对于所有满足d(u,ν)<Rm的节点u,ycV,将它们 G,Gn=(V,E),且初始化V=,E=,令V=V-{l} 按照链路干扰度I(u,ν)增序排序。假设I(u1,w)<(u,v2)<…< (3)节点通过在R灬内进行Hel消息通告,收集邻居信(un,vn),利用数学归纳法证明: 息,统计N(n)并计算与各个邻居节点v∈M(n)的边干扰度e)。 (1)令k=1,第·个节点对(u,n)满足d(u,v1)<Rax,因此 (4)若=(u),则转(7)。 有u少v,l分v成立。 (5)从节点集{V-V}中选取满足(u,v)≤Ram,.且具有最小 (2)假设引理1对前i个节点对(u,ν),=1,2,…,k-1都 I(en)的节点v,令V=V∪v;EoA=EoUe(u,v)Ue(v,n)。 成立: ()若V<(u),则转(5) ①假设u(v成立,则分以成立 (7)选择节点ν∈V,满足ε(u,v)∈e(u),令V=v,En= ②2假设uv不成立,由于d(l,v)≤Rm,因此存在路径p e(u,y)+e(v,u)。 (v。=,W,12,…,1n=ν),÷0,1,…,m-1。记T为节点l的 (8)对所有节点t∈F,令G=(V,E1),其中V=V,E:=传输范围Rn内的一棵最小生成树,且(w,w-)<(t,v);若 E+E 节点u的R灬范围内存在另一棵具有最小链路干扰度的生成树 (9)节点u与其所有一跳邻居节点v进行消息通告,构建则将边(u,v)替换为边(w,w),并保存灬其他边。归纳到节 其两跳范围内子拓扑结构G=(V,E),其中=V+,E=点对(m,w-),=0,1,…,m-1,得到ww,可知mnwm, E+EN 因此有 (10)令G=(V-M,En-e(u),若 Connected(G)成立, 定理1若原拓扑结构G连通,则拓扑结构Go连通。 转专(14) 证明由于G为GoA的子集,因此通过G的连通性证明 (11)在G中选取具有最小T扰度的边e(u,y),并令E=G连通性。假没G不连通,则存在节点对(v,),满足链路 En+e(u,v)+e(v,u)。 干扰度I(v,ν)小于G中其他不可达节点对的链路干扰度。 王东,蔡小莉,李晓鸿,等:基于准瓶颈节点的干扰优化祏扑控制算法 2011,47(24) 65 iLDC a LIFE I LE UDG --API D LIFE OIA 品=API 10 QIA 8 111 护计 00 80 0.1 406080100120140160180 80100120140160180 网络密度 网络密度 (a)平均节点度 (b)平均节点传输半径 100 l00 La. UDG 日LIFE D LIFE THE API -E OIA QIA 二之二 一一 0.I 6080100120140 406080100120140160180 网络密度 网络密度 (c)平均链路干扰度 (d)a 图4拓扑结构特性比较 由于G为连通图,因此有d(ν,ν)≤Ra。根据引理1,有ν兮拓扑结构,既减小了网络局部干扰,又保证了路径长度稳定, 4v,与假设矛盾。因此G连通可知Go连通。 减小了路径干扰,同原始拓扑结构相比,优化了网络干扰,图44 (d)中表现为α值减小。基于准瓶颈节点干扰优化的QIA算 4性能评佔 法,在优化恻络局部干扰的基础上,运行了內络准瓶颈节点优 41拓扑结构的性能 化策略,减少了由亍准瓶颈节点处信道竞争从而带来的大量 本文主要考察了网络平均节点度、平均节点传输半径、网千扰,使得网络干扰为三种拓扑控制算法中最少的,同时图4 络平均链路干扰度以及基于准瓶颈节点的网络干扰度,并且(d)中表现为其a值为三种拓扑控制算法中最小的。 为了直观分析相关干扰优化算法对网络全局干扰的优化程42网络性能仿真 度,将给出干扰优化后的拓扑图的网络干扰度与原始拓扑图 本文通过在仿真半台 OPNET10.5上建立模型并运行仿 的网络干扰度的比值分析(用a表示)。 真,定量分析干扰优化拓扑控制算法对无线自组网性能的影 本文通过对不同节点密度的 Ad hoc网络进行100次仿真响。根据上述拓扑图特性的仿真实验可知,节点数在50到170 来考察αA算法的拓扑结构性能,并与LIFE、 APL UDG三种之间,各种算法生成的拓扌图特性变化趋势稳定。本文取160个 拓扑结构进行比较。仿真场景为100×1000m,网络节点数节点随机分布在1000m×1000m的二维区域中,仿真场景设 从50递增到170,节点最大传输半径R为250m。 置如下:每个节点传播损耗模型使用自由空间模型,使用OdB 图4给出了不同算法的拓扑结构特性比较。如图4(a)、增益的全向天线,天线高度为1.5m,接收阈值为-80dBm,节 (b)所示,IIFF、AP、QIA算法生成的拓扑结构所具有的平均点初始最大发射功率为0.0064W(此时每个节点传输半径为 节点度在各种节点密度下都比较稳定,且节点度数比较小,说250m)。每个节点在链路层和网络层分别使用基于80211标 明了该算法构建的拓扑图是度有界的。同时随着节点密度增准的MAC协议和DSR路由协议。随机选择50个源节点,数 加,与原始拓扑图相比,LIFE、API、QA三种控制算法都有效据包的大小为1K比特,每个源节点产生分组速率(单位为 地缩减了节点半径,降低了相邻节点间干扰。 packets,/s)从0.2到2,发送间隔时间服从泊松分布。仿真时间 通过图4(c)可知,同UDG相比,LIFE、API、OIA三种算法为500s。仿真中,根据节点最大功率构建的初始拓扑结构(简 生成的拓扑结构都降低了网终平均链路干扰,优化了网络局称UDG)和不同拓扑控制算法(LIFE、API和QIA)生成的拓扑 部干扰。然而从图4d)可以看出,当从网络全局角度考察时,结构设置每个节点的发射功率。 由于LIFE算法生成的拓扑子结构中路径长度与准瓶颈节点的 仿真结果发现,对于每一个拓扑结构,随着数据流数量的 增加,导致网络干扰度加剧,图4(d)中表现为α值增加,说明增加和发包速率的增加,网络的传输性能表现出逐渐下降的 了原始拓扑结构经过LIFE拓扑控制优化反而加了网络全局趋势。从图5中可以看出,相比于另外两种干扰优化拓扑控制 干扰。按照网络路径干扰最小化思想设计的AP算法构造的算法LIFE、API,QA算法显示了良好的性能。 66 2011,47(24) Computer Engineering and Applications计算机工程与应用 的网络干扰度量模型的有效性。QIA算法由于采用了准瓶颈 E UDG LIFE 节点优化策略,构造了具有较小网络千扰的拓扑结构,相比于 70 API 60 -OIA 其他干扰优化拓扑控制算法,进一步提升了网络传输性能。 40 资30 5结束语 10 设计了一种基于准瓶颈节点的干扰优化拓扑控制算 12030405060708090100 网络负载( packets-) 法——QIAε仿真结果表明,QIA算法在保证网络连通性的前 (a)网络吞吐率 提下,构造了具有较小网络干扰的拓扑结构,相比经典干扰优 9000 3+UDG 化拓扑控制算法,网络吞吐率提高了约10%~30%。 7000 LIFE 由丁网络干扰与网络负载紧密相关,因此仅基丁拓扑结 a.6000AP P5000-QIA 构进行网络干扰优化还不能充分提升网络性能。在下一步的 工作中,将研究网终负载状态感知的自适应拓扑控制技术。 ;2000 1000 102030405060708090100 参考文献 网络负载/( packets.s-") [1] Goldsmith A J, Wicker S B Design challenges for energy- (b)重传数据包 constrained Ad Hoc wireless networks[JEEE Wireless CoIll UDG munications. 2002.9(4): 8-27 50 LIFE AP [2]沈中,常义林,崔灿,等.一种建立可白维护且具有最小能量特性的 QIA 无线网络的分布式拓扑控制算法门J计算机学报,2007,30(4) 签20 [3]张信明,刘涼,代仕芳,等移动 Ad hoc网络通信量相关干扰感知 路由协议[软件学报,209,20(10):2721-2728 102030405060708090100 网络负载( packets:s-) [4] Moscibroda T, Wattenhofer R, Zollinger A Topology control meets (c)网络延迟 SINR: the scheduling complexity of arbitrary topologies[C]iInter 图5网络性能 national Symposium on Mobile Ad Iloc Networking&Computing 2006:310-321 当网络负载较低时,网络中信道碰撞概率较低,路由稳[5LiN, Hou j c, Sha L Design and analysis of an MST-based to 定,因此此时网络性能较稳定,有无拓扑控制对网络性能影响 pology control algorithm[JJ. IEEE Transactions on Wirclcss Com 不大。但是,由于LIFE算法形成的拓扑结构过于稀疏,增加了 munications,2005,4(3):1195-1206 网络中的路径长度与网络准瓶颈节点个数,使得网终中路径[6]IiI.F, Halpern J Y, Bahl p,eta! a cone-based distributed 多样性受限,流汇聚现象较严重,导致网络干扰加剧,网络吞 opology-control algorithm for wireless multi-hop networks[J] 吐率下降。随着网终负载増加,网络中信道碰撞概率增加,使 IEEE/ACM Transactions on Networking, 2005,13(1):147-159. 得DSR路由协议不断进行路由重新发现过程,增加了大量路7 Blough D M, Leoncini m, Resta g.ea. The K-neigh protocol 由开销,占用了元线信道带宽,导致网络吞叶率急剧下降。基 for symmetric topology control in Ad Hoc networks[C]/Proc of 于网络路径干扰优化的API算法,由于其在减小网络局部干扰 ACM MObiHoc Anapolis, US.A: ACM Press, 2003: 145-152 的前提下保证了网络中路径干扰的最小化,在一定程度上提 18] Burkhart M, Rickenbach P V, Wattenhofer R, et al. Does topology 高了空间复用度,提升了网络吞吐率。同AP相比,QIA算法 control reduce interference[C]//Proceedings of the ACM Interna 运行了准瓶颈节点优化策略,在一定程度上优化了因稀疏化 lional SyImposiuin on Mobile Ad Hoc Networking and Comput- ing.NY, USA: ACM, 2004: 9-19 网络带来的路径多样性受限与流汇聚现象。同LIFE算法相 [9] Johansson T, Carr-Motyckov L Reducing interference in ad hoc 比,网络吞吐率提高了约30%,同API算法相比,网络不叶率提 networks through topology control[C]/Proceedings of 3rd ACM 高了约10%。 Joint Workshop on Foundations of Mobile Computing(DIALM 对比图4(d)与图5,可发现QIA、API、LIFE三种拓扑结构 POMC), Cologne, Germany, 2005: 17-23 的干扰因子呈递增趋势,说明这三种拓扑结构的网络度为递卩10]田乐,谢东亮,韩冰,等.无线传感器网络中瓶颈节点的研究冂软 増趋势,而其对应的网终吞叶率呈递减趋势,验证了本文所提 件学报,2006,17(4):830-837

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐