论文研究 随机部署的无线传感器网络的负载平衡.pdf

从结构的角度来研究在大规模随机部署时所形成的无线传感器网络的数据流负载平衡。通过统计分析邻居节点数目来分析其对无线传感器网络的数据流负载平衡的影响，发现在大规模随机部署时节点的邻居节点数目近似服从正态分布，其成因在于边缘效应。仿真实验发现节点通信半径的增大比部署密度的增大更不利于负载平衡。l8014,50(23)Computer Engineering and Applications计算机工程与应用期望为0.35D(X)=1.96D(X)-9x0.25D(X)-25方差为:D(r=ELX-E(X)(4)0.1032方差与负载平衡方差用来度量随机变量和其数学期望之问的偏离程度。D(X)小,表示集中;D(X)大,表示分散。246810121416邻居节点数目性质方差D(X)越小,X的分布就越集中图1正态分布密度曲线比较小意图证明当D(X)=0,若E表示任意小,则P(X->e)≥033四种情况的分析(5)331四种情况根据切比雪夫不等式有k/≥e)<本文对4种情况进行了讨论,分别是节点稀疏时小(6)的通信半径,节点稀疏时大的通信半径,节点稠密时小因此可见方差D(X)越小,X的分布就越集中。的通信半径,节点稠密时大的通信半径。节点稀疏时部署的节点数为100,节点通信半径为25和75。节点稠密随着节点数目的增加和通信距离的增大正态曲线吋部署的节点数为300.节点通信半径为25和75。呈现扁平化趋势。σ越小表明节点的邻居节点数目集(1)节点稀疏,小的通信半径,如图2。屮,σ越大表明节点的邻居节点数目分散。从图1可见(2)节点稀疏,大的通信半径,如图3。D(X)对正态曲线的影响:σ越小,正态曲线越陡峭;σ(3)节点密集,小的通信半径,如图4越大,正态曲线越扁平。扁平化意味着负载分化越严(4)节点密集,大的通信半径,如图5。重,正态曲线越陡峭表示WSN负载较平衡图2和图4显示网络中含有邻居节点数为0的节通过以上的分析可知减小D(X)可以提高WSN负点,表明这时网络是不连通的。连通是首要问题,连通载平衡。本文用 MATLAB仿真来验证WSN负载平衡之后的负载平衡问题才具有意义。邻居节点数为0的问题相关结论。节点数目随着部署节点的增多或者节点通信半径的增101234567891011邻居节点数日邻居节点数日图2N-100,R-25图3N-100,R-75来150253035邻居节点数目邻居节点数日图4N=300.R=25图5N=300,R=75辛强伟,房鼎益:随机部署的无线传感器网络的负载平衡2014,50(23)19大而减少,从而网络连通状况得到改善。随着N的增大,D(X)的变化是非线性的。33.2四种情況的比较用△k来表示WSN中节点最大度和最小度的差值,即图6~图9是将图2~图5的正态数据写入正态分布△k=km-k密度曲线以进行比较。图6和图7是节点的通信半径增其中k≥1。大至3倍。图8和图9是随机部署节点的密度增大至3倍。通过50次实验,数据是50次实验的平均值,取至小D(X)增大,会使分散程度加重,即会使Δk增大,因数点后两位。而D(X)增大不利于WSN随机部署情况下的负载平衡。(1)节点稀疏时通信半径3倍时的关系陌着N增大或者R增大,边缘效应越明显,从而使N=100时,R=75是R=25的E(X)的644倍,D(x)Dx)增大,即邻居节点数目的分布随着节点数目的增的767倍大或者逦信半径的增大而分散程度加重。E(X)的变化(2)节点稠密时通信半径3倍时的关系:是线性的,D(X)的变化是非线性的,当N增大或者RN=300时,R=75是R=25的E(X)的7.96倍,增大时wSN的负拔不平衡非线性增大。通过仿真实验D(X)的16.16倍。发现:同样的倍数关系的增长,节点通信半径的增大比(3)小的通信半径节点密度3倍时的关系节点数目的增大造成的邻居节点数目的分化作用要明R=25时,N=300是N=100的E(X)的2.59倍显得多,通信半径的增大更易造成WSN随机部署情况D(X)的2.33倍下的负载不平衡(4)大的通信半径节点密度3倍时的关系:R=75时,N=300是N=100的E(X)的3.19倍34进一步的讨论D(X)的492倍从二维平面到三维立体空间的推广有利于更贴近F(X)的变化实际情况。在三维空间V中,节点的通信范围是以坐标E(ax +D=E(X)+b(7)(xy,)为球心、以R为半径的圆球。若点q∈,设覆EG(X)+O(]=E[C(X)]+E[O()(8)盖度为W,覆盖度指覆盖∫点q的节点数目,则在三维随着N的增大,E(X)的变化是线性的。空间V中的覆盖为D(X)的变化Vi 8(g)da(12)D(ax +b)=a D(其中g(q)0.W<1DOX)=FLX-E(X](10W≥10.450.35N=300.R=25N=100,R=75N=300,R=750.300.150.002030邻居节点数目邻居节点数目图6N=100,R=25和R=75比较图7N=300,R=25和R=75比较]45M-100,R-25N=100,R=75N=300,R=2510.14N-300,R0.040.0505101520邻居节点数日邻居节点数日图00和N=300比较图9R=75,N=100和N=300比较20014,50(23)Computer Engineering and Applications计算机工程与应用在WSN的随机部署中,如山地起伏不平的地形、树参考文献:木的遮挡都会引起节点间通信距离以及无线信号空间1 Xiong Shuguang, Li jianzhong,LiMo, et al. Multiple传播损耗的増大。在二维平面上两节点的位置分别为task scheduling for low-duty-cycled wireless sensor net(x1y)、(x,y则两节点问的距离为works[c]/Proc of IEEE INFOCOM, 2011: 1323-1331D)=、(x2-x)+(y,-y)(13)[2 Cheng T E, Ruzcna B Congestion control and fairnessfor many-to-one routing in sensor networks[C] Proc of在三维立体空间两节点的位置分别为(x,y,z)、ACM SENSYS. 2004:148-161(x,y,2)则两节点间的距离为[3 Zhao Miao, Yang Yuanyuan. A framework for mobile dataD=、(x-x)+(,-y)+(2-2)(14)gathering with load balanced clustering and MIMOuploading[ C //Proc of IEEE INFOCOM, 2011: 2759-2767距离的变化影响到了无线信号的传播,无线信号空[4 Liu Yunhao. He Yuan, Li Mo, et al. Does wireless sensor间RSSI理论值为:network scale? a measurement study on green orbs[c]/S=101g=-10kg1C2P(15)Proc of ieee infocom, 2011: 873-881[5] Zhou Yangfan, Michael R L PORT: a price-oriented reliG为接收机天线增谧,G为发射机天线增谧。无线信ablc transport protocol for wireless sensor nctworks[C]号在空间传播中的损耗为Proc of Ieee issre. 2005: 117-126o=3244+20lgD+201gf(16) [6] Rahul C S, Jan M REnergy aware routing for low energyJoss为传输损耗,D为距离,f为工作频率。距离的增ad hoc sensor networks[C]pRoc of IEFF WCNC, 2002大,会使无线信号在空间传播中的损耗最大,并且RSSI350-355会减小。此外在实际情况中三维立体空间往往存在障] Chen T s, Tsai h w, Chu c P Gathering load balanced碍物的遮挡,比如树木的遮挡,无线信号在空间传播中trcc protocol for wireless sensor nctworks[C]/Proc of的损耗进一步增大,如果诸如物体遮挡等因素的影响表IEEE SENSORNETS. 2006: 8-13示为PL,则[8 Hull B, Jamiwson K, Balakrishnan H Bandwidth manageLOss=3244+20 1g d+201gf+PL(17)ment in wireless sensor networks[C]/Proc of ACMSENSYS,2003:306-307维空间可以投影到二维平面,假设三维空间中的点坐标为(a,a,a)若采用正交投影的方法将该点投[9 Luo Jun, He Ying. GeoQuorum: load balancing and energyefficient data access in wireless sensor networks[C]!影到二维平面,假设其在二维平面上的坐标为(b,b),则Proc of IEEE INFOCOM, 2011: 616-620[10] Yu Xiaokang, Ban XZeng Wei, et al. Sphericalb=t +u a(18)representation and polyhedron routing for load balancing其中向量t为偏移量,向量u为缩放因子。用矩阵表示为:in wireless sensor networks[C/proc of IEEE INFOCOM0(19) [11] Tijs V D, Koen L.An adaptive energy-efficient MAC protocol for wireless sensor networks[C]/Proc o因此采用正交投影的方法影响二维平面完全反映SENSYS,2003:171-180维空间的因素是偏移量和缩放因子,但二维平面还是[12] Rahim K, Riadh D, Andre-Luc B. Load balancing tech-可以在一定程度上反映三维立体的特点:故对于在二niques for lifetime maximizing in wireless sensor net维平面得出的结果,在三维空间可以得到与维平面类works[J].Ad Hoc Networks, 2013, 11(8): 2172-2186似的结论。[13] He Jing, Ji Shouling, Pan Yi, et al. Approximation algorithms for load-balanced virtual backbone constructionin wireless sensor networks[J].Theoretical Computer Sci4结论ence,2013,507:2-16.本文在不考虑具体的调度和路出算法的情况下,从[14] Anju S, Kingsly S RA secured load balanced clustcring结构的角度来研究节点随机部署且Sink位置仟意选取algorithm for wireless sensor network[J]. International时wSN的负载平衡,以便明晰在随机部署时所形成的Journal of research in Computer and Communication结构对WSN负载平衡的影响。通过分析发现边缘效应Technology,2014,3(4):517-520对随机部署有着重要影响。仿真发现随机部署时邻居15] Chatterjee p,DasN. Coverage constrained non- uniform节点数目近似于正态分布,且部署密度的增大比节点通信node deployment in wireless sensor networks for load半径的增大更有利于随机部署情况卜WSN的负载平衡。balancing[C]/Proc of IEEE AIMoC, 2014