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

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

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

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

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

    LEACH協(xié)議是基于分簇的典型協(xié)議，本文針對(duì)它的不足提出了一種新的路由協(xié)議AF-LEACH。該協(xié)議明確利用數(shù)據(jù)的相關(guān)性，根據(jù)數(shù)據(jù)融合的能量開銷和所帶來的節(jié)能增益，對(duì)傳感器節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行自適應(yīng)的數(shù)據(jù)融合。經(jīng)仿真結(jié)果表明，改進(jìn)后的AF-LEACH降低節(jié)點(diǎn)的能量消耗，進(jìn)而延長網(wǎng)絡(luò)的生命周期。
參考文獻(xiàn)
[1] 王培東，李海東，徐妍．基于移動(dòng)Agent的LEACH協(xié)議的研究與改進(jìn)[J]．通信技術(shù)，2009，42(9):151-153.
[2] 孫利民，李建中，陳渝,等．無線傳感器網(wǎng)絡(luò)[M]．北京：清華大學(xué)出版社，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] 胡海峰，楊震．無線傳感器網(wǎng)絡(luò)中基于移動(dòng)代理的自適應(yīng)數(shù)據(jù)融合路由算法[J]．電子與信息學(xué)報(bào)，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.