下载文档原格式
小型微型计算机系统Journal o f Chi nese Co m puter Sy stem s2009年5月第5期V o l 130N o .52009收稿日期:2009-02-28 基金项目:重庆市自然科学基金项目(K J 080526)资助;重庆市科委项目(C STC2008B B2085)资助. 作者简介:尚凤军,男,1972年生,博士,副教授,主要研究方向为无线传感网络,网络流量测量;雷 阳,男,1984年生,硕士研究生,主要研究方向为无线传感网络,无线自组织网络.无线传感器网络能量有效成簇算法研究尚凤军,雷 阳(重庆邮电大学计算机科学与技术学院,重庆400065)E-m ai:l s han gfj @cqup.t edu .cn摘 要:分析当网络覆盖范围变大时LEA CH 协议存在的问题,针对传感网络中簇头采用单跳通信时距离基站较远的簇头能量消耗太大而过早死亡,采用多跳通信时距离基站较近的节点过多参与数据会转发而过快死亡,提出一种综合考虑节点位置、节点能量状况的多跳改进算法L E A CH-L,同时,LEA CH-L 还通过限制簇头的最短转发距离,避免网络过多的进行数据转发使网络开销增大.仿真结果显示,当网络范围变大时,L EACH -L 能有效的减少网络中节点和基站通信时的能量消耗,均衡传感网络节点负载,较大幅度的延长传感器网络的生命周期.关键词:无线传感器网络;LEA CH;路由;多跳中图分类号:T P39314 文献标识码:A 文章编号:1000-1220(2009)05-0839-04Energy E fficient Clustering A lgorit h m forW ireless Sensor Net worksSHA NG F eng -jun ,L EI Y ang(C ollege o f Com pu ter Sci en ce and Techno l ogy,C hon gq i ng Un iversity of Po sts and Tel eco mmun ica ti on s ,C hongqing 400065,C hina )Abstrac t :T his paper ana l y se s the proble m i n L E A CH w hen t he ne t w o rk is in a larg e sco pe ,consi der i ng o n t he c l usters w h ich is far w it h t he B S deed ea rli er fo r t he big d is patch o f energy i n once comm un icati on i n one hop routi ng and t he cluster sw h ich is c l o ser the BS deed ear lier fo r transferring m o re date packe ts in m ulti p l e hop ro uting.A new R o uti ng P ro toco ls na m ed L EACH-L is propo sed ,EACH-L restrict a m i ni m u m distance fo r m u lti ple hop ro uti ng w hich can avo i d increase t he energy d is patch i n a m ulti p l e hop comm u -n i cation .T he result o f experi m en t show s tha t L E A CH-L can ba l ance the ene rgy d is pa t ch o f t he senso rs i n different area and m ake a long er life span o f sen s o r ne t w o rk w hen t he scope o f net w o rk go es i n t o larg er .K ey word s :w ire l e ss s enso r net w o rk ;routi ng ;LEA CH;m u lti ple -hop1 引 言无线传感器网络能够在恶劣的环境下获取大量详实而可靠的信息,可以广泛应用于国防军事、工业控制、环境监测、交通管理、医疗保健、智能家居等各个领域.但是,传感器节点一般只靠电池供电,有效的利用传感器节点的能量是传感网络通信协议设计的重要目标.文献[1]提出一种称为L EACH 的动态分簇协议,在一个周期内,少量节点成为簇头,非簇头节点向簇头节点以TDM A 的方式发送数据,簇头节点融合了来自非簇头节点的数据之后,以单跳的方式和基站直接通信,文献[2]提出了基于LEA CH 的多跳路由协议,称为L EACH -D.PEG A SIS 算法[3]借鉴了LEACH 中分簇算法的思想,将节点组织成链的形式,链的形成由每一个节点或者基站计算得到,因此需要知道网络拓扑的全局知识,导致需要额外的节点和基站之间的通信.HEED 算法[4]以簇内平均可达能量作为衡量簇内通信成本的标准.但是HEED 算法,在每轮的簇头选择过程中,所有的节点都处于工作状态(发送或侦听),无形中增大了整个网络的能量消耗.SEP 协议[5]提出了分布式能量有效的异构传感器路由协议,引入了平均能量因子有效延长了网络的生存周期.文献[6]研究了无线传感器网络中的功率控制问题,通过采用一种新的基于节点位置的功率控制算法,该算法的复杂度不高,易于在节点运行,仿真结果证明该算法能取得较好的网络性能.2 问题描述大量节点所采集的数据通过多跳方式流向极少数的基站,造成距离基站较近的节点较早死亡即热点问题.同时,无线传感网络中的传感器节点一般采取随机抛洒的方式进行布图1 线性网络模型F i g 1 L i near net w o rk m ode l置,因此传感器分布并不均匀,采取单纯的以距离为路由下一跳的路由选择的话,会造成个别节点因为地理位置的优势在多个路径中被选择,从而较快的面临/死亡0.另外,采用多跳的路由机制,能够降低网络数据通信的能量开销,但是却增加了作为路由中间节点的电路能量消耗,有时采用多跳的路由方式所消耗的能量有可能甚至大于直接传送的方式.为了便于研究而这之间的关系,假设存在如下页图1所示的线性网络模型:当位于距离基站半径为n r 的节点向基站发送数据时,若采用直接通信的方式,则网络消耗的总能量为:E direct =E Tx (k,nr)=E Tx -elec t (k )+E Tx-a m p (k,nr )若采用多跳的传输时,网络消耗的总能量为:E m ulthop =nE Tx-e lect (k )+(n -1)E Rx -elect (k )+nE Tx-a m p (k ,r )=(2n -1)kE elec t +nE T x-a m p (k ,r )本文采用文献[1]给出的参数,有如下结论:当r \d 0时,E direct -E m ulthop =n 4r 4kE T X -Emp -2(n -1)kE elect -nr 4kE TX-Emp :0;当nr [d 0时,E direct -E m ulthop =n 2r 2kE T X -Efs -2(n -1)kE elec t -nr 2kE TX-Ef s <0;当r <d 0,nr \d 0时,E direct -E m ulthop =n 4r 4kE T X -Emp -2(n -1)kE elect -nr 2kE TX-Ef s ,当r >d 0n d 2+40000n 2(n -1)4n 2d 214时,n 4r 4kE TX -Emp -2(n -1)kE elect -nr 2kE T X -Efs :0;当r >d 0n d 2+40000n 2(n -1)4n 2d 214时,n 4r 4kE TX -Emp -2(n -1)kE elect -nr 2kE T X -Efs [0.因此,在节点距离基站较近时,应该避免多跳的路由机制,减少路由的开销,当传输距离较大时,在限制转发距离的前提下,多跳的传输策略能够减少网络的能量消耗,同时多跳传输中应注意减少跳数,以节约中间节点的电路消耗.3 LEAC H -L 算法311 LEACH -L 最优簇头数假设位于r 1区域的簇头的个数为h 1,传感器节点的数量为N 1,则每个簇头的能量消耗由接收所有簇成员的信息、融合这些数据、并把融合后的信息传送给Si nk 节点三个方面组成.我们假设基站离第一区域比较近,同样采用自由空间模型进行传输,这样,在一帧中簇头节点消耗的能量为:E CH =l E e lec tN 1h 1-1+l E DAN 1h 1+l E e lec t +l E TX -E fs d toB S 2l 为每个数据的信息位数,E DA 为数据融合的消耗,d toB S 是簇头节点和基站的距离,这里我们取它为第一个区域的半径的一半.簇内成员节点离簇头的距离假设它不超过自由空间模型的临界值,这样,一个非簇头节点的能量消耗为;E non-CH =l E e lect +E TX -E fs d to CH 2d toCH 为簇内成员到簇头的距离.R 区域中每个簇所占的面积大约为P R 21h 1.通常情况下,这是一个任意形状的区域,节点以Q (x,y )密度分布.簇头位于簇中间,这样从节点到簇头的平方距离可由下式计算:d toC H 2=k (x 2+y 2)Q (x,y )dxdy =kr 2Q (r ,H )rd rd H =QQ 2P H =0Qr 21h 1r 1=0r 3(r,H )drd H =Q 2P r 41h 21如果整个簇内节点的密度是均匀的,那么Q =N 1P r 21,那么d toC H 2=2N 1r 21h 21,则E non-C H =l E elect +l E T X -Efs2N 1r 2h 21则发送一帧中整个簇的能量消耗为:E cluster =E C H +N 1h 1-1E non-CH U E CH +N 1h 1E non-C H =l E electN 1h 1+l E DA N1h 1+l E elec t +l E TX -E fs d toB S 2+N 1h 1E TX -E fs 2N 1r 21h 21l +l E elect那么在R 1区域的一帧的总能量消耗为:对E to ta l 求倒,让其等于零,得到r 1最优簇头数为:h 1=232E TX -E fs N 21r 214E e le ct +r 21E T X -E fs这个最优值和上面分区域大小的计算是在做了很多假设的情况下得到的,只能作为参考,实际的应用中需要具体考虑和设定.312 LEAC H -L 描述与LEACH 相似,L EACH -D,LEA CH -L 协议按轮运行,每轮分为设置阶段和稳定工作阶段.设置阶段选出簇头,由簇头给成员分配TDM A 时隙.在稳定工作阶段,簇的成员按分配好的TDM A 时隙将数据发送至聚类首领,LEA CH -D 中簇头将数据聚合后如果簇头节点和基站的距离较近,采用直接传输的方式,否则把数据发送给和它最近的簇头节点,收到数据的簇头节点再根据距离最近的原则选择它的下一跳簇头路由节点,直至数据传输到据基站较近的簇头节点,通过它传输到基站.而L E A CH -L 中聚类首领将来自成员节点的数据融合之后,如果聚类首领离基站较近,采用直接传输的策略,否则根据临近基站的簇头节点的位置和能量状况选择下一条路由,得到来自上一跳的数据的簇头再根据临近基站的簇头的位置和能量状况选择它的下一跳路由,如此直至将数据发送到基站,经过一轮数据收集后,将选取新的聚类首领,如此重复两个阶段,同时,为了保证离基站较远的节点向基站发送数据时,下一条路由选择能够尽量采用多跳的传输,本文吸收SEP [5]协议的思想,假设网络中有一定比例的传感器节点拥有较多的能量.下面是L E A CH -L 协议的描述:840 小 型 微 型 计 算 机 系 统 2009年S i nk .x,S i nk .y :基站的坐标信息;S(i ).x,S(i ).y :传感器节点i 的坐标;S(i ).d :传感器节点i 和基站间的距离,可通过坐标计算出;S(i ).E:传感器节点i 的能量;S(i ).ed :传感器节点i 和基站直接通信时的能量消耗,S(i ).:t 根据距离划分的传感器节点时域信息;S c (i)t :位于时域t 并且当选为簇头的传感器节点;S c (i)t .CH:可以作为簇头节点S c (i)t :下一跳路由的候选簇头节点集合;R e str i c tion_d istance :数据转发的最短有效距离;M ax _d ist ance :直接通信的最大距离;(1)首先基站向全网广播一个M ax _d istance 和一个预先确定的距离D,当S(i).d \M ax _distance 时,S (i).t =S (i).d -m ax_d is tan ceD(2)根据LEA CH 算法中的簇头选举算法和簇的形成算法进行簇的划分,成员节点按照TDM A 的方式向簇头发送数据且簇头节点对成员节点传送的数据进行数据融合.(3)t=0时,S c (i)0以频率f 0向基站直接发送数据包,数据包中包含S c (i )0的能量和位置信息,基站以频率f 1向S c (i)1发送S c (i )0的位置和能量信息,S c (i)1维护自己的S c (i)1.CH.S c (i)1.CH ={S c (i)0/d (S c (i)0,S c (i )1)<S c (i )1.d,S c (i )1.d -S c (i)0.d >=Restr iction _distance,S c (i )1E -S c (i)i .ed <S c (i)0.E -S c (i)0.ed }(4)T =T +1,t=T;(5)S c (i)t 从S c (i)t .CH 中选择使d(S c (i)t ,S c (i)t-1)最小的节点S c (i)t-1作为目的节点以频率f t 发送数据,并更新S c (i)t .CH 中关于S c (i)t-1的能量信息,如果S c (i)t .CH 为空,直接以频率f t 向基站发送数据.(6)如果t >0,t =t-1,转到(5),否则S c (i)t 直接向基站发送数据;(7)基站收到来自S C (i )t 的数据后,基站以频率f t 向S c(i )t+1发送S c (i)t 的位置和能量信息,S c (i)t+1维护S c (i)t +1.CH ={S c (i )t /d (S c (i)t ,S c (i )t+1)<S c (i )t+1.d,S c (i)t+1.d -S c (i)t d >=R estr icticn _d istance,S c (i )t+1.E -S c (i )t+1.ed <S c (i )t .E -S c (i)t .ed },转到(4)通过上述的步骤,距离基站较远的基站通过中间簇头的转发完成和基站之间的通信,其中R e str i c tion_d istance 限制了簇头之间转发数据的最短有效距离(向基站的推进距离),最小的d(S c (i)t ,S c (i)t-1)使得中间路由趋向于基站和源簇头的连接线上,通过分析可知,这样的路由策略不仅能平衡传感器的能量开销,并且能够降低网络的能量消耗.4 仿真与分析图2为网络生命周期.L EACH -L 的FND 、HND 时间分别是L EACH 的12倍、118倍,这是因为在大场景环境下,LEACH 的簇头和基站之间的通信距离加大,簇头单轮的通信能量损耗也随之加大,而L E A CH -L 中簇头和基站之间的通信通过离基站较近且能量充裕的簇头转发,因此单个簇头单轮通信能量损耗不会随区域的增大而大幅增加,并且单轮的簇头和基站通信的过程中,簇头之间趋于能量平衡.此外,L EACH 和L EACH -D 的节点最后死亡时间比L EACH 的长,这是因为LEA CH -L 在路由选择的过程中充分考虑了簇头节点的能量状况,使得网络的能量尽可能的平均的分布在所有的传感器中,所以在前期,LEA CH -L 算法的网络中的存活节点和网络覆盖面积远远大于LEA CH -D 和L E A CH,在某个时间点,LEA CH 网络中的节点开始迅速死亡,所以后期的存活节点数量迅速降低,传感网络中死亡节点的数目占有一定比例的时候我们就可以认为网络的死亡,因此,这个不影响LEACH -L 在延长传感网络生命期中的优越表现.图2 500@500死亡节点和轮的关系F i g 2 N u m ber o f dead no de s ove r nu m be r o f rounds 图3是L EACH -L 和L EACH 及LEA CH -L 的能量消耗图,从图中可以看出,和LEA CH 、L EACH -D 相比,LEACH -L 在时间为200轮时能够节约将近一半的能量,同样的因为随着轮数的推移,L EACH -L 的覆盖面积远远大于L EACH 、LEA CH -D,在某一时刻,L EACH -L 的总能量消耗会大于LEACH 和L EACH -D.图3 500@500环境下能量消耗F i g 3 Com par i ng t o ta l resi dua l energy o f ne t w o rk ov er nu m ber o f rounds图4(见下页)为LEA CH -L 中各区域能量消耗和时间的关系,我们可以发现,无论在那个场景下LEA CH -L 中的8415期尚风军等:无线传感器网络能量有效成簇算法研究能耗明显的大于另外一个区域,从前面的分析可以知道,LEACH -L 均衡网络的能量,延长了网络的寿命.图4 不同区域节点的能量消耗F ig 4 Com par i ng energ y co st o fnet w o rk ov er nu m ber o f rounds5 结 论本文提出了一种能够应用于大范围布置传感器网络的路由协议LEA CH -L.L E A CH -L 中簇首节点之间可以相互通信,离基站较远的传感器簇首节点根据靠近基站的簇首节点的能量状况选择路由,仿真实验表明,在较大的范围的传感器网络中,和L EACH 、单纯考虑距离的多跳协议LEACH -D 相比,LEA CH -L 能够均衡网络的负载,降低网络的能量消耗,提高网络的数据采集精度,延长网络的生命周期.R eferences :[1]H ei nz el m an W,C handrakas an A,B al ak ri shnan H.En ergy effi cien tco mm un icati on pro t ocol fo rw i rel essm icrosensor net w ork s[C ].H a -w aii In t ernationa l C onference on S yste m S ci ences ,2000,3005-3014.[2]Fan X i an g -n i ng ,Song Yu-li n.I m prove m ent on LEACH pro t o col ofw i rel ess sensor net w o rk [J ].In t ernati onal Con ference on S ensor Techno l og ies and App li cati ons ,2007,260-264.[3]L i nd s ey S,Raghavendra C,S i va li nga m K.D at a gatheri ng i n sensornet w o rks us i ng t he en ergy-del ay m etric[J].I EEE T ran s .on Parallel and D istri bu ti ve S yste m s ,Sp eci a l Iss ue on M ob il e Com pu ti ng,2002,13(9):924-935.[4]Y oun i s O,Fahm y S .H eed :a hyb ri d ,energy -effi cien,t d istri butedcl u st eri ng approach for ad-hoc s en s or net w o r k s[J].I EEE T ran s .on M ob ile C o m puti n g ,2004,3(4):660-669.[5]Q i ng l,i Zh u q i ng -xi n,W ang m i ng-w en .A distri bu t ed energy -eff-icien t cl u st eri ng al gorit hm for heterogeneous w i rel ess sen s or ne-t w orks[J].C hines e J ournal of Soft w are ,2006,17(3):481-489.[6]W en ka,i G uo w e,i H uang guang -jie .Pow er contro l algo rit hm bas edon nod e po sition i n w ire l ess sen s or net w ork [J ].C h i nese J ourn al of S ci en tifi c Instrum en ,t 2008,29(2):426-431.附中文参考文献:[5]卿 利,朱清新,王明文.异构传感器网络的分布式能量有效成簇算法[J].软件学报,2006,17(3):481-489.[6]文 凯,郭 伟,黄广杰.传感器网络中基于节点位置的功率控制算法[J].仪器仪表学报,2008,29(2):426-431.842 小 型 微 型 计 算 机 系 统2009年。
