2014, Vol. 25
表 1(Table 1)
不可靠通信环境下无线传感器网络最小能耗广播算法
引用本文
程红举, 黄行波, XIONG Naixue. 不可靠通信环境下无线传感器网络最小能耗广播算法[J].软件学报,2014, 25(5): 1101-1112.http://www.jos.org.cn/1000-9825/4455.html 
CHENG Hong-Ju, HUANG Xing-Bo, XIONG Naixue. Minimum-Energy Broadcast Algorithm for Wireless Sensor Networks with Unreliable Communications[J]. Ruan Jian Xue Bao/ Journal of Software, 2014, 25(5): 1101-1112.http://www.jos.org.cn/1000-9825/4455.html
不可靠通信环境下无线传感器网络最小能耗广播算法
1 福州大学 数学与计算机科学学院, 福建 福州 350108;
2 School of Computer Science, Colorado Technical University, USA
2 School of Computer Science, Colorado Technical University, USA
摘要：在实际的通信环境中，由于噪声、报文冲突、信号衰减等因素的影响，无线传感器网络节点间信息交换往往是不可靠的.广播是无线传感器网络中广泛使用的操作，如何在不可靠通信环境下实现能量高效的广播算法，对提高整个无线传感器网络的性能具有重要的理论和应用价值.研究了不可靠通信环境下的无线传感器网络最小能耗广播问题，首先，分析了相邻节点之间最小能耗通信模型，并给出了保证节点接收概率不低于P*的最优发送半径；然后，讨论了多跳转发策略与节点位置信息之间的关系.在此基础上，提出了一种基于PSO的最小生成树广播算法，通过优化各节点的发送半径，在保证所有节点都能以不低于P*的概率接收到广播数据包的前提下，实现广播操作的总能耗最小.实验结果表明：所提出的广播算法不仅可使每一个节点的接收概率不小于P*，而且广播总能耗比改进后的BIP算法要小，具有较好的性能.
关键词：
无线传感器网络
最小能耗广播
粒子群优化
算法
不可靠通信环境
Minimum-Energy Broadcast Algorithm for Wireless Sensor Networks with Unreliable Communications
1 College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China;
2 School of Computer Science, Colorado Technical University, USA
2 School of Computer Science, Colorado Technical University, USA
Corresponding author:
Abstract: In the realistic communication environment, due to the noise, packet conflict, signal attenuation and other factors, information exchange is generally unreliable among nodes in the wireless sensor networks. Broadcast is a widely-used operation, and building an energy-efficient broadcast algorithm has important theoretical and application value in improving the performance of wireless sensor networks. This paper studies the minimum energy broadcast problem of wireless sensor networks with the unreliable communications. Firstly, it analyzes the minimum energy consumption of communication model between adjacent nodes and presents the optimal transmission radius that can guarantee the neighbor node to receive packets with probability no less than P*. Then, it discusses the relationship between multi-hop relay strategy and location information of nodes. It finally presents a PSO-based broadcast algorithm with minimum spanning tree, which can guarantee that all nodes in the network will receive packets with probability no less than P* and minimize the total energy consumption. The simulation results show that the presented broadcast algorithm can not only guarantee all nodes to receive packets with probability no less than P*, but also consume less energy and have better performance compared with the improved BIP algorithm.
Key words:
wireless sensor network
minimum-energy broadcast
particle swarm optimization
algorithm
unreliable communications
随着微电子技术、无线通信技术和传感技术的飞速发展,无线传感器网络(wireless sensor network,简称WSN)已经成为当今研究的热点.无线传感器网络由许多低成本、低能耗、易管理的无线传感器节点组成,这些节点共同协作完成网络通信,被广泛应用于军事侦察、环境监测、医疗诊断等领域.广播是无线传感器网络中一个必不可少的操作,可用于传递控制信息、重要数据与报警信号等,同时也是建立路由的重要手段.由于传感器节点通常由电池提供能量,能量有限且难以补充.如何实现能量高效的广播算法,对提高网络的性能、延长网络的生命周期具有重要的理论和应用价值.能量高效的广播算法最重要的衡量标准之一就是能耗最小,这已经被证实为NP困难的组合优化问题[1, 2].现有的广播算法往往基于通信可靠这一假设,即1个节点广播1次,位于其传输覆盖范围内的节点都能以概率1正确地接收到广播数据包,但在实际通信环境中,无线链路是不可靠的,节点只能以小于1的概率P正确地接收到广播数据包.如果P很小,就需要通过多次重传来保证广播数据包被正确地接收.当节点重传N次时,接收节点正确接收到数据包的概率为1-(1-P)N.理论上,我们无法确定一个具体的N值来保证节点能够以100%的概率接收到广播数据包.
粒子群优化(particle swarm optimization,简称PSO)算法是一种新的群智能优化算法[3].与其他进化算法相比,它最吸引人的特征是实现简单和更强的全局优化能力.PSO算法提出之后,引起了众多学者的极大关注,在短短几年内,就形成了一个研究热点并出现了许多的研究成果.大量实验结果也表明,PSO算法确实是一种有力的优化工具.为了解决不可靠环境下的最小能耗广播问题,本文提出了一种集中式的基于PSO的最小生成树广播算法.该算法不仅能够保证所有节点接收到广播数据包的概率不低于一个给定的值P*,而且广播总能耗最小.
本文第1节进行相关工作的比较.第2节介绍模型和基础工作.第3节详细介绍算法的具体构造过程.第4节是仿真结果及其分析.第5节对全文进行总结.
1 相关工作近几年来,关于无线传感器网络中广播的研究已有很多.最简单、直接的广播就是洪泛(flooding).它要求每个节点第1次接收到广播数据包后都进行重播,这会导致严重的广播风暴问题[4].针对洪泛引发的问题,文献[5]提出了动态概率广播算法,每个节点都设置了数据包计数器来评估其邻居节点密度情况:如果计数器值很大,表明邻居节点多,则相应地降低节点重传概率;否则增加重传概率,通过动态调整节点重传概率,有效地减缓了广播风暴.但是很难确定合适的重传概率值,使得所有节点接收到广播数据包的概率大,重传次数小.文献[6]提出了一种启发式广播算法BIP(broadcast incremental power).它以广播源节点为树根来构建一棵广播树,在构建的过程中,每次将一个未被覆盖的节点加入广播树,并且为此付出的能耗代价最小.文献[7]进一步优化了BIP算法,提出了有效的搜索算法r-shrink,通过对已经构建好的广播树的非叶子节点重新调度来减少广播总能耗.文献[8]使用模拟退火算法来构建最小能耗广播树.文献[9]提出了基于PSO的最小能耗广播算法.该算法能够找到最优或近似最优解.而在不可靠通信环境下如何提供可靠数据传输的研究,已经取得较好进展,如文献[10,11,12,13,14,15],分别就容错路由、传输容错、拓扑控制和网络编码等问题进行了分析,并且取得较好的效果.针对传输出错率高的物理层环境,文献[16]提出了双覆盖广播算法来保证网络的可靠性.它所选择的转发节点不仅能够覆盖所有2跳邻居节点,而且能够保证所有1跳邻居节点至少被2个转发节点覆盖.文献[17]提出了一种双发送半径机制,其中,一个半径用于构建广播树,另一个半径用于传输广播数据包.该算法首先构建广播树,然后根据广播能耗和覆盖率计算最佳发送半径,并让节点使用该半径进行通信.实验结果表明,该算法能够保证网络的平均覆盖率较高和能量的有效性,但是不能保证每个节点接收到广播数据包的概率满足人们的要求.文献[18]考虑到通信链路不可靠性等特点,引入网络编码和重传机制来保证可靠性,并采用基于链路质量的最小生成树来减少广播操作中的转发次数.文献[19]研究了在传输半径固定这一情况下,如何使用接收概率模型来统计所有节点的接收概率,并通过多次重传保证接收概率达到所希望的预期值.上述工作利用不同距离范围内节点具有不同的接收概率这种实际情况,提供了较好的研究思路,但并未考虑到节点传输半径可调这种情况.
本文的贡献是分析了相邻节点之间通信的最小能耗问题,给出了保证节点接收概率不低于P*的最优发送半径,以及多跳转发策略与节点位置信息之间的关系.在此基础上提出了基于PSO的最小生成树广播算法,通过优化各节点的发送半径,在保证所有节点都能以不低于P*的概率接收到广播数据包的前提下实现能耗最小.
2 模型与基础在详细描述算法之前,本节先介绍网络中用到的模型以及基础.
2.1 接收信号的概率模型和能耗模型无线通信中的信号传播与障碍物、反射面及散射体等各种环境因素有关,这使得在量化接收信号强度时存在不确定性.Stojmenovic等人[20]在阴影衰落模型的基础上进一步研究了接收方单一比特位的接收概率,并指出,在通信距离等于发送半径时,整个数据包的接收概率P(d)=0.5;然后,量化并给出了一般情况下接收方正确接收数据包的概率P(d)与通信距离d、路径损耗系数a之间的关系为
(1)
同时,Stojmenovic等人通过实验证实了上述概率模型的有效性:当L=120bits,aÎ[2,6],q=2时,通过该模型得到的接收概率与实际接收概率的误差在4%以内.
本文也采用该模型来量化接收方正确接收数据包的概率,其中,q=2,aÎ[2, 6].假设发送半径率d=R/d.从图 1可以看出:对任意的a值,当d=0.5时,P(d)=0;当d=1时,P(d)=0.5.也就是说,当发送半径和节点间的距离相等时,节点正确接收到数据包的概率是0.5;当节点间的距离大于或等于2倍的发送半径时,节点正确接收数据包的概率接近0.
 | Fig. 1 Reception probability vs. transmission radius ratio (d)图 1 接收概率和发送半径率(d)之间的关系 |
节点通信时需要消耗一定的能量,这里,我们分析节点广播一次消耗的能量模型如下所示:
E¢=kRa+m+b (2)
其中,k为正常数,R为发送半径,a是路径损耗系数,m表示信号处理消耗的能量,b表示其他节点监听该信号消耗的能量.本文模拟的是室外环境,且假定传感器节点之间的距离相对较大,那么能量消耗主要是路径损耗.为了简单化,我们忽略信号处理和监听消耗的能量,并取k=1.因此,节点广播一次的能耗模型可以简化如下:
E=Rα (3)
2.2 两个节点的情况分析网络通信中最简单、最基础的方式是点对点通信,由于无线通信是不可靠的,IEEE 802.11协议很难确定所需要的重传次数和最小能耗来保证数据包被正确接收.这里根据第2.1节中接收信号的概率模型,在满足接收方的接收概率不低于P*的前提下,分析点对点通信时发送半径与最小能耗之间的关系.
图 2描述了一个点对点通信的网络拓扑.
 | Fig. 2 A network with 2 nodes图 2 两个节点组成的一个网络 |
假设节点1有数据包要传输给节点2,为了使节点2正确地接收到数据包的概率不低于P*,需要分析节点1的发送半径应设置为多大才能使总能耗最小.为了便于研究,本文假设路径损耗系数a=4,发送半径率d=R/d.根据式(1)计算节点2的接收概率P(d),为使节点2的接收概率不低于P*,节点1至少需要重传N次,并使1-(1-P(d))N≥P*,即
(4)
如果R>d,根据公式(1)得到P(d)=1-0.5(d/R)2α,那么节点1重传N次消耗的能量为
(5)
如果R≤d<2R,根据公式(1)得到P(d)=0.5(2-d/R)2α,那么节点1重传N次消耗的能量为
(6)
为了保证节点1的传输能耗最小,本文对公式(5)和公式(6)进行分析,得出发送半径率d和要求的接收概率P*之间的变化关系,如图 3所示.
 | Fig. 3 Transmission radius ratio (d) vs. expected reception probability图 3 发送半径率(d)和要求的接收概率之间的关系 |
通过上面的分析可以得出如下结论:在点对点通信中,对于给定的要求接收概率P*,可以找到相应的发送半径率d,使得节点发送半径R=dd时,传输能耗最小.我们称该R为最优发送半径.
2.3 中继转发性能的分析一般认为:在无线多跳网络中,通过中继转发的方式比直接覆盖消耗的能量更小.然而事实并非总是如此,这与节点位置分布和当时的环境有很大的关系.为了便于研究,本文假设环境参数在有限范围内不会出现很大的变动,侧重于研究节点位置分布和最小传输能耗之间的关系.图 4列举了由3个节点组成的网络拓扑图,且节点都配备了全向天线,节点1要广播一个消息,使得两个目标节点2、节点3都能正确接收到该消息.假设节点1和节点2之间的距离为d12,节点1和节点3之间的距离为d13,节点2和节点3之间的距离为d23.
 | Fig. 4 A network with 3 nodes图 4 3个节点组成的一个网络 |
在该例子中,节点1可以有两种策略进行广播操作:
a) 节点1直接传输信息给节点2和节点3,此时能耗为
b) 节点1通过节点2作为中继节点,使节点3接收到数据包,此时能耗为
根据第2.2节的分析结果,对于给定的P*,都可以找到相应的d=R/d,使得最优发送半径为R=dd.
这里取R1=dd1,其中,d1为d12和d13之间的较大者,R12=dd12,R23=dd23.根据公式(1)计算出P(d11),P(d12),P(d23),根据公式(4)计算出N1,N12,N23.
通过对上述两种方式的分析,我们得出以下结论:
1) 当E>E¢,即
采用策略b)能耗小;
2) 当E<E¢,即
采用策略a)能耗小;
3) 当E=E¢,即
两种策略能耗相同.
为了便于理解,假设广播源节点1的坐标是(80,0),节点2的坐标为(0,0),路径损耗系数a=4,P=0.9.对节点3的位置分布和最小能耗之间的关系进行分析,其结果如图 5所示.
 | Fig. 5 Relationship between minimum energy consumption and nodes’ location图 5 节点位置和最小能耗之间的关系 |
当节点3分布在曲线的左边时,通过节点2中继转发消耗的总能量更小;当节点3分布在曲线上时,节点1直接传输信息给节点2和节点3与通过节点2中继转发消耗的总能量相同;当节点3分布在曲线右边时,节点1直接传输信息给节点2和节点3消耗的总能量更小.
通过上述分析可以得出如下结论:在无线多跳传感网络中,有时候通过中继转发消耗的能量小,有时候直接传输信息消耗的能量小,这与节点的位置分布有关.
3 集中式最小生成树广播算法因为实际通信环境中无线链路是不可靠的,所以传统的基于生成树的广播算法存在固有的缺陷.本文首先提出一种生成树优化机制,使得基于生成树的广播算法仍然适用,然后提出一种基于PSO的最小生成树广播算法.该算法不仅保证所有节点接收到广播数据包的概率不低于P*,而且保证实现广播操作的总能耗最小.
表 1列举出后面用到的重要符号.
|
Table 1 Notation of the symbols 表 1 符号说明 |
生成树优化机制是指对一棵已经构建好的生成树T,从第1层开始,逐层保证节点接收到广播数据包的概率不低于P*.对于T中的每一个非叶子节点,根据第2.2节中的结论,计算它们的最优发送半径,并且通过最小的重传次数保证它们的子节点满足接收概率不低于P*.
根据公式(1)可以发现,位于节点2倍发送半径范围内的节点都有一定的概率接收到广播数据包.如果一个节点位于多个节点的覆盖范围内,它就可能接收到多个节点的广播数据包.假设节点i的发送半径为Ri,节点j当前接收到广播数据包的概率为Pj,为使节点j的接收概率不低于P*,节点i的重传次数可以表示如下:
(7)
当节点i重传Ni次后,节点j的接收概率更新公式如下:
(8)
下面介绍生成树优化机制的具体实现过程,其伪代码见算法1.
算法1. 生成树优化机制.
输入:T,S,P*.
输出:优化后的广播树.
1. 标记源节点S,Pi=0,iÎ{V-S}.
2. 根据给定的P*计算最优半径对应的d.
3. 对于源节点S,根据其最远子节点k,计算发送半径Rs=ddsk.
3.1. 根据公式(1)计算P(dsk),根据公式(4)计算Ns,根据公式(5)或者公式(6)计算Es.
3.2. 当S重传Ns次以后,根据公式(8)更新所有节点的接收概率,如果存在节点的接收概率不低于P*,则标记该节点.
3.3. 将C(S)中的节点插入队列Q中;
4. 如果存在节点未被标记,则从队列Q中取出一个元素X;否则,跳转到步骤5.
4.1. 如果X是叶子节点,则跳转到步骤4.
4.2. 如果X的所有子节点都被标记,则跳转到步骤4;否则,
对于节点jÎC(X):
如果j没有被标记;
Rx=ddxj;
求一个最小的重传次数Nx,使得C(X)中所有节点接收概率不低于P*;
计算Ex=NxRx.
选择最小的Ex作为X的广播消耗的能量,及其对应的Rx作为发送半径,Nx作为重传次数.
4.3. X重传Nx次后,根据公式(8)更新所有节点的接收概率,如果存在节点接收概率不低于P*,标记该节点.
4.4. 将C(X)中的节点插入队列Q中.
5. 所有节点接收到广播数据包的概率都满足P*,结束.
为了更清楚地表达该优化机制,下面举一个例子予以说明.图 6是该例子对应的一棵生成树,节点1是广播源节点.所有节点的坐标由表 2给出.
 | Fig. 6 A spanning tree图 6 一棵生成树 |
|
|
Table 2 Coordinates of nodes 表 2 节点的坐标 |
假设a=4,P*=0.9.根据第2.2节中的公式,计算得出节点的最优发送半径率d=1.2228.首先考虑第1层节点1,其最远的子节点是节点3,那么节点1的最优发送半径R1=1.2228d13=3.4586.根据公式(4)计算节点1的最小重传次数为1,并广播1次.根据式(8)更新所有节点的接收概率,结果为表 3中Iteration 1这一列所对应的值.然后考虑第2层的节点2和节点3.对于节点2,若取发送半径R2=1.2228d25=2.7343,则至少需要重传10次才能使它的子节点4和节点5的接收概率不低于P*,此时,传输总能耗E=558.9650;若取发送半径R2=1.2228d24=3.6684,则重传1次就能使节点4和节点5的接收概率不低于P*,此时,传输总能耗E=181.0951.因此,为了使节点2的传输能耗最小,节点2的发送半径应取3.668 4.当节点2以半径3.668 4广播1次后,所有节点的接收概率如表 3中Iteration 2一列所示.同理,节点3计算其最优发送半径和最小重传次数,当节点3执行完相应的广播操作以后,所有节点的接收概率如表 3中Iteration 3一列所示.
|
|
Table 3 Reception probability of nodes at each iteration 表 3 每轮迭代中节点接收概率 |
通过表 3可以看出,原始的生成树经过优化机制优化后,所有节点的接收概率都大于0.9,这是因为节点间存在重叠覆盖.例如节点5,不仅有一定的概率接收到其父节点2的数据包,而且还可能接收到节点1和节点3的数据包,其接收概率是接收到所有包的概率的一个累积值.
3.2 基于PSO的最小生成树广播算法在文献[9]中,我们运用离散PSO来解决最小能耗广播问题,但那是基于无线通信是可靠的这一假设.本文提出基于PSO的最小生成树广播算法来解决不可靠通信环境下的最小能耗广播问题,称该算法为BR-PSO (best radius-PSO).
3.2.1 标准粒子群优化算法Kennedy等人受自然界中鸟群运动模型的启发,提出了一种新的基于种群的搜索算法——PSO.该算法的原理是:每个粒子都是一个备选的可行解,并以一定的速度在解空间中不断搜索.通过对环境的学习与适应,每个粒子根据自身以及同伴的飞行经验来动态地调整飞行速度和方向,并追随当前最优粒子向最优解方向靠近.粒子根据下面的公式来更新速度:
Vid =wVid +c1rand(×)(Pid -Xid)+c2rand(×)(Pgd -Xid),
其中,w是惯性因子,Xid是粒子当前位置,Pid是粒子搜索到的历史最佳位置,Pgd表示整个种群的历史最优位置即全局最优解,rand(×)表示[0, 1]之间的随机数,c1和c2是加速因子.在根据速度公式计算出速度后,粒子便根据下面的位置公式计算出下一次搜索的位置:Xid=Xid+Vid.
3.2.2 离散粒子群优化算法PSO算法最初用于解决连续优化问题,其研究主要集中于连续函数方面,其速度、加速度等变量都是连续的,它们的运算法则也是连续量的运算.然而,无线传感器网络中的广播问题对应的解空间是离散的.这里,我们采用离散的PSO算法来解决最小能耗广播问题.
(1) 编码
假设无线传感器网络是由n个传感器节点组成的,且每个节点都赋有一个ID标识号.本文使用节点ID号的排列编码表示广播问题的一个解(粒子).对于一个排列(粒子)t,其编码格式表示如下:
Xt=[x1,…,xn].
其中,xi表示节点i的ID号.在所有的排列中,广播源节点的ID号始终是在第1位.(2) 种群初始化
初始的种群是由随机的方法和确定的方法生成的.这里,确定的方法是指BIP算法.
(3) 更新公式
根据之前的分析,标准PSO算法中的速度和位置更新公式已不再适用.本文采用下面的更新公式:
Vid=wVidÅc1rand(×)(Pid-Xid)Åc2rand(×)(Pgd-Xid) (9)
Xid=XidÅVid (10)
其中,w,c1和c2都是[0, 1]之间的随机数,Vid表示一个交换序.对于一个排列Xt=[x1,…,xn],交换子操作SO(i,j)表示交换ID号xi和ID号xj.一个或更多的交换子操作组成一个交换序,交换序中交换子的顺序非常重要.联合操作符“Å”表示将几个交换序合并成一个交换序.例如,SS¢=SS1ÅSS2,表示交换序SS¢作用于排列Xt的效果等价于交换序SS1和SS2先后作用于Xt.对于操作符“-”,本文定义SS=X1-X2,表示交换序作用于排列X2后的结果是X1.这里,举一个简单的例子进行说明.假设有两个排列X1=[1, 2, 3, 4, 5]和X2=[2, 3, 1, 5, 4].因为X1(1)=X2(3)=1,所以第1个交换子是SO(1,3),根据X2=X2+SO(1,3)得到X2=[1, 3, 2, 5, 4].同理,第2个交换子操作是SO(2,3),根据X2=X2+ SO(2,3)得到X2=[1, 2, 3, 5, 4].相应地,第3个交换子是SO(4,5),作用于X2后得到X2=X1.最后,将所有交换子联合起来得到交换序SS=X1-X2=(SO(1,3),SO(2,3),SO(4,5)).
(4) 解码
对于一个排列(粒子),需要将它解码为一棵广播树,其伪代码由算法2给出.
算法2. 一个排列解码成一棵广播树.
1. 标记源节点,表示该节点已经加入广播树,并作为广播树的根节点.
2. 赋予源节点一定的发射功率,使它能够覆盖排列中的第2个节点.标记这个节点,并将其作为源节点的子节点加入广播树.
3. 检查其他节点,看是否被步骤2中的源节点覆盖,若是,则标记它们并加入广播树.
4. 选择排列中的第1个未标记的节点u,通过已经在广播树中的节点v将其加入广播树.并且,为了使u能被加入广播树,v节点消耗的能量最小.然后标记u,并检查其他未标记的节点是否能被v节点覆盖,若能,则标记它们并加入广播树.
5. 如果排列中还有没有标记的节点,则重复步骤4.
6. 结束.
(5) 适应值函数
当一个排列(粒子)被解码后,即意味着一棵广播树已经构建完成,对该广播树运用生成树优化机制,保证所有节点的接收概率都不低于P*.本文的目标是最小能耗广播,因此,采用广播树的总能耗表示适应值函数:
(11)
(6) 参数设置
合理的设置参数能够提高PSO算法的性能.本文采用下面的调整策略来设置参数w,c1和c2:
· w=(wmax-wmin)x(MaxIteration-CurIteration)/MaxIteration+wmin;
· c1=1.0-1.0xCurIteration/MaxIteration;
· c2=1.0-c1.
其中,wmax和wmin表示w可以取到的最大值和最小值.MaxIteration和CurIteration相应地表示最大的迭代次数和最小的迭代次数. 3.2.3 基于PSO的最小生成树广播算法本文使用BR-PSO算法来解决不可靠环境下的最小能耗广播问题.算法3给出了对应的伪代码.
算法3. BR-PSO.
输入:网络拓扑G=(V,L)和源节点SÎV.
输出:所有节点接收到广播数据包的概率不低于P*,且总能耗最小.
1. 初始化种群.
2. 把种群解码成对应的广播树,并对它们应用生成树优化机制.
3. 计算种群个体最佳Pid和全局最佳Pgd.
4. 如果满足终止条件,则转到步骤9.
5. 遍历每一个粒子:
5.1. 计算Pid -Xid.
5.2. 计算 Pgd-Xid.
5.3. 根据公式(9)计算速度Vid.
5.4. 根据公式(10)更新粒子位置Xid.
6. 将种群解码成对应的广播树,并对它们应用生成树优化机制.
7. 更新Pid和Pgd.
8. 如果终止条件满足,则跳转到步骤9;否则,跳转到步骤5.
9. 获得全局最优解Pgd.
4 仿真结果及其分析广播算法BIP是一种非常经典的最小能耗广播算法,已经得到学者的广泛认同,并经常作为比较对象来衡量其他广播算法的性能.但是,BIP算法基于可靠通信环境,即1个节点广播1次,位于其传输覆盖范围内的节点都能以概率1正确接收到广播数据包,这在不可靠通信环境中是很难实现的.为了让BIP算法同样适用于不可靠通信环境,本文对其进行了扩展.主要思想是:先利用BIP算法构建广播树,然后应用本文提出的生成树优化机制对该广播树进行优化,使所有节点的接收概率不低于P*,我们称扩展后的BIP算法为BR-BIP(best radius-BIP).
下面对BR-BIP算法和BR-PSO算法的性能进行实验仿真,并对结果进行比较,同时对算法的参数进行分析.本文使用MATLAB工具来仿真模拟相应的实验环境,在1000mx1000m的区域内随机生成节点数为nÎ[20,50, 75,100,150,200]的网络.假设所有节点都是固定不动,并且都配置有全向天线,节点的发送半径可调节.广播源节点是随机从网络中选择出来的,广播数据包大小也是固定的,路径损耗系数a=4.
图 7和图 8描述的是本文提出的BR-PSO算法与BR-BIP算法相比,在能耗方面提高的百分比.从图中可以看出:无论要求的接收概率和网络中节点数如何变化,BR-PSO算法在能耗方面都比BR-BIP算法有显著的改善,尤其是当节点数为20时,提高了30%以上.
 | Fig. 7 Energy consumption with expected reception probability P*图 7 能量消耗与要求的接收概率P*之间的关系 |
 | Fig. 8 Energy consumption with expected reception probability P*图 8 能量消耗与要求的接收概率P*之间的关系 |
图 9描述了BR-PSO算法消耗的能量随着要求的接收概率变化的情况.从图中可以看出:无论网络大小是20,50,75还是100个节点,在要求节点的接收概率变大时所消耗的能量也随之相应增加.
 | Fig. 9 Energy consumption with expected reception probability P*图 9 能量消耗与要求的接收概率P*之间的关系 |
图 10描述的是当P*=0.9时,网络中节点实际接收的概率随着网络大小变化的情况.从图中可以看出:对于各种大小的网络,BR-BIP算法和BR-PSO算法都能保证节点实际的接收概率在0.964以上.图 11描述的是在100个节点的网络中,节点实际接收的概率随着P*变化的情况.不难发现:BR-BIP算法和BR-PSO算法都能保证节点实际接收的概率比要求的接收概率P*要大.图 10和图 11表明:不管网络大小和所要求的接收概率P*如何变化,BR-BIP算法和BR-PSO算法都能保证节点的实际接收概率比要求的接收概率要大.
 | Fig. 10 Actual reception probability of nodes in case P*=0.9图 10 当 P*=0.9时,节点实际的接收概率 |
 | Fig. 11 Actual reception probability of nodes in case n=100图 11 当n=100 时,节点实际的接收概率 |
广播是无线传感器网络中的一个基础操作.能量高效的广播尤为重要.为了实现不可靠通信环境下的最小能耗广播,本文提出了一种基于PSO的最小生成树广播算法,通过优化网络中各节点的发送半径,在保证所有节点都能以不低于P*的概率接收到广播数据包的前提下实现能量最小化.模拟实验结果表明:本文提出的算法不仅能够保证所有节点的接收概率大于P*,而且总能耗最小,具有较好的性能.
参考文献
| [1] | Clementi AEF, Crescenzi P, Penna P, Rossi G, Vocca P. On the complexity of computing minimum energy consumption broadcast subgraphs. In: Ferreira A, Reichel H, eds. Proc. of the 18th Annual Symp. on Theoretical Aspects of Computer Science. Berlin, Heidelberg: Springer-Verlag, 2001.121-131 [doi: 10.1007/3-540-44693-1_11] . |
| [2] | Čagalj M, Hubaux JP, Enz C. Minimum-Energy broadcast in all-wireless networks: NP-Completeness and distribution issues. In: Proc. of the 8th Annual Int’l Conf. on Mobile Computing and Networking. New York: ACM Press, 2002.172-182 [doi: 10.1145/ 570645.570667]. |
| [3] | Eberhart RC, Kennedy J. A new optimizer using particles swam theory. In: Proc. of the 6th Int’l Symp. on Micro Machine and Human Science. Boston: Academic Press, 1995.39-43 [doi: 10.1109/MHS.1995.494215]. |
| [4] | Tseng YC, Ni SY, Chen JP. The broadcast storm problem in a mobile ad hoc network.Wireless Network, 2002,8(2):153-167 [doi: 10.1145/313451.313525]. |
| [5] | Zhang Q, Agrawal DP. Dynamic probabilistic broadcasting in mobile ad hoc networks. In: Proc. of the IEEE Vehicular Technology Conf. (VTC). Piscataway: IEEE Press, 2003.2860-2864 [doi: 10.1109/VETECF.2003.1286132]. |
| [6] | Wieselthier JE, Nguyen GD, Ephremides A. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE Press, 2000.585-594 [doi: 10.1109/INFCOM.2000.832232]. |
| [7] | Das AK, Marks RJ, El-Sharkawi M, Arabshahi P, Gray A. R-Shrink: A heuristic for improving minimum power broadcast trees in wireless networks. In: Proc. of the IEEE GLOBECOM. Piscataway: IEEE Press, 2003.523-527 [doi:10.1109/GLOCOM.2003.125 8292]. |
| [8] | Montemanni R, Gambardella LM, Das AK. The minimum power broadcast problem in wireless networks: A simulated annealing approach. In: Proc. of the Wireless Communications and Networking Conf. Piscataway: IEEE Press, 2005.2057-2062 [doi: 10. 1109/WCNC.2005.1424835]. |
| [9] | Xiong NX, Huang XB, Cheng HJ, Wan Z. Energy-Efficient algorithm for broadcasting in ad hoc wireless sensor networks.Sensors, 2013,13(4):4922-4946 [doi: 10.3390/s130404922]. |
| [10] | Kuruvila J, Nayak A, Stojmenovic I. Hop count optimal position based packet routing algorithms for ad hoc wireless networks with realistic physical layer. IEEE Journal on Selected Areas in Communications, 2005,6(23):1267-1275. |
| [11] | Wang Y, Chen HM, Chu XW, Wu YW, Qi Y. Reliable and energy-efficient routing for static wireless ad hoc networks with unreliable links. IEEE Trans.on Parallel and Distributed Systems, 2009,20(10):1408-1421 [doi: 10.1109/TPDS.2008.248]. |
| [12] | Xu JF, Li KQ, Min GY. Reliable and energy-efficient multipath communications in underwater sensor networks. IEEE Trans.on Parallel and Distributed Systems, 2012,23(7):1326-1335 [doi: 10.1109/TPDS.2011.266]. |
| [13] | Campobello G, Leonardi A, Palazzo S. Improving energy saving and reliability in wireless sensor networks using a simple CRT- based packet-forwarding solution. IEEE/ACM Trans. on Networking, 2012,20(1):191-205 [doi: 10.1109/TNET.2011.2158442]. |
| [14] | Gallais A, Ingelrest F, Carle J. Preserving area coverage in sensor networks with a realistic physical layer. In: Proc. of the INFOCOM. 2007.2416-2420 [doi:10.1109/INFCOM.2007.292]. |
| [15] | Chi KK, Jiang XH, Horiguchi S. Network coding-based reliable multicast in wireless networks.Computer Networks, 2010,54(11): 1823-1836 [doi: 10.1016/j.comnet.2010.02.010]. |
| [16] | Lou W, Wu J. Toward broadcast reliability in mobile ad hoc networks with double coverage. IEEE Trans.on Mobile Computing, 2007,6(2):148-163 [doi: 10.1109/TMC.2007.31]. |
| [17] | Xu H, Garcia-Luna-Aceves JJ. Efficient broadcast for wireless ad hoc networks with a realistic physical layer.Elsevier Ad Hoc Networks Journal, 2010,8(2):165-180 [doi: 10.1016/j.adhoc.2009.06.003] . |
| [18] | Yang ZY, Li M, Lou WJ. R-Code: Network coding-based reliable broadcast in wireless mesh networks.Ad Hoc Networks, 2011, 9(5):788-798 [doi: 10.1016/j.adhoc.2010.09.009]. |
| [19] | Wong GKW, Liu H, Chu XW, Leung WY, Xie C. Efficient broadcasting in multi-hop wireless networks with a realistic physical layer.Ad Hoc Networks, 2013,11(4):1305-1318 [doi: 10.1016/j.adhoc.2010.12.001] . |
| [20] | Stojmenovic I, Nayak A, Kuruvila J, Ovalle-Martinez F, Villanueva-Pena E. Physical layer impact on the design and performance of routing and broadcasting protocols in ad hoc and sensor networks.Computer Communications, 2005,28(20):1138-1151 [doi: 10. 1016/j.comcom.2004.07.040] . |