《电子技术应用》

基于自适应数据融合的LEACH路由协议

来源:电子技术应用2011年第7期
王培东1, 袁召兰1, 王 瑜2
((1. 哈尔滨理工大学 计算机科学与技术学院,黑龙江 哈尔滨 150080; 2. 中国人民解放军九)
摘要: 如何有效地使用传感器节点的能量以延长WSN的生存时间,一直是WSN路由协议研究的重点。基于LEACH,提出了一种新的路由协议AF-LEACH,AF-LEACH根据数据融合的能量开销和所带来的节能增益,对传感器节点采集的数据进行自适应的数据融合。仿真实验表明,与LEACH协议以及在各节点都进行数据融合的MA-LEACH[1]协议相比,AF-LEACH在降低节点能耗,延长网络寿命等方面上有了显著提高。

Abstract:

摘  要:    如何有效地使用传感器节点的能量以延长WSN的生存时间,一直是WSN路由协议研究的重点。基于LEACH,提出了一种新的路由协议AF-LEACH,AF-LEACH根据数据融合的能量开销和所带来的节能增益,对传感器节点采集的数据进行自适应的数据融合。仿真实验表明,与LEACH协议以及在各节点都进行数据融合的MA-LEACH[1]协议相比,AF-LEACH在降低节点能耗,延长网络寿命等方面上有了显著提高。
关键词: 无线传感器网络; LEACH; 数据融合; 移动代理; 网络生存时间

    无线传感器网络WSN(Wireless Sensor Network)可以定义为部署在监控区域内的大量传感器节点所组成的无线网络。该网络能够协作地实时监测、采集和处理节点分布区域内的各种环境或监测对象的信息,并将处理后的数据传送到网络中的特定位置[2]。在WSN中,节点的电池能量和通信带宽等资源均十分有限,因此如何有效地利用有限资源、降低网络能耗、延长网络生命周期是无线传感器网络研究的核心问题。数据融合算法利用感知数据的相关冗余性来减少传输的数据量以达到节能的目的。但在许多WSN的应用场合中,数据融合的能量开销是不能忽略不计的,例如图像数据融合开销和数据传输开销已经非常接近[3]。
    LEACH[4](Low Energy Adaptive Clustering Hierarchy)是低功耗自适应分层路由算法,是WSN中最早提出的分簇路由协议。该算法通过等概率地随机循环选取簇头,其他各节点根据接收到的来自簇头的信号强度进行集群分组。LEACH的执行过程是周期性的,为达到节省能量的目的,每轮由簇的建立阶段和稳定工作两个阶段组成。但这种算法没有考虑到节点测量数据之间存在的相关冗余性,不论数据之间的相关性大还是小,都进行数据融合,然而当数据相关性小时,这样不仅没有减少传输的数据量,反而还额外增加了融合开销,以致增加了网络的能耗,缩短了网络的生命周期。
    LEACH协议中的簇采用C/S(客户机/服务器)计算模式,它把数据发送到簇头节点进行融合处理,这不适合簇组织结构的分布式环境。而MA-LEACH采用的基于移动Agent(MA[5])的分布式计算模式是把处理代码移动到本地节点去处理数据,其所具有的优势非常适合用于簇组织结构。MA-LEACH协议中的数据收集方式是:MA从簇头出发,按照一定的路由在簇内各节点上迁移,每迁移到一个节点都将其携带的数据与该节点采集的数据融合,最后将所有的数据发送至簇头。MA-LEACH将MA与LEACH结合,有效地减少传输中的数据量,从而减少了传输能耗,但该算法也没有考虑到数据之间的相关冗余性。
    AFMR(Adaptive Fusion Mobile Agent Routing)[6]算法根据移动代理在无线传感器网络各节点迁移过程中传输能量和融合能量的开销以及数据融合能带来的节能增益,对移动代理迁移到各节点时是否执行数据融合进行自适应调整,使得MA在路由过程中收集、融合相关节点测量数据的同时,保持总的能量开销接近最优。
    在WSN中对传感器节点进行数据融合后,减少了传输能量,但同时增加了融合开销。针对这一矛盾,AFMR算法根据数据融合算法的能量开销和节能增益,对每个节点是否进行数据融合运算进行了自适应调节。
    针对上述问题,在已有LEACH等协议的基础上,提出了一种新的路由协议AF-LEACH(Adaptive Fusion LEACH),通过在簇内对各节点采集的数据是否执行融合进行自适应调整来节省节点能耗,以达到延长无线传感器网络生命周期的目的。

 


1 基于自适应数据融合的LEACH协议
1.1 基本定义和概念

    无线传感器网络中的一个簇可以用一个无向加权全连通图G=(V,E)来表示,V是簇中所有传感器节点的集合,E使簇中两个节点之间可以直接通信。假设顶点v∈V代表簇中的一个传感器节点,边euv=(u,v)∈E代表顶点u和v所对应的传感器节点能够直接通信。
    LEACH采用的能量消耗公式是无线传感器网络中通用的一阶无线电模式[7],传感器节点在距离d发送一条长度为l bit消息所消耗的能量为:

 设MA由ID、路由算法、数据缓存、处理测量数据代码组成,其中数据缓存中包含部分融合的簇成员节点的测量数据。
1.2 基于自适应数据融合的LEACH路由协议
    基于自适应数据融合的LEACH协议的基本思想是:在LEACH的簇结构形成后,网络的能耗主要体现在感知数据的传输和融合上。
 传输能耗与MA的迁移路由有关,计算MA的路由是TSP问题,本文采用最近邻居算法,从簇头出发,在所有的成员节点中寻找权值(传输能量与融合能量之和)最小的边对应的节点加入到路径解中,然后再在没有访问过的节点中寻找与当前权值相比最小的节点,加入到路径解中,依次类推,直至所有的成员节点都被访问完,路径解中最后一个节点为簇头节点。
    数据融合能够减少传输的数据量,从而减少传输能量,但数据融合本身又能导致能量的开销,因此当节省的传输能量大于数据融合开销时,进行数据融合对于网络节能才是有益的,反之,则会增加网络能耗。由此分析得出,对簇内成员节点应该动态地进行数据融合(自适应数据融合)。当在该节点进行数据融合能节省网络能耗时,就进行数据融合(融合计算开关置1);否则,不进行(融合计算开关置0)。在某一节点进行数据融合后所节省的能量实际是,按照计算好的MA迁移路由,未融合的感知数据从该节点传输到簇头的能量与融合后的数据从该节点传输到簇头节点的能量之差。差值与数据融合的能量进行比较,大于0时,在该节点进行数据融合,否则,不进行。因此簇中某一节点是否进行数据融合还得在迁移路径上后面的节点开关值确定之后才能确定,于是对应于迁移路径上的节点顺序,各节点的融合开关值是逆序计算的。
  簇内各成员节点的数据收集和处理过程是:簇头节点按照簇内成员节点的数目,生成一个TDMA时隙表,簇头节点根据MA的迁移路由中各节点的顺序依次为每个成员分配通信时隙,成员节点只能在其特定的时隙内与由簇头创建的MA进行通信,此时簇内其他成员节点关闭通信模块以节省能量。然后,簇头节点的MAE开始创建并派遣MA,MA从簇头出发,按照已经计算好的迁移路由和各节点的融合计算开关值,MA依次迁移到各节点,当融合计算开关为1(0)时,MA携带的数据缓存中的数据与相应节点采集的数据进行(不进行)数据融合,最后MA携带着融合处理后的数据返回簇头,完成一次数据收集。
    基于自适应数据融合的LEACH协议的基本思想简述为以下三点:
    (1) 计算MA的迁移路由(子函数1)
    根据最近邻居算法计算MA的迁移路径:从簇头出发,依次取权值(传输能量与融合能量之和)最小的边对应的点加入当前解中直至形成回路解。
    (2) 计算自适应数据融合开关值(子函数2)
    假设通过子函数1求得的MA迁移路由为{x0,x1,x2,…,xk,xk+1,…,xn-1,x0}(其中x0为簇头),未融合的感知数据从某一节点传输到簇头的能量与融合后的数据从该节点传输到簇头节点的能量作差,其差值和数据融合的能量进行比较,大于0时,在该节点进行数据融合,融合计算开关置1;否则,不进行数据融合,融合计算开关置0。由于节点xk必须知道它后面的节点xk+1,…,xn-1的融合计算开关值,才能计算出它自己的,故逆序求解In-1,In-2,…,I2,I1,亦即得出该簇内哪些节点进行融合计算,哪些不进行。
    (3) 进行簇内所有成员节点的数据收集(主函数)
    调用子函数1,求出MA的迁移路径{x0,x1,x2,…,xk,xk+1,…,xn-1,x0};
    调用子函数2,根据子函数1的迁移路径求出簇内各节点的融合计算开关值In-1,In-2,…,I2,I1;
    簇头节点派遣MA,收集节点xi(i=1,2,…,n-1)的感知数据,根据Ii=1(或0)的值融合(或不融合)节点xi的感知数据与MA数据缓存中的数据,最后所有的数据汇总至簇头节点。
    传感器节点的数据结构定义如下:
    typedef struct node
    {    int nodeID;      
                                             //节点ID
    int visitedFlag;   
        //是否被访问,1为已经被MA访问过,0为未访问
    }SensorNode;
     基于自适应数据融合的LEACH的算法如下:
    void  FindTheMAPath(int chID,SensorNode cnodes[n])
         //计算MA的迁移路径的子函数,chID表示簇头ID
    {
    int temp=0;
    //暂存迁移路径上某个节点在权值矩阵对应的列下标,
       以便在该列下标值对应的行进行下一个节点的查找
    int x[n];
        //将迁移路径上节点的ID依次存入一维数组x[n]
         i=0;
        //数组x[n]的下标变量
         x[0]=chID;
        //MA迁移路径上的第一节点为簇头节点,即MA
        由簇头节点派遣出去
    do{  DataType  minweight=∞;
       //DataType是感知数据类型,给最小权值变量赋初值    for(j=1;j<n; j++)
        //从所有的簇成员节点中找出距离ID为i的节点            最近的节点
         {  curID=getcurID( );
        //获取第j个簇成员节点的ID
            if((W[temp][j]<minweight)&&(cnodes[curID].
            visitedFlag==0))
       {minweight=w[temp][j];temp=j;}
        }
              x[++i]=curID;
               cnodes[curID].visitedFlag=1;
         }while(i==n-1)
}
void AdaptiveFusion(int *x)
{
    bool I[n];
        //I[i]表示Ii(融合计算开关)
       h(xn-1x0)= c();
        // c(exi,xj)为MA从节点xi到节点xj的单位数据传
                 输能量
    if (ρ(e■)* h(xn-1x0)-q(xn-1))   I[n-1]=1;
        //⊿xn-2 xn-1﹥0?圯In-1=1;
       else                             I[n-1]=0;
       for(i=n-2; i>0; k--) 
    //逆序求解In-1,In-2,……,I2,I1
    { h(xix0)=c(exi,xi+1)+q(xi+1)*I[i+1]+(1-ρ(exi,xi+1)*I[i+1]) *h(xi+1x0);
    //假设ρ(e■),q(xi+1)为已知量
          cmp=ρ(exi,xi+1)* h(xix0)-q(xi);
          if(cmp>0)  I[i]=1;
         else       I[i]=0;
         }
}
main( )  
{ While(1)
    {  select cluster heads and form clusters;
           for(each cluster)
                   {FindTheMAPath(int chID,SensorNode cnodes[n]);     //求得MA的迁移路径
         AdaptiveFusion(int *x);
    //求得各节点的融合开关
               for(i=1; i<n; i++)
                   {  CopeWithSenseDate(x[i],I[i]);
    //处理ID为x[i]的节点的感知数据,并根据I[i]值自适
    应数据融合
           send the data to the sink node;
                    }
            }
     }
}
2 仿真结果与分析
    本文采用NS-2(Network Simulation version2)对AF-LEACH进行仿真,它是一种可扩展的、容易配置的和可编程的事件驱动网络仿真引擎。在仿真过程中,比较了LEACH、MA-LEACH(Mobile Agent LEACH)和AF-LEACH三种路由协议。LEACH中簇成员节点将数据分别发送给簇头,然后由簇头一起将所有数据进行融合,簇头负担过重;MA-LEACH中MA按照能量开销最小的路由到感知节点进行本地处理,然后将融合后的数据发送至簇头;AF-LEACH根据数据融合的开销和节能增益,对簇内各节点进行自适应数据融合。
    在100 m×100 m的区域内随机部署100个节点,节点一旦部署将不再移动。基站位于(50 m,175 m),簇头节点创建MA后,将其封装在数据包中发送出去,MA遍历簇内所有节点后返回簇头节点。模拟实验参数如表1。

    由图1和图2可以看出,比较LEACH协议、MA-LEACH协议和AF-LEACH协议,它们的节点存活时间依次增加,能耗依次减少。原因在于,相对于LEACH,MA-LEACH、AF-LEACH避免了由大量的感知数据传输而导致的能量消耗,并且移动Agent计算模式把数据融合的过程分散到簇内每个节点上,这样减少了簇头节点的能量消耗,推迟了节点的死亡时间;相对于MA-LEACH,AF-LEACH的优势是当有些节点之间的相关性较小时,即数据融合节省的能量小于数据融合能量开销时,就不进行数据融合,也就是自适应数据融合,这样就减少了节点的能耗,延长了整个网络的存活时间。

    LEACH协议是基于分簇的典型协议,本文针对它的不足提出了一种新的路由协议AF-LEACH。该协议明确利用数据的相关性,根据数据融合的能量开销和所带来的节能增益,对传感器节点采集的数据进行自适应的数据融合。经仿真结果表明,改进后的AF-LEACH降低节点的能量消耗,进而延长网络的生命周期。
参考文献
[1] 王培东,李海东,徐妍.基于移动Agent的LEACH协议的研究与改进[J].通信技术,2009,42(9):151-153.
[2] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005.
[3] LUO H, LUO J, DAS S K et al. Energy efficient routing  with adaptive data fusion in sensor networks[C]. 2005.CSE UTA:Technical Report,2005.
[4] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless  micro sensor networks:Proc.of the 33rd Annual Hawaii Int’ l Conf.on System Sciences,Maui,2000[C].IEEE Computer Society,2000:3005-3014.
[5] TAO Xianping. Research on internet based mobile Agent  technology and application [D].Nanjing: Nanjing University,  2001.
[6] 胡海峰,杨震.无线传感器网络中基于移动代理的自适应数据融合路由算法[J].电子与信息学报,2008,30(9):2254-2258.
[7] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application specific protocol architecture for wireless micro sensor networks[J]. IEEE Trans on Wireless Comm, 2002,1(4):660-670.

继续阅读>>