摘  要:    如何有效地使用傳感器節(jié)點的能量以延長WSN的生存時間,一直是WSN路由協議研究的重點?；?a class="innerlink" href="http://ihrv.cn/tags/LEACH" title="LEACH" target="_blank">LEACH，提出了一種新的路由協議AF-LEACH，AF-LEACH根據數據融合的能量開銷和所帶來的節(jié)能增益，對傳感器節(jié)點采集的數據進行自適應的數據融合。仿真實驗表明，與LEACH協議以及在各節(jié)點都進行數據融合的MA-LEACH[1]協議相比，AF-LEACH在降低節(jié)點能耗，延長網絡壽命等方面上有了顯著提高。
關鍵詞: 無線傳感器網絡； LEACH； 數據融合； 移動代理； 網絡生存時間

    無線傳感器網絡WSN(Wireless Sensor Network)可以定義為部署在監(jiān)控區(qū)域內的大量傳感器節(jié)點所組成的無線網絡。該網絡能夠協作地實時監(jiān)測、采集和處理節(jié)點分布區(qū)域內的各種環(huán)境或監(jiān)測對象的信息,并將處理后的數據傳送到網絡中的特定位置[2]。在WSN中,節(jié)點的電池能量和通信帶寬等資源均十分有限，因此如何有效地利用有限資源、降低網絡能耗、延長網絡生命周期是無線傳感器網絡研究的核心問題。數據融合算法利用感知數據的相關冗余性來減少傳輸的數據量以達到節(jié)能的目的。但在許多WSN的應用場合中，數據融合的能量開銷是不能忽略不計的，例如圖像數據融合開銷和數據傳輸開銷已經非常接近[3]。
    LEACH[4]（Low Energy Adaptive Clustering Hierarchy）是低功耗自適應分層路由算法,是WSN中最早提出的分簇路由協議。該算法通過等概率地隨機循環(huán)選取簇頭,其他各節(jié)點根據接收到的來自簇頭的信號強度進行集群分組。LEACH的執(zhí)行過程是周期性的，為達到節(jié)省能量的目的，每輪由簇的建立階段和穩(wěn)定工作兩個階段組成。但這種算法沒有考慮到節(jié)點測量數據之間存在的相關冗余性，不論數據之間的相關性大還是小，都進行數據融合，然而當數據相關性小時，這樣不僅沒有減少傳輸的數據量，反而還額外增加了融合開銷，以致增加了網絡的能耗，縮短了網絡的生命周期。
    LEACH協議中的簇采用C/S(客戶機/服務器)計算模式，它把數據發(fā)送到簇頭節(jié)點進行融合處理，這不適合簇組織結構的分布式環(huán)境。而MA-LEACH采用的基于移動Agent(MA[5])的分布式計算模式是把處理代碼移動到本地節(jié)點去處理數據，其所具有的優(yōu)勢非常適合用于簇組織結構。MA-LEACH協議中的數據收集方式是：MA從簇頭出發(fā),按照一定的路由在簇內各節(jié)點上遷移，每遷移到一個節(jié)點都將其攜帶的數據與該節(jié)點采集的數據融合,最后將所有的數據發(fā)送至簇頭。MA-LEACH將MA與LEACH結合，有效地減少傳輸中的數據量，從而減少了傳輸能耗，但該算法也沒有考慮到數據之間的相關冗余性。
    AFMR(Adaptive Fusion Mobile Agent Routing)[6]算法根據移動代理在無線傳感器網絡各節(jié)點遷移過程中傳輸能量和融合能量的開銷以及數據融合能帶來的節(jié)能增益，對移動代理遷移到各節(jié)點時是否執(zhí)行數據融合進行自適應調整，使得MA在路由過程中收集、融合相關節(jié)點測量數據的同時,保持總的能量開銷接近最優(yōu)。
    在WSN中對傳感器節(jié)點進行數據融合后，減少了傳輸能量,但同時增加了融合開銷。針對這一矛盾，AFMR算法根據數據融合算法的能量開銷和節(jié)能增益，對每個節(jié)點是否進行數據融合運算進行了自適應調節(jié)。
    針對上述問題，在已有LEACH等協議的基礎上，提出了一種新的路由協議AF-LEACH(Adaptive Fusion LEACH)，通過在簇內對各節(jié)點采集的數據是否執(zhí)行融合進行自適應調整來節(jié)省節(jié)點能耗，以達到延長無線傳感器網絡生命周期的目的。

1 基于自適應數據融合的LEACH協議
1.1 基本定義和概念
    無線傳感器網絡中的一個簇可以用一個無向加權全連通圖G=(V,E)來表示，V是簇中所有傳感器節(jié)點的集合，E使簇中兩個節(jié)點之間可以直接通信。假設頂點v∈V代表簇中的一個傳感器節(jié)點，邊euv=(u,v)∈E代表頂點u和v所對應的傳感器節(jié)點能夠直接通信。
    LEACH采用的能量消耗公式是無線傳感器網絡中通用的一階無線電模式[7]，傳感器節(jié)點在距離d發(fā)送一條長度為l bit消息所消耗的能量為：

　設MA由ID、路由算法、數據緩存、處理測量數據代碼組成，其中數據緩存中包含部分融合的簇成員節(jié)點的測量數據。
1.2 基于自適應數據融合的LEACH路由協議
    基于自適應數據融合的LEACH協議的基本思想是：在LEACH的簇結構形成后，網絡的能耗主要體現在感知數據的傳輸和融合上。
　傳輸能耗與MA的遷移路由有關，計算MA的路由是TSP問題，本文采用最近鄰居算法，從簇頭出發(fā)，在所有的成員節(jié)點中尋找權值(傳輸能量與融合能量之和)最小的邊對應的節(jié)點加入到路徑解中，然后再在沒有訪問過的節(jié)點中尋找與當前權值相比最小的節(jié)點，加入到路徑解中，依次類推，直至所有的成員節(jié)點都被訪問完，路徑解中最后一個節(jié)點為簇頭節(jié)點。
    數據融合能夠減少傳輸的數據量，從而減少傳輸能量，但數據融合本身又能導致能量的開銷，因此當節(jié)省的傳輸能量大于數據融合開銷時，進行數據融合對于網絡節(jié)能才是有益的，反之，則會增加網絡能耗。由此分析得出，對簇內成員節(jié)點應該動態(tài)地進行數據融合(自適應數據融合)。當在該節(jié)點進行數據融合能節(jié)省網絡能耗時，就進行數據融合(融合計算開關置1)；否則，不進行(融合計算開關置0)。在某一節(jié)點進行數據融合后所節(jié)省的能量實際是，按照計算好的MA遷移路由，未融合的感知數據從該節(jié)點傳輸到簇頭的能量與融合后的數據從該節(jié)點傳輸到簇頭節(jié)點的能量之差。差值與數據融合的能量進行比較，大于0時，在該節(jié)點進行數據融合，否則，不進行。因此簇中某一節(jié)點是否進行數據融合還得在遷移路徑上后面的節(jié)點開關值確定之后才能確定，于是對應于遷移路徑上的節(jié)點順序，各節(jié)點的融合開關值是逆序計算的。
　　簇內各成員節(jié)點的數據收集和處理過程是:簇頭節(jié)點按照簇內成員節(jié)點的數目，生成一個TDMA時隙表，簇頭節(jié)點根據MA的遷移路由中各節(jié)點的順序依次為每個成員分配通信時隙，成員節(jié)點只能在其特定的時隙內與由簇頭創(chuàng)建的MA進行通信，此時簇內其他成員節(jié)點關閉通信模塊以節(jié)省能量。然后，簇頭節(jié)點的MAE開始創(chuàng)建并派遣MA，MA從簇頭出發(fā)，按照已經計算好的遷移路由和各節(jié)點的融合計算開關值，MA依次遷移到各節(jié)點，當融合計算開關為1(0)時，MA攜帶的數據緩存中的數據與相應節(jié)點采集的數據進行(不進行)數據融合，最后MA攜帶著融合處理后的數據返回簇頭，完成一次數據收集。
    基于自適應數據融合的LEACH協議的基本思想簡述為以下三點：
    (1) 計算MA的遷移路由(子函數1)
    根據最近鄰居算法計算MA的遷移路徑：從簇頭出發(fā)，依次取權值（傳輸能量與融合能量之和）最小的邊對應的點加入當前解中直至形成回路解。
    (2) 計算自適應數據融合開關值(子函數2)
    假設通過子函數1求得的MA遷移路由為{x0,x1,x2,…,xk,xk+1,…，xn-1,x0}(其中x0為簇頭)，未融合的感知數據從某一節(jié)點傳輸到簇頭的能量與融合后的數據從該節(jié)點傳輸到簇頭節(jié)點的能量作差，其差值和數據融合的能量進行比較，大于0時，在該節(jié)點進行數據融合，融合計算開關置1；否則，不進行數據融合，融合計算開關置0。由于節(jié)點xk必須知道它后面的節(jié)點xk+1,…，xn-1的融合計算開關值,才能計算出它自己的，故逆序求解In-1，In-2，…，I2，I1，亦即得出該簇內哪些節(jié)點進行融合計算，哪些不進行。
    (3) 進行簇內所有成員節(jié)點的數據收集（主函數）
    調用子函數1，求出MA的遷移路徑{x0,x1,x2,…,xk,xk+1,…，xn-1,x0}；
    調用子函數2，根據子函數1的遷移路徑求出簇內各節(jié)點的融合計算開關值In-1，In-2，…，I2，I1；
    簇頭節(jié)點派遣MA，收集節(jié)點xi（i=1,2，…，n-1）的感知數據，根據Ii=1（或0）的值融合（或不融合）節(jié)點xi的感知數據與MA數據緩存中的數據，最后所有的數據匯總至簇頭節(jié)點。
    傳感器節(jié)點的數據結構定義如下：
    typedef struct node
    {    int nodeID;      
                                             //節(jié)點ID
    int visitedFlag;   
        //是否被訪問，1為已經被MA訪問過，0為未訪問
    }SensorNode;
     基于自適應數據融合的LEACH的算法如下：
    void  FindTheMAPath(int chID,SensorNode cnodes[n])
         //計算MA的遷移路徑的子函數，chID表示簇頭ID
    {
    int temp=0;
    //暫存遷移路徑上某個節(jié)點在權值矩陣對應的列下標，
       以便在該列下標值對應的行進行下一個節(jié)點的查找
    int x[n];
        //將遷移路徑上節(jié)點的ID依次存入一維數組x[n]
         i=0;
        //數組x[n]的下標變量
         x[0]=chID;
        //MA遷移路徑上的第一節(jié)點為簇頭節(jié)點，即MA
        由簇頭節(jié)點派遣出去
    do{  DataType  minweight=∞;
       //DataType是感知數據類型，給最小權值變量賦初值    for(j=1;j<n; j++)
        //從所有的簇成員節(jié)點中找出距離ID為i的節(jié)點            最近的節(jié)點
         {  curID=getcurID( );
        //獲取第j個簇成員節(jié)點的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從節(jié)點xi到節(jié)點xj的單位數據傳
                 輸能量
    if (&rho;(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，&hellip;&hellip;，I2，I1
    { h(xix0)=c(exi,xi+1)+q(xi+1)*I[i+1]+(1-&rho;(exi,xi+1)*I[i+1]) *h(xi+1x0)；
    //假設&rho;(e■)，q(xi+1)為已知量
　　        cmp=&rho;(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);
    //求得各節(jié)點的融合開關
               for（i=1; i<n; i++）
                   {  CopeWithSenseDate(x[i]，I[i]);
    //處理ID為x[i]的節(jié)點的感知數據，并根據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中簇成員節(jié)點將數據分別發(fā)送給簇頭，然后由簇頭一起將所有數據進行融合，簇頭負擔過重；MA-LEACH中MA按照能量開銷最小的路由到感知節(jié)點進行本地處理，然后將融合后的數據發(fā)送至簇頭；AF-LEACH根據數據融合的開銷和節(jié)能增益，對簇內各節(jié)點進行自適應數據融合。
    在100 m&times;100 m的區(qū)域內隨機部署100個節(jié)點，節(jié)點一旦部署將不再移動?；疚挥?50 m,175 m)，簇頭節(jié)點創(chuàng)建MA后，將其封裝在數據包中發(fā)送出去，MA遍歷簇內所有節(jié)點后返回簇頭節(jié)點。模擬實驗參數如表1。

    由圖1和圖2可以看出,比較LEACH協議、MA-LEACH協議和AF-LEACH協議,它們的節(jié)點存活時間依次增加,能耗依次減少。原因在于,相對于LEACH，MA-LEACH、AF-LEACH避免了由大量的感知數據傳輸而導致的能量消耗，并且移動Agent計算模式把數據融合的過程分散到簇內每個節(jié)點上，這樣減少了簇頭節(jié)點的能量消耗，推遲了節(jié)點的死亡時間；相對于MA-LEACH，AF-LEACH的優(yōu)勢是當有些節(jié)點之間的相關性較小時，即數據融合節(jié)省的能量小于數據融合能量開銷時，就不進行數據融合，也就是自適應數據融合，這樣就減少了節(jié)點的能耗，延長了整個網絡的存活時間。

    LEACH協議是基于分簇的典型協議，本文針對它的不足提出了一種新的路由協議AF-LEACH。該協議明確利用數據的相關性，根據數據融合的能量開銷和所帶來的節(jié)能增益，對傳感器節(jié)點采集的數據進行自適應的數據融合。經仿真結果表明，改進后的AF-LEACH降低節(jié)點的能量消耗，進而延長網絡的生命周期。
參考文獻
[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&rsquo; 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.