随机部署的无线传感器网络的负载平衡

辛强伟，房鼎益

西北大学 信息科学与技术学院，西安 710127

随机部署的无线传感器网络的负载平衡

辛强伟，房鼎益

西北大学 信息科学与技术学院，西安 710127

1 引言

无线传感器网络（Wireless Sensor Networks，WSN）的节点处理能力有限，当数据量较大时，单个节点或者单一路径无法承担负载，因而需要WSN具有良好的负载平衡。在一些实际应用中出现了对少数节点的过度使用和依赖，而大多数节点是空闲状态，这种状况容易导致拥塞。此外，节点自身既感知数据，又要作为路由中继，由于距离Sink近的节点转发的数据量多于距离Sink远的节点，故拥塞较易出现在Sink附近。实现负载平衡有利于WSN减轻网络拥塞、降低丢包率以及增加网络生存时间。

关于负载平衡，文献[1]提出了两种有效的安排算法以达到负载平衡，设计了相应的协议。文献[2]提出基于子节点数目的传输调度方法，以确保每个节点发送到Sink的数据量相同。文献[3]中当每个簇不多于两个簇头时，提出的方法可以显著减少最大发送节点数目以及平均发送节点数目。文献[4]指出很少的一部分节点承担整个WSN的大部分通信量，部分节点由于邻居节点较多而承担了过大负载。将数据流均衡地划分给多条链路以实现多路径传输是一种实现负载平衡的有效方法。文献[5]运用多路径的路由方式，选择链路质量较好的路径以减少使用链路质量不好的路径。文献[6]运用多路径以达到负载均衡，具体方法是根据节点的能量以不同的概率选择路径，从而使能耗均衡。文献[7]提出了负载平衡树算法，将数据流均衡地分配给路由树的不同分支。对于Sink位置的优化选择，需要其附近节点具备多路径的分流条件。文献[8]提出部署多个Sink以分散数据量，从而避免在Sink周围出现过热的节点。本文研究节点随机部署这种情况，Sink位置在节点部署区域之内或周边的任意位置。

另外还有一些别的方法：文献[9]引入几何法定人数系统来体现内网数据存储的思想，系统可以较好改善负载平衡并可保持有竞争力的能量效率。文献[10]把节点嵌入3维凸多面体，用离散流开发了一个分布式算法完成嵌入，采用贪婪路由达到负载平衡。文献[11]指出节点的部署必须拥有能够处理最高网络负载的活动时间。文献[12]将负载平衡和功率控制结合起来，以使节点能耗均衡，从而最大化网络生存时间。文献[13]建立虚拟骨干网，将连通支配集的大小和负载平衡同时考虑。文献[14]提出了优化分簇来避免簇规模过大而导致负载不平衡，从而平衡能耗并提升网络生存时间。文献[15]在减少总的部署节点的前提下提出了新的算法以实现负载平衡。上述工作没有从结构的角度研究在随机部署节点时的负载平衡，由于WSN随机部署的环境复杂多样，如山地丛林等野外环境，繁复的路由算法和复杂的功率控制算法的作用在这样的环境下往往得不到有效的发挥。采用增大节点密度和统一变化节点通信半径这样的基础方法反而更易适应WSN随机部署的复杂多样的环境。然而增大节点密度和统一变化节点通信半径对于随机部署情况下负载平衡的具体影响以及两者的区别，尚未得到明确研究。且以往关于负载平衡的研究的前提是已经确定了Sink的位置，而本文的前提是Sink位置不确定，即Sink可位于任意位置。

本文不考虑具体的路由和调度算法，对节点随机部署在一区域内所形成的结构进行统计分析，从结构方面研究负载平衡。这一研究可以为将节点随机部署在一区域内且Sink位置可任意选取的WSN的负载平衡的更为科学的路由和调度算法的设计提供参考。

2 节点随机部署的特点分析

2.1 相关符号及定义

N：节点数目。

R：节点通信半径。

k：度，表示邻居节点的数目。

S：部署区域的面积。

d：部署节点的密度。

L：负载。

定义1（负载）负载L为在时间间隔T内节点转发数据包以及发送自身数据包的总和。

定义2（同级节点）到Sink跳数相同的节点。

定义3（负载平衡）假设WSN的节点数量为N，每个节点自身产生的数据量相同，通过多跳的方式传输数据，若距Sink某相同跳数的同级节点有h个，L1，L2，…，Lh表示这h个节点的负载，负载平衡即L1≈L2≈…≈Lh。

2.2 随机大规模部署带来的均匀化趋势

假设把部署区域划分为m个子区域，即S=S1+ S2+…+Sm，且每个子区域的面积都为S/m，因为是随机部署，每个子区域在每随机部署1个节点时的概率都是相同的，假定概率为P(Xi)，d=N/S，每部署1个节点都是独立的，可用一组相互独立随机变量 X1，X2，…，XN表示，则当 N→∞，ds1≈ds2≈…≈dsm，这说明随机大规模部署会带来节点分布的均匀化趋势。

2.3 边缘效应

由于边界的存在，靠近边界和远离边界的传感节点的覆盖面积是不同的。以典型的矩形区域为例，一个节点覆盖区域为πR2。如果是随机部署在边缘上的节点，则其覆盖区域为。如果是随机部署在四个顶点上的节点，则其覆盖区域为。

假定节点部署的位置距离边缘的距离为e，若0≤ e＜R，则其覆盖面积为；若 e≥R ，则其覆盖面积为πR2。因此节点的位置距离边缘的距离在R以内，其邻居节点数目以较大概率为节点的位置距离边缘的距离在R以外的倍。

因此，随机部署使得节点的分布呈现均匀化趋势，但边缘效应导致了邻居节点数目分布的不均匀。

3 节点随机部署情况下的负载平衡

3.1 节点随机部署时所具有的规律

本文采用Matlab模拟在一个500×500的区域随机部署节点。仿真发现随机部署传感节点在一定区域里的WSN的邻居节点数目的分布近似服从正态分布。

根据正态分布曲线的性质，在[μ-σ，μ+σ]区间的邻居节点数有68.25%；在 [μ-2σ，μ+2σ]区间的邻居节点数有85.45%；在 [μ-3σ，μ+3σ]区间的邻居节点数有99.73%；而邻居节点数在(μ±3σ)范围以外的不到0.3%。

假设H0为邻居节点数目服从正态分布；H1为邻居节点数目不服从正态分布。Xj表示实验中得到的邻居节点数目，实验中得到μ和σ。

接受假设H0，即大规模随机部署传感节点在一定区域里的WSN的邻居节点数目的分布近似服从正态分布。

令 X表示邻居节点的数目，正态分布的密度函数是：

期望为：

3.2 方差与负载平衡

方差用来度量随机变量和其数学期望之间的偏离程度。D(X)小，表示集中；D(X)大，表示分散。

性质方差D(X)越小，X的分布就越集中。

证明当D(X)=0，若ε表示任意小，则

根据切比雪夫不等式有：

因此可见方差D(X)越小，X的分布就越集中。

随着节点数目的增加和通信距离的增大正态曲线呈现扁平化趋势。σ越小表明节点的邻居节点数目集中，σ越大表明节点的邻居节点数目分散。从图1可见D(X)对正态曲线的影响：σ越小，正态曲线越陡峭；σ越大，正态曲线越扁平。扁平化意味着负载分化越严重，正态曲线越陡峭表示WSN负载较平衡。

通过以上的分析可知减小D(X)可以提高WSN负载平衡。本文用MATLAB仿真来验证WSN负载平衡问题相关结论。

图1 正态分布密度曲线比较示意图

3.3 四种情况的分析

3.3.1 四种情况

本文对4种情况进行了讨论，分别是节点稀疏时小的通信半径，节点稀疏时大的通信半径，节点稠密时小的通信半径，节点稠密时大的通信半径。节点稀疏时部署的节点数为100，节点通信半径为25和75。节点稠密时部署的节点数为300，节点通信半径为25和75。

（1）节点稀疏，小的通信半径，如图2。

（2）节点稀疏，大的通信半径，如图3。

（3）节点密集，小的通信半径，如图4。

（4）节点密集，大的通信半径，如图5。

图2和图4显示网络中含有邻居节点数为0的节点，表明这时网络是不连通的。连通是首要问题，连通之后的负载平衡问题才具有意义。邻居节点数为0的节点数目随着部署节点的增多或者节点通信半径的增大而减少，从而网络连通状况得到改善。

图2 N=100，R=25

图3 N=100，R=75

图4 N=300，R=25

图5 N=300，R=75

3.3.2 四种情况的比较

图6～图9是将图2～图5的正态数据写入正态分布密度曲线以进行比较。图6和图7是节点的通信半径增大至3倍。图8和图9是随机部署节点的密度增大至3倍。

通过50次实验，数据是50次实验的平均值，取至小数点后两位。

（1）节点稀疏时通信半径3倍时的关系：

N=100时，R=75是R=25的E(X)的6.44倍，D(X)的7.67倍。

（2）节点稠密时通信半径3倍时的关系：

N=300时，R=75是 R=25的 E(X)的7.96倍，D(X)的16.16倍。

（3）小的通信半径节点密度3倍时的关系：

R=25时，N=300是 N=100的 E(X)的2.59倍，D(X)的2.33倍。

（4）大的通信半径节点密度3倍时的关系：

R=75时，N=300是 N=100的 E(X)的3.19倍，D(X)的4.92倍。

E(X)的变化：

图6 N=100，R=25和R=75比较

图7 N=300，R=25和R=75比较

图8 R=25，N=100和N=300比较

随着N的增大，D(X)的变化是非线性的。

用Δk来表示WSN中节点最大度和最小度的差值，即

其中 kmin≥1。

D(X)增大，会使分散程度加重，即会使Δk增大，因而D(X)增大不利于WSN随机部署情况下的负载平衡。

随着N增大或者R增大，边缘效应越明显，从而使D(X)增大，即邻居节点数目的分布随着节点数目的增大或者通信半径的增大而分散程度加重。E(X)的变化是线性的，D(X)的变化是非线性的，当N增大或者R增大时WSN的负载不平衡非线性增大。通过仿真实验发现：同样的倍数关系的增长，节点通信半径的增大比节点数目的增大造成的邻居节点数目的分化作用要明显得多，通信半径的增大更易造成WSN随机部署情况下的负载不平衡。

3.4 进一步的讨论

从二维平面到三维立体空间的推广有利于更贴近实际情况。在三维空间V中，节点的通信范围是以坐标(x，y，z)为球心、以 R为半径的圆球。若点 q∈V，设覆盖度为W，覆盖度指覆盖了点q的节点数目，则在三维空间V中的覆盖为：

图9 R=75，N=100和N=300比较

Gt为接收机天线增益，Gr为发射机天线增益。无线信号在空间传播中的损耗为：

Loss为传输损耗，D为距离，f为工作频率。距离的增大，会使无线信号在空间传播中的损耗最大，并且RSSI会减小。此外在实际情况中三维立体空间往往存在障碍物的遮挡，比如树木的遮挡，无线信号在空间传播中的损耗进一步增大，如果诸如物体遮挡等因素的影响表示为 PL，则

三维空间可以投影到二维平面，假设三维空间中的一点坐标为(ax，ay，az)，若采用正交投影的方法将该点投影到二维平面，假设其在二维平面上的坐标为(bx，by)，则

在WSN的随机部署中，如山地起伏不平的地形、树木的遮挡都会引起节点间通信距离以及无线信号空间传播损耗的增大。在二维平面上两节点的位置分别为(xi，yi)、(xj，yj)，则两节点间的距离为：

在三维立体空间两节点的位置分别为(xi，yi，zi)、(xj，yj，zj)，则两节点间的距离为：

距离的变化影响到了无线信号的传播，无线信号空间RSSI理论值为：

其中向量t为偏移量，向量u为缩放因子。用矩阵表示为：

因此采用正交投影的方法影响二维平面完全反映三维空间的因素是偏移量和缩放因子，但二维平面还是可以在一定程度上反映三维立体的特点。故对于在二维平面得出的结果，在三维空间可以得到与二维平面类似的结论。

4 结论

本文在不考虑具体的调度和路由算法的情况下，从结构的角度来研究节点随机部署且Sink位置任意选取时WSN的负载平衡，以便明晰在随机部署时所形成的结构对WSN负载平衡的影响。通过分析发现边缘效应对随机部署有着重要影响。仿真发现随机部署时邻居节点数目近似于正态分布，且部署密度的增大比节点通信半径的增大更有利于随机部署情况下WSN的负载平衡。

[1]Xiong Shuguang，Li Jianzhong，Li Mo，et al.Multiple task scheduling for low-duty-cycled wireless sensor networks[C]//Proc of IEEE INFOCOM，2011：1323-1331.

[2]Cheng T E，Ruzena B.Congestion control and fairness for many-to-one routing in sensor networks[C]//Proc of ACM SENSYS，2004：148-161.

[3]Zhao Miao，Yang Yuanyuan.A framework for mobile data gathering with load balanced clustering and MIMO uploading[C]//Proc of IEEE INFOCOM，2011：2759-2767.

[4]Liu Yunhao，He Yuan，Li Mo，et al.Does wireless sensor network scale?a measurement study on green orbs[C]// Proc of IEEE INFOCOM，2011：873-881.

[5]Zhou Yangfan，Michael R L.PORT：a price-oriented reliable transport protocol for wireless sensor networks[C]// Proc of IEEE ISSRE，2005：117-126.

[6]Rahul C S，Jan M R.Energy aware routing for low energy ad hoc sensor networks[C]//Proc of IEEE WCNC，2002：350-355.

[7]Chen T S，Tsai H W，Chu C P.Gathering load balaneed treeprotocol for wireless sensor networks[C]//Procof IEEE SENSORNETS，2006：8-13.

[8]Hull B，Jamiwson K，Balakrishnan H.Bandwidth management in wireless sensor networks[C]//Proc of ACM SENSYS，2003：306-307.

[9]Luo Jun，He Ying.GeoQuorum：load balancing and energy efficientdata accessin wirelesssensornetworks[C]// Proc of IEEE INFOCOM，2011：616-620.

[10]Yu Xiaokang，Ban Xiaomeng，Zeng Wei，et al.Spherical representation and polyhedron routing for load balancing in wireless sensor networks[C]//Proc of IEEE INFOCOM，2011：621-625.

[11]Tijs V D，Koen L.An adaptive energy-efficient MAC protocol forwirelesssensornetworks[C]//Proc ofACM SENSYS，2003：171-180.

[12]Rahim K，Riadh D，André-Luc B.Load balancing techniques for lifetime maximizing in wireless sensor networks[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 construction in wireless sensor networks[J].Theoretical Computer Science，2013，507：2-16.

[14]Anju S，Kingsly S R.A secured load balanced clustering algorithm for wireless sensor network[J].International Journal of Research in Computer and Communication Technology，2014，3（4）：517-520.

[15]Chatterjee P，Das N.Coverage constrained non-uniform node deployment in wireless sensor networks for load balancing[C]//Proc of IEEE AIMoC，2014.

XIN Qiangwei,FANG Dingyi

School of Information Science and Technology,Northwest University,Xi’an 710127,China

This paper uses topology to study load balance of wireless sensor networks when sensors are deployed in large scale area randomly.Through the statistical analysis of the number of neighbor nodes of wireless sensor network to study the influence of data flow load balance,the number of neighbor node follows approximately normal distribution when sensors are deployed in large scale area randomly.Its origin lies in the edge effect.Simulation results show that the increase of node communication radius is more difficult to load balance than the increase of deployment density.

wireless sensor networks;load balance;deploy randomly;neighbor node

从结构的角度来研究在大规模随机部署时所形成的无线传感器网络的数据流负载平衡。通过统计分析邻居节点数目来分析其对无线传感器网络的数据流负载平衡的影响，发现在大规模随机部署时节点的邻居节点数目近似服从正态分布，其成因在于边缘效应。仿真实验发现节点通信半径的增大比部署密度的增大更不利于负载平衡。

无线传感器网络；负载平衡；随机部署；邻居节点

A

TP393

10.3778/j.issn.1002-8331.1404-0272

XIN Qiangwei,FANG Dingyi.Load balance of wireless sensor network with deploying randomly.Computer Engineering and Applications,2014,50（23）：16-20.

国家科技支撑项目（No.2013BAK01B02，No.2013BAK01B05）；国家自然科学基金（No.61070176，No.61202393）；陕西省科技厅国际合作项目（No.2013KW01-02）。

辛强伟（1980—），男，博士研究生，主要研究方向为无线传感器网络的容错和拓扑控制；房鼎益（1959—），男，通讯作者，教授，博士生导师，主要研究领域为无线传感器网络、软件安全和信息安全。E-mail：qiangweifendou@163.com

2014-04-17

2014-06-17

1002-8331（2014）23-0016-05

CNKI网络优先出版：2014-07-01,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0272.html