一種基于分簇的優(yōu)化定向擴散路由協(xié)議

梁小宇，劉 泉，劉新華

(武漢理工大學(xué)信息工程學(xué)院，湖北武漢430070)

隨著微電子技術(shù)、傳感器技術(shù)及通信技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展迅猛。但由于無線傳感器網(wǎng)絡(luò)具有硬件資源和電源容量有限、以數(shù)據(jù)為中心、自組織、多跳路由、動態(tài)拓撲、節(jié)點數(shù)量眾多且分布密集等特點，許多現(xiàn)有的路由協(xié)議都不適用于它，特別是大規(guī)模無線傳感器網(wǎng)絡(luò)。在現(xiàn)有的路由協(xié)議中，以數(shù)據(jù)為中心、具有良好擴展性的定向擴散算法較適合于大規(guī)模無線傳感器網(wǎng)絡(luò)［1］，但由于定向擴散算法主要依賴耗能大的平面泛洪來建立路由，導(dǎo)致其在大規(guī)模無線傳感器網(wǎng)絡(luò)中消耗能量更為嚴重，基于此，筆者在定向擴散算法的基礎(chǔ)上提出了一種改進的基于分簇的定向擴散路由協(xié)議。該協(xié)議是一種利用分簇來簡化網(wǎng)絡(luò)拓撲、抑制泛洪傳播產(chǎn)生的冗余消息，從而節(jié)約能量，實現(xiàn)能源有效性的定向擴散路由協(xié)議。

1 定向擴散路由協(xié)議

定向擴散路由(directed diffusion routing，DDR)是一種經(jīng)典的以數(shù)據(jù)為中心的路由機制［2］。定向擴散(directed diffusion，DD)是一種以數(shù)據(jù)為中心的路由協(xié)議。匯節(jié)點向所有傳感器節(jié)點發(fā)送其嗜好(通過分配不同屬性值來表示不同任務(wù)的描述符)，每個傳感器節(jié)點在收到嗜好后保存在各自的緩存中。每個嗜好項包含一個時間標(biāo)簽域和若干個梯度域，按成本最小化和能量自適應(yīng)原則引導(dǎo)數(shù)據(jù)擴散的方向。當(dāng)一個嗜好傳遍整個網(wǎng)絡(luò)后，從源節(jié)點即嗜好所在區(qū)域的傳感器節(jié)點，到匯節(jié)點之間的梯度就建立起來了。一旦源節(jié)點采集到嗜好所需的數(shù)據(jù)，便將其沿著該嗜好的梯度路徑傳輸數(shù)據(jù)到匯節(jié)點或基站。其中，源節(jié)點采集的數(shù)據(jù)首先在本地采用數(shù)據(jù)融合技術(shù)進行整合，然后在網(wǎng)上傳輸。

顯然，定向擴散路由建立時需要一個嗜好擴散的泛洪傳播［3］，以及一個探測消息的泛洪傳播來加強路徑，形成梯度。泛洪產(chǎn)生的過剩消息會增加鏈路層的開銷，增加沖突概率，同時也會造成網(wǎng)絡(luò)擁塞。在大規(guī)模無線傳感器網(wǎng)絡(luò)中，這種額外的開銷會嚴重影響網(wǎng)絡(luò)的性能。因此，如何改進定向擴散算法中這些固有的缺陷使其能適用于大規(guī)模傳感器網(wǎng)絡(luò)是筆者研究的重點。

2 CBODD原理

CBODD是利用分簇［4］思想提高定向擴散的能源有效性的無線傳感器網(wǎng)絡(luò)路由協(xié)議。通過分簇來簡化網(wǎng)絡(luò)拓撲及減少泛洪中的冗余消息來達到提高網(wǎng)絡(luò)能源有效性的目的，使之能適用于大規(guī)模無線傳感網(wǎng)絡(luò)［5］。

2.1 分簇算法

筆者采用一種基于被動分簇算法［6］的分簇機制，通過定向擴散協(xié)議本身的泛洪傳播來建立網(wǎng)絡(luò)拓撲。因此不需要額外的控制信息(通過泛洪傳播)來建立或維護網(wǎng)絡(luò)拓撲，僅需在原有的包結(jié)構(gòu)中加入一個與簇相關(guān)的信息結(jié)構(gòu)來實現(xiàn)路由的建立與維護［7－8］。

該被動分簇算法的思想是僅當(dāng)網(wǎng)絡(luò)中有數(shù)據(jù)通信要求時才在網(wǎng)絡(luò)中建立分簇網(wǎng)絡(luò)拓撲，且網(wǎng)絡(luò)拓撲的建立與維護都在本地完成，不需要單獨的控制命令以節(jié)省能量開銷。分簇策略中最重要的是簇頭選舉機制和網(wǎng)關(guān)節(jié)點的選擇機制，簇頭選舉采用“先聲明者勝”的選舉機制，網(wǎng)關(guān)節(jié)點的選擇則是根據(jù)網(wǎng)絡(luò)健壯性和能源有效性之間平衡的原則來確定選擇機制。

2.2 路由的建立與維護

CBODD路由的建立由網(wǎng)絡(luò)中Sink節(jié)點發(fā)起，當(dāng)節(jié)點分布完成后，網(wǎng)絡(luò)處于初始狀態(tài)，如果之后沒有數(shù)據(jù)傳輸要求，則網(wǎng)絡(luò)保持初始狀態(tài)，由于形成分簇的網(wǎng)絡(luò)拓撲由Sink節(jié)點發(fā)起，分簇的網(wǎng)絡(luò)拓撲形成以后只有當(dāng)網(wǎng)絡(luò)拓撲受到損害或無法維持下去時，網(wǎng)絡(luò)才會重新回到初始狀態(tài)，等待Sink節(jié)點的下一次傳輸要求來重新建立網(wǎng)絡(luò)拓撲并形成由源節(jié)點到Sink節(jié)點的路由。

整個CBODD路由協(xié)議的建立基于分簇的基礎(chǔ)，主要分為3個階段:擴散階段、建立階段和路徑加強階段。圖1描述了CBODD路由建立的完整過程。

(1)擴散階段。當(dāng)Sink節(jié)點廣播嗜好時，若網(wǎng)絡(luò)處于初始狀態(tài)(圖1(a))，則網(wǎng)絡(luò)拓撲隨嗜好在網(wǎng)絡(luò)中泛洪傳播而建立起來(圖1(b))，同時建立起從源節(jié)點到Sink節(jié)點的網(wǎng)絡(luò)梯度(圖1(d));當(dāng)網(wǎng)絡(luò)已經(jīng)處于成簇狀態(tài)時，則嗜好僅沿簇首擴散(圖1(c))，建立從源節(jié)點到Sink節(jié)點的網(wǎng)絡(luò)梯度(圖1(d))。

(2)建立階段。當(dāng)源節(jié)點采集到與嗜好匹配的數(shù)據(jù)時，源節(jié)點把數(shù)據(jù)發(fā)送給自己的簇首節(jié)點，簇首節(jié)點通過網(wǎng)關(guān)節(jié)點向多個相鄰的簇首節(jié)點發(fā)送數(shù)據(jù)，Sink節(jié)點可能收到多個路徑的相同數(shù)據(jù)(圖1(d))。中間的簇首節(jié)點收到其他簇首節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)后，首先查詢嗜好列表的表項。如果沒有匹配的嗜好表項就丟棄數(shù)據(jù);如果存在響應(yīng)的嗜好表項，則檢查與該嗜好對應(yīng)的保存最近轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)據(jù)緩沖池。若其中有與接收到的數(shù)據(jù)匹配的副本，說明已轉(zhuǎn)發(fā)過該數(shù)據(jù)，可避免出現(xiàn)傳輸環(huán)路而丟棄這個數(shù)據(jù);否則，檢查該嗜好表項中的鄰居節(jié)點信息。對于轉(zhuǎn)發(fā)的數(shù)據(jù)，數(shù)據(jù)緩沖池保留一個副本，并記錄轉(zhuǎn)發(fā)時間。

圖1 CBODD路由建立過程

(3)路徑加強階段。節(jié)點在收到從源Sink節(jié)點發(fā)來的數(shù)據(jù)后，啟動建立到源節(jié)點的加強路徑，后續(xù)數(shù)據(jù)將沿著加強路徑以較高的速率進行傳輸(圖1(e))。

3 協(xié)議的實現(xiàn)

3.1 CBODD的實現(xiàn)機制

利用NS2所提供的網(wǎng)絡(luò)路由應(yīng)用編程接口［9］來實現(xiàn)基于定向擴散協(xié)議的CBODD協(xié)議。網(wǎng)絡(luò)應(yīng)用編程接口提供了一種過濾器API，利用API可以將設(shè)計的模塊與定向擴散內(nèi)核連接起來［10］。在CBODD協(xié)議的實現(xiàn)過程中，對NS2中的定向擴散協(xié)議作如下修改:

(1)原定向擴散協(xié)議包結(jié)構(gòu)中增加與簇相關(guān)信息;

(2)增加一個優(yōu)先級比梯度過濾器高的分簇過濾器，分簇過濾器的主要功能是實現(xiàn)網(wǎng)絡(luò)拓撲的建立與維護。實現(xiàn)CBODD路由協(xié)議實際上主要是設(shè)計分簇過濾器。

3.2 CBODD的實現(xiàn)過程

在NS2中利用網(wǎng)絡(luò)應(yīng)用編程接口設(shè)計實現(xiàn)一個過濾器分為兩步:第一步是初始化操作;第二步是返回處理。初始化操作包括創(chuàng)建定向擴散路由類;建立分簇過濾器，用來過濾進入定向擴散路由中的數(shù)據(jù)包。

返回處理是對接收到的嗜好包進行處理，這是設(shè)計分簇過濾器的關(guān)鍵。其詳細算法如下:

Void ClusterFilter::recv(Message*msg，handle h)

{//嗜好消息過濾后轉(zhuǎn)發(fā);否則丟棄該包

bool bForward=true;

static int iHeaderCount=0;//簇首計數(shù)器

if(!msg－＞new_message){丟棄這個消息;

return;}

if(msg－ ＞last_hop==LOCALHOST_ADDR)

{獲取本節(jié)點當(dāng)前狀態(tài);

將與簇相關(guān)的信息填入嗜好消息中;}

else//否則嗜好消息來自其他節(jié)點

{提取嗜好包中與簇相關(guān)的信息;

獲取本節(jié)點當(dāng)前狀態(tài);

switch(本節(jié)點當(dāng)前狀態(tài))

{case NS_INITIAL://節(jié)點為初始態(tài)

if(嗜好來自簇首預(yù)備態(tài)的節(jié)點)

{置本節(jié)點當(dāng)前態(tài)為普通節(jié)點狀態(tài);

bForward=false;}

else{if(嗜好來自簇首節(jié)點)

{保存該簇首信息;iHeaderCount++;

bForward=false;}

else{置本節(jié)點當(dāng)前態(tài)為簇首預(yù)備態(tài);

將與簇相關(guān)信息填入嗜好消息;

啟動該節(jié)點簇首選取機制;}}break;

case NS_HEADER_READY:

if(嗜好來自簇首預(yù)備態(tài)的節(jié)點)

{if(該嗜好比本節(jié)點發(fā)的嗜好早)

{中斷該節(jié)點簇首選取機制;

置本節(jié)點當(dāng)前態(tài)為普通節(jié)點態(tài);}}

else{if(嗜好來自簇首節(jié)點)

{中斷該節(jié)點簇首選取機制;

置本節(jié)點當(dāng)前態(tài)為普通節(jié)點態(tài);}}

bForward=false;//丟棄該包break;

case NS_GATEWAY_READY:

if(嗜好來自網(wǎng)關(guān)預(yù)備態(tài)的節(jié)點)

{保存預(yù)備網(wǎng)關(guān)信息至預(yù)備網(wǎng)關(guān)表;

據(jù)網(wǎng)關(guān)機制決定本節(jié)點是否成為網(wǎng)關(guān)節(jié)點;

if(選定本節(jié)點為網(wǎng)關(guān)節(jié)點)

{置本節(jié)點當(dāng)前態(tài)為網(wǎng)關(guān)節(jié)點態(tài);

將與簇相關(guān)信息填入嗜好消息;}

else{置本節(jié)點當(dāng)前態(tài)為普通節(jié)點態(tài);

bForward=false;//丟棄該包}}

else{if(嗜好來自網(wǎng)關(guān)節(jié)點)

{保存網(wǎng)關(guān)信息至網(wǎng)關(guān)列表;

據(jù)網(wǎng)關(guān)機制決定本節(jié)點是否為網(wǎng)關(guān)節(jié)點;

if(選定本節(jié)點為網(wǎng)關(guān)節(jié)點)

{置本節(jié)點當(dāng)前態(tài)為網(wǎng)關(guān)節(jié)點態(tài);

將與簇相關(guān)信息填入嗜好消息中;}

else{置本節(jié)點為普通節(jié)點狀態(tài);

bForward=false;}}

else{bForward=false;}}break;

case NS_HEADER:

if(嗜好來自網(wǎng)關(guān)節(jié)點)

{將與簇相關(guān)的信息填入嗜好消息中;}

else{bForward=false;//丟棄該包}break;

case NS_GATEWAY:

if(嗜好來自網(wǎng)關(guān)節(jié)點)

{將與簇相關(guān)的信息填入嗜好消息中;}

Else{bForward=false;//丟棄該包}break;case NS_ORDINARY:

if(嗜好來自簇首節(jié)點)

{if(簇首不屬于現(xiàn)存的簇首)

{保存該簇首信息;iHeaderCount++;}

if(iHeaderCount＞=2)

{置本節(jié)點當(dāng)前狀態(tài)為網(wǎng)關(guān)預(yù)備狀態(tài);

將與簇相關(guān)信息填入嗜好消息中;}

else{bForward=false;//丟棄該包}}

else{bForward=false;//丟棄該包}break;}}

if(bForward)//將嗜好消息往下轉(zhuǎn)發(fā)

((DiffusionRouting*)dr)－＞

sendMessageToNext(msg，h);}

3.3 CBODD協(xié)議性能分析

在一個節(jié)點隨機分布、無限大的無線傳感器網(wǎng)絡(luò)區(qū)域中取一小塊區(qū)域(X×Y m2)為例來分析，在該區(qū)域內(nèi)隨機分布了N個節(jié)點。

首先考慮最壞即節(jié)點密度最大情況下，簇首節(jié)點的覆蓋半徑為R，兩簇首間距為R，則轉(zhuǎn)發(fā)節(jié)點的個數(shù)為:

因分簇而減小的消息比率為:

因分簇而減小的消息比率為:

假設(shè)該區(qū)域為1 000 m×1 000 m，R=250 m，則轉(zhuǎn)發(fā)節(jié)點在密度最大情況下共有56個，而在平均密度情況下共有21個，因此如果在該區(qū)域內(nèi)有1 000個節(jié)點的話，則可以抑制超過94.4%的轉(zhuǎn)發(fā)消息數(shù)。

4 仿真試驗結(jié)果及分析

在NS－2.27中通過改變仿真參數(shù)實現(xiàn)實際無線傳感器網(wǎng)絡(luò)的模擬。分別對每種情境下傳統(tǒng)的定向擴散路由協(xié)議和基于分簇的定向擴散路由協(xié)議進行仿真，并對所獲得的仿真數(shù)據(jù)進行統(tǒng)計。設(shè)定節(jié)點的發(fā)送功率為0.660 W，節(jié)點的接收功率為0.395W，同時假設(shè)節(jié)點偵聽與休眠狀態(tài)的能量消耗功率均為0。

能量有效性試驗結(jié)果如圖2所示。在圖2中可以看到，隨著網(wǎng)絡(luò)規(guī)模擴大(網(wǎng)絡(luò)中節(jié)點數(shù)增加)，DD與CBODD的平均消耗能量均呈上升趨勢，然而，CBODD的平均消耗能量要比DD低得多。結(jié)果表明，CBODD利用分簇來抑制泛洪傳播的冗余消息提高能量有效性效果顯著。網(wǎng)絡(luò)平均延遲比較結(jié)果如圖3所示。隨著網(wǎng)絡(luò)規(guī)模擴大，DD協(xié)議與CBODD協(xié)議的平均延遲均有所上升，但DD協(xié)議增長很快，即在節(jié)點數(shù)增加的情況下，由于泛洪傳播冗余消息的影響，平均延遲顯著增大，這表明，CBODD協(xié)議采用分簇機制來簡化網(wǎng)絡(luò)拓撲，不僅不會增加網(wǎng)絡(luò)平均延遲，相反會使網(wǎng)絡(luò)延遲性更好。

圖2 DD與CBODD能量有效性比較

圖3 DD與CBODD網(wǎng)絡(luò)平均延遲比較

［1］A l－ KARAKI JN，KAMAL A E.Routing techniques in wireless sensor networks:a survey［J］.IEEEWireless Comm，2004(11):6 －28.

［2］INTANAGONWIWAT C，GOVINDAN R，ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks［C］//Proceedings of ACM MobiCom.Boston:MA，2000:56 －67.

［3］Y IY，GERLA M，KWON T J.Efficient flooding in ad hoc networks using on－demand(passive)cluster formation［C］//Proc of the 3rd ACM MobiHoc.Lausanne:［s.n.］，2002:217 －225.

［4］L IANG X Y，LIU Q .A new model and route protocol of cluster－ b ased wireless sensor network［J］.Computational Intelligence and Industrial Application，2004(12):28－30.

［5］S HELTMAI T，MOUFTAH H.A comparative study of on－demand and cluster－based routing prototols in MANETs［C］//Proceedings of IEEE IPCCCWorkshop on EWCN.Arizona:［s.n.］，2003:291 －295.

［6］劉 泉，梁小宇.一種基于被動分簇算法的能源有效無線傳感器網(wǎng)絡(luò)模型［J］.計算機工程與應(yīng)用，2007，43(16):142 －145.

［7］MANJESSHWAR A，GRAWAL D P.TEEN:a protocol for enhanced efficiency in wireless sensor networks［C］//Proc of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001:2009－2015.

［8］Q IAN Y，ZHOU J F，CHEN K S.Prolonging the lifetime of wireless sensor network viamultihop clustering［C］//NEW2AN.［S.l.］:［s.n.］，2006:118 －129.

［9］S ILVA F，HEIDEMANN J，GOVINDAN R.Network routing application programmer's interface(API)and walk through 9.0.1 ［R］.LOS Angeles:Information Sciences Institute，USC，2002.

［10 周琴，李臘元.基于雙簇頭的無線傳感器網(wǎng)絡(luò)多跳路由協(xié)議［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2010，32(2):202－205.