文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2011)07-123-04
摘 要: 如何有效地使用傳感器節(jié)點(diǎn)的能量以延長(zhǎng)WSN的生存時(shí)間,一直是WSN路由協(xié)議研究的重點(diǎn)?;?a class="innerlink" href="http://ihrv.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)能耗,延長(zhǎng)網(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ò)能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期是無線傳感器網(wǎng)絡(luò)研究的核心問題。數(shù)據(jù)融合算法利用感知數(shù)據(jù)的相關(guān)冗余性來減少傳輸?shù)臄?shù)據(jù)量以達(dá)到節(jié)能的目的。但在許多WSN的應(yīng)用場(chǎ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á)到延長(zhǎng)無線傳感器網(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ā)送一條長(zhǎng)度為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é)議的基本思想簡(jiǎn)述為以下三點(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 (ρ(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);
//假設(shè)ρ(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);
//求得各節(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×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)的能耗,延長(zhǎng)了整個(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)而延長(zhǎng)網(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’ 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.