无线传感器网络的蚁群自组织算法

第9期2007年9月电󰀁󰀁子󰀁󰀁学󰀁󰀁报ACTAELECTRONICASINICAVol.35󰀁No.9

󰀁

Sep.󰀁2007

无线传感器网络的蚁群自组织算法

王󰀁睿

1,2

,梁󰀁彦,潘󰀁泉

11

(1󰀁西北工业大学自动化学院,陕西西安710072;2󰀁中国科学院计算技术研究所,北京100080)

󰀁󰀁摘󰀁要:󰀁探测效能与能量节省的综合性能优化是无线传感器网络研究的一个热点问题.提出了一种分布式、自适应的无线传感器网络蚁群自组织算法,将无线传感器网络节点映射为情绪蚂蚁,通过蚁群间的协同对节点的唤醒概率进行群体智能优化,从而实现无线传感器网络自组织,并以定理的形式给出了性能指标和相关参数的设计方法.仿真表明,算法实现在唤醒较少节点的前提下,对目标保持了较好的探测能力.

关键词:󰀁无线传感器网络;群体智能;自组织;蚁群优化

中图分类号:󰀁TP393󰀁󰀁󰀁文献标识码:󰀁A󰀁󰀁󰀁文章编号:󰀁0372-2112(2007)09-1691-05

AntColonyforWirelessSensorNetworksSel-fOrganization

WANGRui1,2,LIANGYan1,PANQuan1

(1.CollegeofAutomation,NorthwesternPolytechnicUniversity,Xi󰀁anShaanxi710072,China;2.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080,China)

Abstract:󰀁Inwirelesssensornetworks(WSN),itisafundamentalissuetobalancethetwoconflictingperformanceindexes:sensingabilityandenergycost.Anadaptiveanddistributiveself-organization(SO)algorithmisproposed,inwhichsensornodeintheWSNismappedtoemotionalantintheantcolonysystem.Bythismeans,thewakeupprobabilityofnodescanthenbeopt-imizedthroughthecollaborationamongantcolonieswithswarmintelligence,soastoaccomplishefficaciousSOofWSN.Inadd-i

tion,thedesigningmethodoftheperformanceindexesandrelativeparametersisdepictedintheformoftheorem.Simulationresultsshowthattheproposedalgorithmmaintainssuperiordetectionabilitywhilewakingupfewernodestodetect.

Keywords:󰀁wirelesssensornetworks;swarmintelligence;self-organization;antcolonyoptimization

1󰀁引言

󰀁󰀁无线传感器网络[1](WSN,WirelessSensorNetworks)是目前的研究热点.WSN节点通常只有有限能量,当自

身能量消耗殆尽,节点即失效.因此在设计WSN时,如何尽量提高能效成为非常重要的问题;另一方面,WSN节点稠密撒布,节点间的有效探测范围相互重叠,相关节点产生的观测信息有较高的冗余度.这两方面表明了利用WSN自组织来提高系统效率,节省能量开销的必要性和可行性.

WSN自组织的常见算法是预先给节点设定一个随机的唤醒概率[2](randomizedactivation,RA),每个节点都按照此概率随机的唤醒且唤醒概率相互独立,但是由于节点间缺少协同,使得整体算法的效率较低并且节点的唤醒状态不能根据目标状态变化进行自适应的调整.

根据无线传感器网络的特点,WSN自组织须满足

以下要求:(1)分布性:WSN节点的探测、计算能力都较弱,要完成复杂的计算必须要求算法具有分布性特点;(2)协同性:WSN属于sensor-rich系统,通过节点间的简单协同来实现复杂的网络优化;(3)自适应性:WSN的工作环境通常不可预先设定,感知对象的状态也会经常发生变化,网络必须对这些不确定性有较好的自适应性.

如果将WSN的海量节点视为蚁群优化[3]中的蚂蚁,每只蚂蚁都分别具有一定的探测和计算能力,将节点间的通讯看作蚂蚁间信息的传递,则通过蚁群间的协同就有可能以群体智能的方式实现WSN自组织.本文构造了一种基于情绪蚂蚁的自组织算法(EmotionalAntBasedSel-forganizationinWirelessSensorNetworks,EAS),将

WSN自组织问题映射为分布式群体智能优化方法,通过对节点唤醒概率的优化,实现在消耗较少能量的前提下,对目标保持有较好的探测能力.

收稿日期:2006-04-03;修回日期:2007-02-09基金项目:国家自然科学基金(No.60634030)1692󰀁󰀁电󰀁󰀁子󰀁󰀁学󰀁󰀁报2007年

2󰀁基于情绪蚂蚁的无线传感器网络自组织(EAS)算法

2󰀁1󰀁情绪蚂蚁模型设计

首先将无线传感器网络节点定义为一种情绪蚂蚁,它具有如下特性:(1)蚂蚁节点具有情绪,并且其情绪总在自信与不自信之间变化;(2)越自信的蚂蚁节点处于唤醒状态的概率就越大;(3)蚂蚁节点具有感知能力,并且不同的感知结果可以引发其情绪变化;(4)相邻的蚂蚁节点之间可以分享感知结果;(5)如果没有外界因素影响,蚂蚁节点的情绪会随着时间的流逝逐渐趋于不自信.

设感知区域为D,在D内均匀撒布了n个情绪蚂蚁节点,其集合可表示为A={A1,󰀁,An},其中情绪蚂蚁节点Ak表示第k传感器节点,设蚂蚁节点位置向量集合L={l1,󰀁,ln},其中lk为Ak的空间位置向量.

设Ak在时刻t的情绪为Ik(t),且Ik(t)的值反映了其情绪中的自信程度,Ik(t)越大自信度越高,同时I󰀁[Imin,Imax],即超出此范围则情绪达到饱和.

每只情绪蚂蚁节点都具有独立的感知、交流能力(对应于传感器节点的探测、通信能力),分别定义如下:

(1)通信方式

本文考虑传感器节点采用S-MAC协议.即情绪蚂蚁节点在每个Round周期按照以下两个阶段的方式工作:在唤醒/睡眠阶段,情绪蚂蚁节点根据唤醒概率随机选择自己处于唤醒状态或睡眠状态:当处于唤醒状态时,则对周围环境进行探测并进行必要的处理;而处于睡眠状态时,情绪蚂蚁节点将进入睡眠状态以节省能量.在收/发阶段,情绪蚂蚁将与邻居集合的蚂蚁通过交互的方式进行探测结果的共享.

由于多跳通讯不仅消耗了过多的能量而且还会造成网络通讯延迟及误码率增高等不良后果,因此我们仅考虑单跳范围内情绪蚂蚁之间的通信协同.设Ak的邻居集合neighbor(k)如下:

neighbor(k)={Aj|j满足󰀁lj-lk󰀁󰀂Rc,对于j=1,󰀁,n}

[4]

设情绪蚂蚁节点Ak在t时刻唤醒状态标志位󰀁k(t):

󰀁k(t)=

1,󰀁t时刻Ak处于清醒状态0,󰀁t时刻Ak处于睡眠状态

(3)

设Ak在t时刻的唤醒概率wk(t)󰀁P{󰀁k(t)=1},其具体计算将在下节分析.设Ak的检测概率为Pdk,即当在Ak的探测范围内出现目标时,将以Pdk的概率发现目标;虚警概率为Pfk,即使Ak的探测范围内没有目标出现,仍将以Pfk的概率错误的宣告发现目标.设Ak在t时刻判定其是否发现目标的标志位󰀁k(t):

1,t时刻Ak判定目标出现

󰀁(t)=k

0,其他

P{󰀁k(t)=1}=P{󰀁k(t)=1|󰀁k(t)=1}P{󰀁k(t)=1}󰀁+P{󰀁k(t)=1|󰀁k(t)=0}P{󰀁k(t)=0}

=P{󰀁k(t)=1|󰀁k(t)=1}P{󰀁k(t)=1}+0=P{󰀁k(t)=1|󰀁k(t)=1}P{󰀁k(t)=1}

(4)

(5)

显然,当Ak的探测范围内存在目标时,󰀁󰀁k(t)=1󰀁的发生概率为wk(t)󰀁Pdk;而当其探测范围内不存在

目标时,󰀁󰀁fk.k(t)=1󰀁的发生概率为wk(t)󰀁P2󰀁2󰀁算法设计

当无线传感器网络的感知区域内存在目标时,希望有较多的传感器节点能够参与探测,以保证探测效果;而没有目标存在时,为了节省能量,则希望有较多的节点处于睡眠状态.

在t时刻,蚂蚁Ak可以分泌信息素󰀁k(t):

1,󰀁󰀁k(t)=1

󰀁k(t)=󰀁󰀁k=1,󰀁,n(6)

0,󰀁其他

󰀁k(t)可发送到neighbor(k)内所有蚂蚁节点,同时Ak也接收来自neighbor(k)内的蚂蚁节点散布的信息素并进行累积,定义该累积量为󰀁Ik(t),由下式计算:

󰀁Ik(t)=

j󰀁neighbor(k)

󰀁

󰀁j(t)

(7)

同时Ak处积累的信息素Ik(t)也会随着时间逐渐分解,定义一个周期内的分解率(1-󰀁)󰀁[0,1],则分解后剩余的信息素为󰀁Ik.参数󰀁表示信息失效的程度,与被观测对象的运动特性有关,显然被观测对象运动越快,信息素分解得也越快,󰀁也越小.则t+1时刻的信息素由󰀁Ik(t)与󰀁Ik(t)两部分构成.又规定任意I󰀁[Imin,Imax],则Ak在周期t的信息素更新公式如下所示:󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁

󰀁Ik(t+1)=min{Imax,max{Imin,󰀁Ik(t)+󰀁Ik(t)}}(8)

由式(6)~(8)可知:当Ak发现目标后,通过分泌信息素并散布到其邻居情绪蚂蚁,使得邻居情绪蚂蚁的信息素水平通过更新有可能加大,而如果邻居情绪蚂蚁如果也发现目标,就通过这种󰀁正反馈󰀁的方式加强这种趋势,使得Ak及其邻居情绪蚂蚁节点的信息素(1)

其中Rc大小为传感器节点单跳通讯距离.

(2)探测感知

对情绪蚂蚁Ak,其探测范围的体积表示为Vsk.将D划分为单元格,设单元的个数为m,令G={1,2,󰀁,m}为所有单元的集合.对于单元i存在一个影响空间Qi,使得该空间内所有传感器节点的探测范围都包含i,设该空间体积为VQi,该空间内蚂蚁节点的集合sensor(i)表示为:

sensor(i)={Ak|lk󰀁Qi}

(2)

第󰀁9󰀁期王󰀁睿:无线传感器网络的蚁群自组织算法1693

进一步增大;如果Ak唤醒却没有发现目标时则散布的信息素强度为0,而信息素会随着时间而不断分解,使得Ak及其邻居情绪蚂蚁节点的信息素趋于变小.从以上描述中可以得出,情绪蚂蚁节点的唤醒概率应该和其当前的信息素大小有关,而信息素表征了蚂蚁节点的自信程度.当前节点信息素越大,节点的自信度越高,提示在其周围出现目标的可能性越大,因此节点就越需要以较大的唤醒概率转移到唤醒状态.因此本文构造情绪蚂蚁节点Ak唤醒概率计算公式如下:

wk(t)=Ik(t)/Imax

2󰀁3󰀁性能指标设计

为说明算法的性能,设计性能指标如下:

(1)节点利用率ns(t)

t时刻节点利用率ns(t)为在t时刻探测到目标的节点总数与处于唤醒态的节点总数之比,由下式计算:

ns(t)=nd(t)/nw(t)(10)其中nw(t)表示t时刻所有处于唤醒态的情绪蚂蚁节

点总数,实际上是能量消耗指标,nw(t)越大,处于唤醒态的节点越多,总的能量消耗也越多.nd(t)表示t时刻探测到目标的情绪蚂蚁节点总数.ns(t)实际上表示的是资源的有效利用率,ns(t)越大说明算法效率越高,合理提高资源利用率是算法设计的目标,也是衡量算法性能的指标之一.

(2)单元探测概率PA(i)

定义单元的探测概率PA(i)表示当目标存在于i单元时,无线传感器网络发现该目标的概率.

定理1󰀁设无线传感器网络中任一节点k的唤醒概率为wk,检测概率为Pdk,则对于无线传感器网络的探测区域内任一单元格i,该单元内目标被探测到的概率PA(i)为:

PA(i)=1-k󰀁sensor(i)

小探测概率Pmin,则最小唤醒概率wmin可由以下定理设计:

定理2󰀁给定探测区域单元的最小探测概率Pmin,则在不小于置信度1-󰀁的意义下,无线传感器网络中任一节点的最小唤醒概率wmin应满足:

1-(1-wminPD)

Mmin

󰀁Pmin

(12)

(9)

其中PD=min{Pd1,Pd2,󰀁,Pdn},n为网络中传感器节点的总数目.

(2)最大信息素Imax设计定理3󰀁假设目标在探测区域内以等概率可能性出现,则在不小于置信度󰀁的意义下,其最大信息素Imax由下式求出:

Imax=Mmax󰀁(PEPD󰀁+(1-PE)PF)/(1-󰀁)

(13)

其中Mmax为邻居集合内包括的节点数上界,PD󰀁=max{Pd1,Pd2,󰀁,Pdn},PF=max{Pf1,Pf2,󰀁,Pfn},n为传

感器网络中节点总数.

限于篇幅,此处证明略.(3)最小信息素Imin设计

由最大信息素Imax、最小唤醒概率wmin及式(9)可进一步计算出最小信息素Imin如下:

Imin=Imax󰀁wmin

(14)

3󰀁仿真分析3󰀁1󰀁仿真环境

感知区域大小为200󰀁200,其中随机撒布500个性能指标相同的传感器节点,图中以黑点表示,如图1所示.目标为以v=6m/s作匀速直线运动,起点为[35,40],角度为38󰀁,运行时间为50s,运动轨迹在图中表示为虚线,可以看出,该条轨迹完整展现了运动目标从进入感知区域到离开的完整过程.

󰀁

(1-wkPdk)(11)

限于篇幅,此处证明略.

定理1表明单元i周围唤醒的节点越多,节点的探测概率越大,PA(i)也越大,该单元内目标被检测到的概率也越大,说明探测效果越好.对感知区域有较好的探测效果是无线传感器网络实现功能的保障,所以也是衡量算法性能的指标之一.2󰀁4󰀁参数设计

(1)最小唤醒概率wmin设计

最小唤醒概率wmin越大,目标出现后发现的可能性就越大,被随机唤醒的节点数就越多,消耗的能量越多;反之wmin越小,目标出现后发现的可能性就越小,被随机唤醒的节点数就越少,消耗的能量越少.因此,合理的设计唤醒概率需要折衷考虑探测与能量消耗两方面的因素,如果事先给定系统要求的探测区域单元最Rs参数取值如表1所示:

表1󰀁仿真参数意义及其选取

RcPDPFPminRoundc强度601-󰀁度0.9󰀂度0.91-󰀁率0.5有效探有效通探测虚警最小探工作信息素置信置信分解测半径讯半径概率概率测概率周期15米30米0.90.050.31秒1694󰀁󰀁电󰀁󰀁子󰀁󰀁学󰀁󰀁报2007年

󰀁󰀁由2.4节及表1,可求出最小唤醒概率wmin=0󰀁035、最大信息素Imax=11󰀁2、最小信息素Imin=1󰀁09.3󰀁2󰀁仿真结果分析

将本文算法与RA算法相比较,其中算法A中所有节点均按照唤醒概率w=1进行工作;算法B中所有节点均按照唤醒概率w=0󰀁49进行工作;算法C中所有节点均按照唤醒概率w=wmin=0󰀁035进行工作;算法D为本文算法.四种算法中其余参数取值均按照表1选取.每组算法均进行50次MonteCarlo仿真.

图2~4分别是四种算法nw,nd,ns参数比较.从图2可以看出:A算法中所有节点都按照概率1被唤醒,显然消耗了最多的能量.B算法中所有节点的唤醒概

醒,表明C算法只有最少的节点都被唤醒,能量消耗最少.D算法中节点按照本文算法自适应的计算唤醒概率,可看出D算法的唤醒节点数远远小于A和B算法,而与C算法接近.从图3可知:A算法中观测到目标的有效唤醒节点数最多.C算法始终保持较低水平,而B算法中的有效唤醒节点数处于中间.D算法在开始10拍左右对出现目标的反应速度(即达到较高的有效唤醒节点数)有一段延迟,究其原因:一方面由于目标刚刚进入感知区域,理论上能够发现它的节点还较少(即使A算法也是如此),另一方面信息素的积累需要一个过程;在第15拍左右,有效唤醒节点数达到与B算法相当的水平;第20拍以后,观测到目标的有效唤醒节点数与A算法相近.结合图2、3可得,D算法的节点利用率最高,而其它A、B、C三种算法利用率相近,都维持在较低水平,结果体现在图4中.

为进一步直观表示不同参数对算法性能的影响,仿真中,我们还通过对单元i填充介于[0,255]间的灰度值来表示PA(i)的大小,令该单元的灰度值Gri为:

Gri=PA(i)󰀁255

越亮.

(15)

则PA(i)越大则灰度值越大,在图形上该区域的表现就

图5表示16、32、48时刻感知区域探测概率的灰度图对比结果,图中以󰀁+󰀁表示目标所在的位置.从图中可以看出:由于A算法中所有节点都按照概率1被唤醒,因此对整个感知区域内有最大的探测概率,结果体现在A列的灰度图中,其中黑色区域表示探测盲区;B算法节点的唤醒概率为0󰀁49,B列的灰度图中有较多的灰色区域;而C算法中节点只以很小的概率0󰀁035被唤醒,因此整个探测区域几乎被黑色笼罩;而本文提出的D算法由于节点的唤醒概率自适应,可以看出在目标周围区域的灰度图明显比其它区域亮,表明在目标附近的区域有较高的探测概率,在其它区域探测概率

率取为0󰀁49,表明B算法被唤醒节点数较少,能量消耗也较少.C算法中所有节点都按照最小概率wmin被唤

保持在较低的水平.随着目标的运动,可以看出该块区域随着目标状态变化而自适应的变化,这说明D算法第󰀁9󰀁期王󰀁睿:无线传感器网络的蚁群自组织算法1695

中在目标观测范围内的较多节点被唤醒参与感知,而其余节点则多处于睡眠状态,群体智能得到一定程度的体现.

当节点由于能量耗尽而逐步失效,感知区域内的探测盲区会逐渐增多,这时虽然本文算法仍然适用,但系统性能会逐渐下降,需要补充新的节点以保证系统要求.

为1-󰀁的意义下:󰀁PA(i)=1-k󰀁sensor(i)

󰀁

(1-wkPdk)󰀁1-(1-wminPD)

M

Mmin

i

󰀁1-(1-wminPD)min

由上式最小唤醒概率wmin应满足:

1-(1-wminPD)

证毕

参考文献:

Mmin

(18)

󰀁Pmin

(19)

4󰀁结论

󰀁󰀁本文研究了无线传感器网络中的自组织问题,利用蚁群算法󰀁正反馈󰀁的思想,构造出一类感知情绪蚂蚁,提出一种无线传感器网络的蚁群自组织算法,并给出了性能指标和相关参数的设计方法.仿真结果说明了算法的有效性.

[1]AkyildizIF,etal.Asurveyonsensornetworks[J].IEEE

CommunicationsMagazine,2002,40(8):102-114.[2]SPattem,etal.Energy-qualitytradeoffsfortargettrackingin

wirelesssensornetworks[A].LectureNotesinComputersSc-ience2634[C].Berlin:Springer-Verlag,2003.32-46.

[3]MDorigo,etal.Antsystem:optimizationbyacolonyofcoop-eratingagents[J].IEEETransSystems,Man,Cybernet.-Part

B,1996,26(1):29-41.

[4]WeiYe,etal.Anenergy-efficientMACprotocolforwireless

sensornetworks[A].Proceedingsofthe21stInternationalAn-nualJointConferenceoftheIEEEComputerandCommunica-tionsSocieties(INFOCOM󰀁02)[C].NewYork,2002.1567-1576.作者简介:

王󰀁睿󰀁男,1975年6月出生于河南省平顶山市,工学博士.主要研究方向为无线传感器网络、信息融合.E-mail:wangrui@ict.ac.cn

附录

证明

定理2󰀁按系统要求给定单元最小探测概率Pmin,即要求对感知区域内任一单元i,在统计意义上要求PA(i)󰀁Pmin,节点的最小唤醒概率wmin应满足:1-k󰀁sensor(i)

󰀁

(1-wminPdk)󰀁Pmin.考虑n个传感器节点随机

均匀撒布的情况,设感知区域D的体积为VD,则该区域内传感器节点密度󰀁为:

󰀁=n/VD

(16)

一般认为在上述随机均匀撒布下,󰀁Qi󰀁D,传感器节点数服从参量为󰀁VQi的泊松分布.给定置信度1-󰀁,可以计算出该空间内包括的传感器节点数的下界Mmin,即:

r=Mmin

F(Mimin)=

󰀁

(e-

󰀁VQi

r=0

(󰀁VQi)r/r!)󰀁󰀁

(17)

2m

令Mmin=min{M1min,Mmin,󰀁,Mmin},则在不小于置信度