基于Anycast的無線傳感器網(wǎng)絡(luò)模型

李魁峰，張以峰，姜 洋，張大成，趙 明

（1．沈陽炮兵學(xué)院 ，遼寧 沈陽 110162;2．解放軍65134部隊(duì)，遼寧 瓦房店 116302）

0 引言

隨著無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）規(guī)模的不斷擴(kuò)大，通常在網(wǎng)絡(luò)中布設(shè)多個(gè)基站，在考慮路由建立之前，首先需要進(jìn)行基站選擇，傳感器節(jié)點(diǎn)將數(shù)據(jù)傳送至性能最優(yōu)的基站是傳感器網(wǎng)絡(luò)多基站路由協(xié)議研究的主要問題。任播（Anycast）技術(shù)可以有效解決節(jié)點(diǎn)與多基站通信問題。Anycast作為一種網(wǎng)絡(luò)通信服務(wù)模型，最初誕生于IPv6網(wǎng)絡(luò)。在RFC1546中首次提出Anycast模型，對(duì)Anycast的描述僅僅是一個(gè)實(shí)驗(yàn)性的服務(wù)［1］。按照定義，當(dāng)客戶發(fā)送報(bào)文時(shí)，Anycast組組員可以同時(shí)接收該Anycast地址的數(shù)據(jù)包，網(wǎng)絡(luò)盡力而為地將該報(bào)文傳送到這些組員中的至少一個(gè)，且最好是一個(gè)。

研究學(xué)者對(duì)IPv6中的Anycast技術(shù)進(jìn)行改進(jìn)，提出了一些基于Anycast服務(wù)的WSNs路由協(xié)議。在文獻(xiàn)［2］中，對(duì)AODV協(xié)議進(jìn)行改進(jìn)來支持Anycast服務(wù)，當(dāng)有數(shù)據(jù)需要傳輸時(shí)，節(jié)點(diǎn)使用Anycast 技術(shù)發(fā)起路由建立來尋找最適合的目標(biāo)節(jié)點(diǎn)。Intanagonwiwat C等人提出WSNs Anycast路由協(xié)議SARP［3］，SARP算法思想很簡單:選擇最小跳數(shù)路徑將數(shù)據(jù)傳送至最近的基站（base station）或Sink node。SARP不需要知道全局的網(wǎng)絡(luò)拓?fù)湫畔?，是一種分布式路由協(xié)議，但SARP總是選擇跳數(shù)最小的路徑，將導(dǎo)致該路徑上的節(jié)點(diǎn)能耗過快，從而縮短網(wǎng)絡(luò)生存期。隨之，Thepvilojanapong N等人［4］提出了一種層次樹 Anycast路由協(xié)議（HAR），HAR建立以Sink為根節(jié)點(diǎn)的信息樹，傳感器節(jié)點(diǎn)根據(jù)信息樹將數(shù)據(jù)傳送到Sink。Koziuk M等人也給出類似思想［5］:基于通信樹的無線傳感器（制動(dòng)器）網(wǎng)絡(luò)Anycast路由協(xié)議（TBA）用于解決路由查詢傳播問題。HAR和TBA其本質(zhì)和SARP一樣都是選擇最小跳數(shù)路徑，同樣存在能量消耗不均衡的問題。LEACH（low-energy adaptive clustering hierarchy）協(xié)議［6］是第一個(gè)提出數(shù)據(jù)聚合的層次路由協(xié)議。為平衡網(wǎng)絡(luò)各節(jié)點(diǎn)的能耗，簇頭周期性通過隨機(jī)選舉產(chǎn)生。但該協(xié)議仍采用一跳通信，雖然傳輸時(shí)延小，但要求離基站較遠(yuǎn)的節(jié)點(diǎn)采用大功率通信會(huì)導(dǎo)致生存時(shí)間較短，擴(kuò)展性差，而且頻繁簇頭選舉引發(fā)的通信量耗費(fèi)了大量能量。

本文將Anycast通信模型的思想應(yīng)用到無線傳感器網(wǎng)絡(luò)中，所提的模式與當(dāng)前存在的算法也有所不同，基站根據(jù)路徑代價(jià)模型建立Anycast樹，數(shù)據(jù)沿著樹形結(jié)構(gòu)被轉(zhuǎn)發(fā)至最近的一個(gè)目標(biāo)節(jié)點(diǎn)，而不是在TCP/IP協(xié)議中，節(jié)點(diǎn)根據(jù)Anycast地址發(fā)送到指定的Anycast組中，本文不需要支持TCP/IP協(xié)議的運(yùn)行。

1 WSNs系統(tǒng)模型

1．1 拓?fù)淠Ｐ?/h3>

網(wǎng)絡(luò)可以被抽象為一個(gè)無向圖G（V，A），其中，V表示網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)和基站的集合，節(jié)點(diǎn)可以與基站經(jīng)一跳或多跳連通，A表示鏈路集合。記節(jié)點(diǎn)i∈V的鄰居節(jié)點(diǎn)集合為Si，i可以與Si內(nèi)的任意節(jié)點(diǎn)直接通信。大量的傳感器節(jié)點(diǎn)和多個(gè)Sink節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域，源節(jié)點(diǎn)將采集到的數(shù)據(jù)經(jīng)過一跳或多跳發(fā)送至Sink節(jié)點(diǎn)。假設(shè)普通節(jié)點(diǎn)和Sink節(jié)點(diǎn)具有以下特征:

1）所有的傳感器節(jié)點(diǎn)具有相同的初始能量，基站節(jié)點(diǎn)沒有能量限制;

2）所有節(jié)點(diǎn)都具有定位功能，節(jié)點(diǎn)可以根據(jù)接收到其他節(jié)點(diǎn)的位置信息計(jì)算通信半徑;

3）節(jié)點(diǎn)的通信半徑可以調(diào)節(jié)，節(jié)點(diǎn)可以根據(jù)與鄰居節(jié)點(diǎn)距離任意調(diào)整通信半徑;

4）節(jié)點(diǎn)和基站都是靜止的，每個(gè)節(jié)點(diǎn)具有唯一的ID號(hào)，所有的基站節(jié)點(diǎn)擁有同一個(gè)ID號(hào)。

1．2 能量模型

無線傳感器節(jié)點(diǎn)能耗因素主要有以下幾個(gè)部分:感知產(chǎn)生數(shù)據(jù)、空閑、偵聽、接收數(shù)據(jù)和發(fā)送數(shù)據(jù)。用eg為產(chǎn)生一個(gè)字節(jié)數(shù)據(jù)的能耗，es為單位時(shí)間空閑時(shí)的能耗，這兩部分的能耗對(duì)所有節(jié)點(diǎn)是相同的。節(jié)點(diǎn)接收和發(fā)送數(shù)據(jù)的能耗是節(jié)點(diǎn)能耗的主要因素，本文采用第一階無線電波能量模型［7］，驅(qū)動(dòng)發(fā)射機(jī)或接收機(jī)所需要的功率εelec=50 nJ，發(fā)射機(jī)功率增益εamp=100 pJ/bit/m2，節(jié)點(diǎn)接收一個(gè)字節(jié)的能耗為er=εelec。節(jié)點(diǎn)i發(fā)送單位字節(jié)數(shù)據(jù)到鄰居節(jié)點(diǎn)j的能耗為

其中，dij為節(jié)點(diǎn)i的通信半徑，n為路徑功耗模型參數(shù)，通常介于自由空間（d2功耗）信道模型和多經(jīng)衰落（d4功耗）信道模型之間［9］，2≤n≤4。el為節(jié)點(diǎn)偵聽信道的能耗，通過實(shí)驗(yàn)測(cè)試，偵聽信道能耗接近節(jié)點(diǎn)接收數(shù)據(jù)的能耗。Ei為節(jié)點(diǎn)i的初始能量，wi為節(jié)點(diǎn)i完成向基站發(fā)送一個(gè)字節(jié)數(shù)據(jù)的總能耗

節(jié)點(diǎn)在空閑時(shí)的能耗較小，相對(duì)于其他能耗es因素可以忽略不計(jì)，即式（2）變?yōu)?/p>

1．3 路徑選擇

WSNs路由建立是選擇滿足應(yīng)用需要的最優(yōu)路徑，本文建立一個(gè)線性組合來衡量路徑建立的代價(jià)

其中，φ為從源節(jié)點(diǎn)到前一個(gè)節(jié)點(diǎn)的路徑代價(jià)，metrici的取值范圍是（0，1），αi為metrici計(jì)算路徑代價(jià)的權(quán)值系數(shù)，根據(jù)應(yīng)用需要，在路徑建立過程中，權(quán)值系數(shù)可以相應(yīng)地改變來影響路徑代價(jià)的計(jì)算。在本文的Anycast路徑選擇中，主要考慮4部分路徑建立代價(jià):跳數(shù)、能耗、延遲和剩余能量，因此，路徑建立代價(jià)變?yōu)?/p>

其中，hopi=1，為路徑建立的跳數(shù)，wi為數(shù)據(jù)從前一個(gè)節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的能量消耗，delay為數(shù)據(jù)從前一個(gè)節(jié)點(diǎn)傳遞到當(dāng)前節(jié)點(diǎn)的時(shí)間，Ei為節(jié)點(diǎn)的剩余能量。在不同的應(yīng)用模型中，可以設(shè)置不同的權(quán)值系數(shù)。在路徑建立過程中，如果只考慮節(jié)點(diǎn)的剩余能量問題，那么權(quán)值系數(shù)（α1，α2，α3，α4）=（0，1，0，0）。路徑代價(jià)模型主要用來進(jìn)行路徑選擇。

2 Anycast路由協(xié)議

在本文Anycast路由協(xié)議中，所有Sink節(jié)點(diǎn)形成一個(gè)Anycast組，Anycast組共享同一個(gè)ID。Sink節(jié)點(diǎn)各自建立一棵樹形結(jié)構(gòu)，Sink節(jié)點(diǎn)承擔(dān)數(shù)據(jù)收集任務(wù)。傳感器節(jié)點(diǎn)加入“最近”的樹，節(jié)點(diǎn)根據(jù)式（5）最優(yōu)路徑選擇模型進(jìn)行路徑選擇。

2．1 數(shù)據(jù)包種類

在本文的Anycast路由協(xié)議中，共使用4種控制數(shù)據(jù)包，分別是HELLO數(shù)據(jù)包、路由請(qǐng)求（route request，RREQ）數(shù)據(jù)包、路由應(yīng)答（route replay，RREP）數(shù)據(jù)包和路由錯(cuò)誤（route error，RERR）返回?cái)?shù)據(jù)包。只有Sink節(jié)點(diǎn)產(chǎn)生HELLO數(shù)據(jù)包，Sink節(jié)點(diǎn)定期地向所有傳感器節(jié)點(diǎn)廣播HELLO數(shù)據(jù)包。RREQ數(shù)據(jù)包被用來進(jìn)行路由發(fā)現(xiàn)。在RREQ中新增加2個(gè)字段，子節(jié)點(diǎn)請(qǐng)求（child request，CRQ）和父節(jié)點(diǎn)請(qǐng)求（parent request，PRQ）。CRQ用來路由發(fā)現(xiàn)一個(gè)子節(jié)點(diǎn)，PRQ用來路由發(fā)現(xiàn)一個(gè)父節(jié)點(diǎn)。RREP數(shù)據(jù)包用來回答路由請(qǐng)求。當(dāng)某一節(jié)點(diǎn)發(fā)送路由請(qǐng)求至當(dāng)前節(jié)點(diǎn)時(shí)，如果當(dāng)前節(jié)點(diǎn)已經(jīng)鏈接到某一Sink節(jié)點(diǎn)，則進(jìn)行路由應(yīng)答。當(dāng)鏈路產(chǎn)生錯(cuò)誤而中斷時(shí)，節(jié)點(diǎn)產(chǎn)生RERR返回?cái)?shù)據(jù)包給父節(jié)點(diǎn)，讓父節(jié)點(diǎn)等待一段時(shí)間，節(jié)點(diǎn)進(jìn)行路由重構(gòu)。

2．2 Anycast樹

所有Sink節(jié)點(diǎn)形成一個(gè)Anycast組，Anycast組具有唯一ID（ID=0）。每個(gè)Sink節(jié)點(diǎn)建立一棵樹形Anycast樹，樹的“根”是Sink節(jié)點(diǎn)，傳感器節(jié)點(diǎn)可以從Anycast樹中得到Anycast服務(wù)。每個(gè)傳感器節(jié)點(diǎn)加入到最近的Anycast樹中，Anycast樹建立過程如下:

每個(gè)Sink節(jié)點(diǎn)或普通節(jié)點(diǎn)向它的鄰居節(jié)點(diǎn)廣播CRQ，CRQ包含Sink節(jié)點(diǎn)或普通節(jié)點(diǎn)的位置信息、Anycast組ID、路徑代價(jià)φ、下一跳節(jié)點(diǎn)ID和節(jié)點(diǎn)地址。如果CRQ來自Sink節(jié)點(diǎn)，路徑代價(jià)φ=0，下一跳節(jié)點(diǎn)ID為空。鄰居節(jié)點(diǎn)收到CRQ并且節(jié)點(diǎn)還沒有加入任何Anycast樹，節(jié)點(diǎn)接收CRQ，檢查CRQ中的 Anycast組ID，如果 Anycast組 ID=0，表示發(fā)送CRQ的節(jié)點(diǎn)已經(jīng)加入到一棵Anycast樹中，節(jié)點(diǎn)將CRQ添加到父節(jié)點(diǎn)表中，記錄CRQ中的相關(guān)信息。如果Anycast組ID不等于0，表示發(fā)送CRQ的節(jié)點(diǎn)還沒有加入到任何Anycast樹中，節(jié)點(diǎn)丟棄CRQ。

節(jié)點(diǎn)接收CRQ后，設(shè)置一個(gè)時(shí)間遞減參數(shù)，在時(shí)間過期之前，節(jié)點(diǎn)可以收到多個(gè)CRQ，節(jié)點(diǎn)根據(jù)CRQ中的路徑代價(jià)φ進(jìn)行比較，選擇一個(gè)最優(yōu)節(jié)點(diǎn)作為父節(jié)點(diǎn)，同時(shí)發(fā)送RREP進(jìn)行應(yīng)答。如果接收到多個(gè)CRQ中的路徑代價(jià)φ是相等的，則隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為父節(jié)點(diǎn)。父節(jié)點(diǎn)接收到RREP后，向子節(jié)點(diǎn)返回一個(gè)ACK消息，路徑建立成功。在無線傳感器網(wǎng)絡(luò)中，由于Sink節(jié)點(diǎn)可以直接與所有節(jié)點(diǎn)通信，通常父節(jié)點(diǎn)可以不保留子節(jié)點(diǎn)的信息，只需要子節(jié)點(diǎn)保留父節(jié)點(diǎn)的信息即可。子節(jié)點(diǎn)加入到Anycast樹后，用父節(jié)點(diǎn)ID取代下一跳節(jié)點(diǎn)ID，重新計(jì)算路徑代價(jià)φ，并用新的路徑代價(jià)φ替換原φ，節(jié)點(diǎn)更新其他相關(guān)參數(shù)，包括節(jié)點(diǎn)位置等。節(jié)點(diǎn)繼續(xù)向其他節(jié)點(diǎn)廣播CRQ直到所有節(jié)點(diǎn)都加入到Anycast樹中為止，如圖1所示。

圖1 Anycast樹建立過程Fig 1 Establishing process of Anycast trees

Anycast樹建立完成后，每個(gè)源節(jié)點(diǎn)將采集到的數(shù)據(jù)發(fā)送至父節(jié)點(diǎn)，父節(jié)點(diǎn)接收到子節(jié)點(diǎn)的數(shù)據(jù)后，沿著Anycast樹結(jié)構(gòu)繼續(xù)向上一層節(jié)點(diǎn)轉(zhuǎn)發(fā)，最終數(shù)據(jù)被傳輸至Sink節(jié)點(diǎn)。Sink節(jié)點(diǎn)對(duì)所有接收到的數(shù)據(jù)處理后，發(fā)送到網(wǎng)絡(luò)終端或其他接收裝置。

3 仿真實(shí)驗(yàn)

在本文中，通過仿真實(shí)驗(yàn)將 Anycast通信協(xié)議與LEACH進(jìn)行比較。仿真在NS—2環(huán)境中實(shí)現(xiàn)，隨機(jī)產(chǎn)生含有5個(gè)Sink節(jié)點(diǎn)和95個(gè)普通傳感器節(jié)點(diǎn)，節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的平面區(qū)域，所有節(jié)點(diǎn)的傳輸功率可以調(diào)節(jié)，在傳輸距離內(nèi)的任意2個(gè)節(jié)點(diǎn)可以互相直接通信，仿真的其他相關(guān)參數(shù)如表1所示。

表1 Anycast仿真實(shí)驗(yàn)使用的相關(guān)參數(shù)Tab 1 Related parameters used in Anycast simulation experiment

圖2和圖3分別為采用LEACH協(xié)議和本文提出的Anycast路由協(xié)議形成的路由模型。在LEACH協(xié)議形成的路由模型中，網(wǎng)絡(luò)根據(jù)距離劃分成多個(gè)分簇（cluster），在簇頭（cluster head，CH）處會(huì)造成嚴(yán)重的通信干擾。簇頭為普通節(jié)點(diǎn)，簇頭的能量消耗比較快，簇內(nèi)不斷更換簇頭，也容易使得對(duì)原簇頭所在位置失去監(jiān)控的可能性。在Anycast路由協(xié)議模型中，每個(gè)節(jié)點(diǎn)根據(jù)式（5）的路由代價(jià)算法需要加入到一棵Anycast樹中，樹根為Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)能耗消耗可以不受限制，可以有效分擔(dān)網(wǎng)絡(luò)負(fù)載。

圖2 LEACH協(xié)議模型Fig 2 Model of LEACH protocol

圖3 Anycast路由協(xié)議模型Fig 3 Model of Anycast routing protocol

當(dāng)在監(jiān)測(cè)網(wǎng)絡(luò)內(nèi)分別放置2，3，4，5，6個(gè)基站時(shí)，不同數(shù)量傳感器節(jié)點(diǎn)的網(wǎng)絡(luò)能耗和網(wǎng)絡(luò)生命期如圖4和圖5所示。

圖4 網(wǎng)絡(luò)能耗Fig 4 Energy consumption of network

圖5 網(wǎng)絡(luò)生命期Fig 5 Lifetime of network

在圖4和圖5中，隨著節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)能耗不斷增加，同時(shí)網(wǎng)絡(luò)生命期降低。當(dāng)基站數(shù)量增加時(shí)，在相同數(shù)量的節(jié)點(diǎn)下，網(wǎng)絡(luò)能耗降低，網(wǎng)絡(luò)生命期得到提高。這是因?yàn)楫?dāng)增加基站數(shù)量時(shí)，建立的Anycast樹將增多，源節(jié)點(diǎn)到達(dá)基站的路徑將縮短，所以，網(wǎng)絡(luò)能耗降低，同時(shí)延長了網(wǎng)絡(luò)生命期。隨著基站數(shù)量的增加，基站對(duì)網(wǎng)絡(luò)能耗和生命期的影響也逐漸降低。在節(jié)點(diǎn)數(shù)量為100時(shí)，當(dāng)基站數(shù)量從3個(gè)增加到6個(gè)，增加1倍，能量消耗減少33．3%，新增加的基站對(duì)基站周圍節(jié)點(diǎn)的能耗影響較大。

4 結(jié)論

基于Anycast技術(shù)，本文提出一種WSNs模型和路由協(xié)議，仿真實(shí)驗(yàn)表明:所提出的Anycast路由協(xié)議可以解決WSNs多基站通信問題，與LEACH協(xié)議相比，該協(xié)議可以有效分擔(dān)網(wǎng)絡(luò)負(fù)載。在節(jié)點(diǎn)數(shù)量為100時(shí)，當(dāng)基站數(shù)量從3個(gè)增加到6個(gè)，網(wǎng)絡(luò)能量消耗減少33．3%，網(wǎng)絡(luò)生命期得到提高。

［1］ Partridge C，Mendez T，Milliken W．RFC 1546:Host Anycasting service［Z］．IEFT，1993．

［2］ Jia W，Zhou W，Kaiser J．Efficient algorithm for mobile multicast using anycast group［C］∥IEEE Proc of Communications，2001:14－18．

［3］ Intanagonwiwat C，Lucia D D．The Sink-based Anycast routing protocol for Ad Hoc wireless sensor networks［R］．Los Angeles:USC，1999:99 －698．

［4］ Thepvilojanapong N，Y Tobe，K Sezaki．HAR:Hierarchy-based anycast routing protocol for wireless sensor networks［C］∥Proceedings of SAINT 2005，Italy，2005:204 －212．

［5］ Koziuk M，Domaszewicz J．Tree-based Anycast for wireless sensor/actuator networks［C］∥Proceedings of ICDCN 2008，2008:322－331．

［6］ Heinzelman W R，Chandrakasan A，Balakris-hnan H．Energy-efficient communication protocol for wireless micro-sensor networks［C］∥Proceedings of the Hawai International Conference on System Science，Maui，Hawai，2000:3005 － 3014．

［7］ Satapathy S S，Sarma N．TREEPSI:Tree-based energy efficient protocol for sensor information［C］∥International Conference on Wireless and Optical Communications Networks，2006:4