張 蕾,謝楊梅

（1.銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 銅陵 2440001；2.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

一種支持移動(dòng)Sink的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議

張 蕾1,謝楊梅2

（1.銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 銅陵 2440001；2.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

節(jié)能是無(wú)線傳感器網(wǎng)絡(luò)路由算法設(shè)計(jì)的一個(gè)核心問(wèn)題。針對(duì)TTDD算法的不足，提出一種利用K-means聚類來(lái)構(gòu)建層次路由的算法，并減少因sink移動(dòng)的路由重建而造成的能量浪費(fèi)。仿真結(jié)果表明該算法比TTDD更能節(jié)省能耗。

無(wú)線傳感器網(wǎng)絡(luò);路由協(xié)議;多匯聚節(jié)點(diǎn)

無(wú)線傳感器網(wǎng)絡(luò) （Wireless Sensor Network，WSN）中的sink節(jié)點(diǎn)可分為固定sink節(jié)點(diǎn)和移動(dòng)sink節(jié)點(diǎn)。固定sink節(jié)點(diǎn)無(wú)法移動(dòng)，只能在原地持續(xù)性地收集數(shù)據(jù)，需要每隔一段時(shí)間便將源節(jié)點(diǎn)的數(shù)據(jù)傳送給提出查詢的sink節(jié)點(diǎn)。該方式一般用于特定點(diǎn)的監(jiān)測(cè)，數(shù)據(jù)傳輸路徑較為固定。但是這樣會(huì)使得位于傳輸路徑上的節(jié)點(diǎn)能量快速消耗，其他節(jié)點(diǎn)的能量無(wú)法充分利用，造成傳輸路徑中斷。移動(dòng)sink節(jié)點(diǎn)的位置會(huì)經(jīng)常改變，常用于移動(dòng)目標(biāo)的追蹤和實(shí)時(shí)性的監(jiān)控。sink節(jié)點(diǎn)的移動(dòng)會(huì)導(dǎo)致路由的改變，sink節(jié)點(diǎn)在每一次移動(dòng)都必須通過(guò)flooding來(lái)重建路由，導(dǎo)致flooding過(guò)度泛濫，無(wú)形中大量消耗節(jié)點(diǎn)的能量。

針對(duì)sink節(jié)點(diǎn)的移動(dòng)導(dǎo)致網(wǎng)絡(luò)的flooding泛濫問(wèn)題，文獻(xiàn)[1]中提出了雙層數(shù)據(jù)分發(fā)TTDD模型，該方法是根據(jù)源節(jié)點(diǎn)的位置將網(wǎng)絡(luò)劃分為α×α大小的網(wǎng)格，并在交叉點(diǎn)附近找尋最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。TTDD中假定源節(jié)點(diǎn)固定，所有節(jié)點(diǎn)通過(guò)GPS知道自己的位置信息，只有部分移動(dòng)sink節(jié)點(diǎn)不知道。當(dāng)某個(gè)sink節(jié)點(diǎn)需要數(shù)據(jù)信息時(shí)，會(huì)以flooding方式查詢離本地最近的轉(zhuǎn)發(fā)節(jié)點(diǎn)。由于Sink節(jié)點(diǎn)的flooding被限制在一固定方格內(nèi)，因此可避免flooding擴(kuò)散至整個(gè)網(wǎng)絡(luò)。查詢消息會(huì)先經(jīng)過(guò) IA（Immediate Agent）在經(jīng) PA（Primary Agent）到達(dá)轉(zhuǎn)發(fā)節(jié)點(diǎn)，IA是一離Sink節(jié)點(diǎn)最近的1-hop節(jié)點(diǎn)，負(fù)責(zé)將數(shù)據(jù)直接回傳給sink節(jié)點(diǎn)，當(dāng)sink節(jié)點(diǎn)發(fā)生移動(dòng)，會(huì)從鄰居節(jié)點(diǎn)中重新選擇最近的1-hop節(jié)點(diǎn)作為IA。PA為sink所處單元內(nèi)的節(jié)點(diǎn)，負(fù)責(zé)將查詢消息直接傳給本單元的轉(zhuǎn)發(fā)節(jié)點(diǎn)。當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)收到查詢信息時(shí)，按照單元邊長(zhǎng)查詢算法對(duì)其他單元的轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送查詢消息，知道到達(dá)源節(jié)點(diǎn)為止，之后源節(jié)點(diǎn)會(huì)根據(jù)傳輸?shù)穆窂交貍鲾?shù)據(jù)到sink節(jié)點(diǎn)。雖然TTDD提出了解決移動(dòng)sink以及移動(dòng)時(shí)造成的flooding泛濫問(wèn)題。但其本身也存在一些缺點(diǎn)，利用單元邊長(zhǎng)查詢算法將通知信息泛濫的范圍局限在較小的格子內(nèi)，但由于TTDD是針對(duì)每一個(gè)源節(jié)點(diǎn)建立一網(wǎng)格，因此當(dāng)源節(jié)點(diǎn)數(shù)量較多時(shí)，容易增加傳輸復(fù)雜度，以及雖然將flooding的范圍縮小在格中，但依舊會(huì)造成區(qū)域內(nèi)不必要的能量浪費(fèi)。本文針對(duì)TTDD的缺點(diǎn)，利用K-means聚類提出一種新的路由算法，希望可進(jìn)一步改善消耗問(wèn)題。

1 傳感器網(wǎng)絡(luò)模型和初始拓?fù)浣Y(jié)構(gòu)

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)隨機(jī)部署在一個(gè)矩形監(jiān)測(cè)區(qū)域中，區(qū)域中sink節(jié)點(diǎn)的位置和數(shù)目是可變的。算法首先通過(guò)K-means聚類算法建立初始分層路由，層中的上層節(jié)點(diǎn)管理下層節(jié)點(diǎn)。這樣可以減少當(dāng)sink節(jié)點(diǎn)移動(dòng)時(shí)，重復(fù)發(fā)出通知消息所造成的泛濫，因?yàn)樗韪牡穆窂絻H局限在少數(shù)節(jié)點(diǎn)上。

節(jié)點(diǎn)分成4個(gè)簇，聚類操作完成后，每個(gè)簇會(huì)產(chǎn)生各自的質(zhì)心節(jié)點(diǎn)。在每個(gè)簇內(nèi)尋找離質(zhì)心節(jié)點(diǎn)最近和最遠(yuǎn)的節(jié)點(diǎn)，共8個(gè)節(jié)點(diǎn)。分別以4個(gè)最近的節(jié)點(diǎn)與質(zhì)心節(jié)點(diǎn)間的距離為半徑畫4個(gè)圓，篩選未包含在這4個(gè)圓中節(jié)點(diǎn)，已包含在這4個(gè)圓內(nèi)的節(jié)點(diǎn)所屬簇不變。將篩選出來(lái)的節(jié)點(diǎn)與各簇所產(chǎn)生的最遠(yuǎn)的16個(gè)節(jié)點(diǎn)分別進(jìn)行距離計(jì)算，之后進(jìn)行簇合并，即加入與其距離最近的節(jié)點(diǎn)所屬的簇。接下來(lái)，將4個(gè)質(zhì)心節(jié)點(diǎn)的x，y坐標(biāo)分別加總求平均，獲得一個(gè)新的坐標(biāo)。尋找離該坐標(biāo)最近的一個(gè)節(jié)點(diǎn)作為第0層的轉(zhuǎn)發(fā)節(jié)點(diǎn)（L0），原有的4個(gè)質(zhì)心節(jié)點(diǎn)作為第2層的轉(zhuǎn)發(fā)節(jié)點(diǎn)(L1)。L0負(fù)責(zé)記錄4個(gè)L1的位置與轉(zhuǎn)發(fā)的數(shù)據(jù)信息。L1節(jié)點(diǎn)將簇ID通過(guò)廣播賦予所管轄簇內(nèi)的節(jié)點(diǎn)。每一層的轉(zhuǎn)發(fā)節(jié)點(diǎn)只需負(fù)責(zé)其下層節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)。圖1中顯示了經(jīng)過(guò)第一次K-means聚類后無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)洹?/p>

圖1 第一次聚類后的傳感器網(wǎng)絡(luò)拓?fù)?/p>

2 無(wú)線傳感器網(wǎng)絡(luò)路由算法

2.1 查詢請(qǐng)求和數(shù)據(jù)的傳遞

和TTDD算法一樣，源節(jié)點(diǎn)不是被動(dòng)等待sink節(jié)點(diǎn)的查詢請(qǐng)求。其會(huì)一開(kāi)始就主動(dòng)尋找離它最近的轉(zhuǎn)發(fā)節(jié)點(diǎn)，并將其自身的位置和數(shù)據(jù)信息復(fù)制給轉(zhuǎn)發(fā)節(jié)點(diǎn)。轉(zhuǎn)發(fā)節(jié)點(diǎn)收到信息后會(huì)將該信息轉(zhuǎn)發(fā)給它的上一層轉(zhuǎn)發(fā)節(jié)點(diǎn)。

當(dāng)sink節(jié)點(diǎn)需要數(shù)據(jù)信息時(shí)，會(huì)首先向離其最近的一個(gè)節(jié)點(diǎn)發(fā)送一個(gè)消息，收到該消息的節(jié)點(diǎn)會(huì)回復(fù)一個(gè)消息，告知其所屬簇的ID，以此判斷該sink節(jié)點(diǎn)所在的簇。接著sink節(jié)點(diǎn)會(huì)以廣播方式查詢離本地最近的轉(zhuǎn)發(fā)節(jié)點(diǎn)。該廣播信息只在sink節(jié)點(diǎn)所在簇內(nèi)進(jìn)行，若發(fā)現(xiàn)不同簇的節(jié)點(diǎn)，信息不會(huì)繼續(xù)向下傳遞，待找到離sink節(jié)點(diǎn)最近的轉(zhuǎn)發(fā)節(jié)點(diǎn)后，信息將停止傳播。之后，sink節(jié)點(diǎn)便向轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送數(shù)據(jù)請(qǐng)求，若sink節(jié)點(diǎn)與源節(jié)點(diǎn)隸屬于同一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，由于一開(kāi)始源節(jié)點(diǎn)已經(jīng)將其信息復(fù)制到轉(zhuǎn)發(fā)節(jié)點(diǎn)中，sink節(jié)點(diǎn)可以清楚知道源節(jié)點(diǎn)的位置，便可以開(kāi)始進(jìn)行數(shù)據(jù)傳遞。若當(dāng)下的轉(zhuǎn)發(fā)節(jié)點(diǎn)中無(wú)源節(jié)點(diǎn)信息時(shí)，則往上一層尋找。

2.2 sink節(jié)點(diǎn)移動(dòng)后路由的選擇和更新

由于sink節(jié)點(diǎn)的移動(dòng)，其位置改變后就需要進(jìn)行路由更新。本文對(duì)sink節(jié)點(diǎn)的移動(dòng)分為簇內(nèi)移動(dòng)和簇間移動(dòng)兩種情況。當(dāng)sink節(jié)點(diǎn)移動(dòng)后，會(huì)搜索離其最近的一個(gè)節(jié)點(diǎn)，這里我們將sink節(jié)點(diǎn)未移動(dòng)時(shí)，原有路由路徑中離其最近的一個(gè)節(jié)點(diǎn)稱為代理節(jié)點(diǎn)。移動(dòng)后的sink節(jié)點(diǎn)在找到最近的節(jié)點(diǎn)后，會(huì)判斷該節(jié)點(diǎn)與之前的代理節(jié)點(diǎn)的簇ID是否相同，若相同，表示移動(dòng)的并非太遠(yuǎn)，則將該節(jié)點(diǎn)設(shè)置為新的代理節(jié)點(diǎn)。新路由只需包含由新的代理節(jié)點(diǎn)到舊的代理節(jié)點(diǎn)間的路徑。這樣既可以保持不中斷的傳輸又可以避免重新廣播。若sink節(jié)點(diǎn)發(fā)現(xiàn)所獲得新節(jié)點(diǎn)的簇ID與舊的代理節(jié)點(diǎn)的簇ID不同，表示sink節(jié)點(diǎn)已經(jīng)移動(dòng)到了一個(gè)新的簇中，則必須通過(guò)廣播重建路由，轉(zhuǎn)發(fā)節(jié)點(diǎn)也要跟著改變。

2.3 轉(zhuǎn)發(fā)節(jié)點(diǎn)的服務(wù)數(shù)量和層的更新

在傳輸?shù)倪^(guò)程中，由于sink節(jié)點(diǎn)與源節(jié)點(diǎn)的數(shù)量并非固定為1，再加上轉(zhuǎn)發(fā)節(jié)點(diǎn)本身能量有限，因此，當(dāng)其數(shù)量增加時(shí)，容易使得轉(zhuǎn)發(fā)節(jié)點(diǎn)超載(over-load)并快速消耗轉(zhuǎn)發(fā)點(diǎn)本身的能量，因此我們?cè)O(shè)定每一層的轉(zhuǎn)發(fā)節(jié)點(diǎn)最多只能服務(wù) 3個(gè)sink節(jié)點(diǎn)的要求，若轉(zhuǎn)發(fā)點(diǎn)接收到超過(guò)的請(qǐng)求信息時(shí)，將插入新的層來(lái)減少負(fù)載。假設(shè)每一個(gè)L1能服務(wù)的sink節(jié)點(diǎn)數(shù)為 n個(gè)(n為一個(gè)服務(wù)上限)，當(dāng)接收到第n+1個(gè)信息時(shí)，將自動(dòng)建立新的層，重復(fù)一開(kāi)始初始的步驟，建立下一層的轉(zhuǎn)發(fā)節(jié)點(diǎn)L2，并更改每一個(gè)簇的ID和其儲(chǔ)存的信息，每一個(gè)層的轉(zhuǎn)發(fā)點(diǎn)，只負(fù)責(zé)并記錄下一層 4個(gè)轉(zhuǎn)發(fā)點(diǎn)的位置，因此當(dāng)產(chǎn)生新的sink節(jié)點(diǎn)要求或移動(dòng)時(shí)，其flooding的范圍將被局限在當(dāng)前的簇內(nèi)，并不需要再對(duì)所有節(jié)點(diǎn)進(jìn)行廣播，如此可將低整體能耗。

本文雖然采用分層來(lái)分散能耗，但由于 sink節(jié)點(diǎn)的數(shù)量會(huì)可能會(huì)隨著時(shí)間增減，因此在插入層后，當(dāng)sink節(jié)點(diǎn)的數(shù)量減少時(shí)，其原本所插入的層將隨著時(shí)間增加而導(dǎo)致不斷插入層。但由于每個(gè)節(jié)點(diǎn)本身的能量非常小，再加上極少進(jìn)行能量補(bǔ)充，因此一般而言，雖然隨著時(shí)間增加，插入的層數(shù)有可能不斷累積，但通常在尚未累積到一定的層數(shù)，其能量就消耗完畢。再者，插入層重新建立轉(zhuǎn)發(fā)節(jié)點(diǎn)只為了讓其它sink節(jié)點(diǎn)可以找到其它轉(zhuǎn)發(fā)點(diǎn)，避免集中在同一個(gè)身上，即使插入很多層，只是在這個(gè)區(qū)域內(nèi)創(chuàng)造更多轉(zhuǎn)發(fā)點(diǎn)，而原本超過(guò)服務(wù)上限的節(jié)點(diǎn)一樣能繼續(xù)傳輸，只是不再接收新的要求信息。 而當(dāng)sink節(jié)點(diǎn)離開(kāi)后，原則上服務(wù)的數(shù)量應(yīng)下降了，但重點(diǎn)是比起其它節(jié)點(diǎn)，它本身的能量還是已經(jīng)消耗過(guò)了，因此若插入其它層，則可避免快速消耗此轉(zhuǎn)發(fā)節(jié)點(diǎn)的能量，可更有效利用其它節(jié)點(diǎn)。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 仿真環(huán)境與參數(shù)

使用Java語(yǔ)言編寫模擬程序?qū)Ρ疚乃岢龅乃惴ê蚑TDD進(jìn)行性能分析。200個(gè)節(jié)點(diǎn)隨機(jī)分布在200m×200m的平面區(qū)域內(nèi)，sink節(jié)點(diǎn)與源節(jié)點(diǎn)開(kāi)始各預(yù)設(shè) 1個(gè)，轉(zhuǎn)發(fā)節(jié)點(diǎn)的服務(wù)數(shù)量都為 3個(gè)，sink節(jié)點(diǎn)初始位置平均分布，并隨機(jī)在網(wǎng)絡(luò)節(jié)點(diǎn)范圍內(nèi)移動(dòng)，移動(dòng)速度為0.5 m/s。每個(gè)節(jié)點(diǎn)傳送與接收能量消耗與文獻(xiàn)[1]中的設(shè)置一樣，每個(gè)節(jié)點(diǎn)傳輸和接收消耗的能量分別為0.66W和0.395W。

3.2 仿真結(jié)果

對(duì)本文方法與TTDD在不同條件下進(jìn)行的能耗比較，其能量計(jì)算的對(duì)象為在執(zhí)行的時(shí)間內(nèi)，針對(duì)傳感器網(wǎng)路中所有節(jié)點(diǎn)其數(shù)據(jù)接收與傳送所消耗能量的總合，因?yàn)閿?shù)據(jù)傳送為節(jié)點(diǎn)中能耗最多的部分。

圖2 不同sink與源節(jié)點(diǎn)數(shù)的能耗

3.2.1 不同數(shù)量源節(jié)點(diǎn)與sink節(jié)點(diǎn)的能耗比較 針對(duì)不同數(shù)量的源節(jié)點(diǎn)與sink節(jié)點(diǎn)進(jìn)行能耗測(cè)試，執(zhí)行的時(shí)間為200秒，結(jié)果為算法執(zhí)行50次后的消耗均值。如圖2所示，本文方法在不同sink和源節(jié)點(diǎn)下，其能耗均優(yōu)于TTDD。從圖 2中可以看出，一開(kāi)始由于兩種算法均須進(jìn)行全域廣播，因此能耗上大致相同，而隨著時(shí)間與sink節(jié)點(diǎn)和源節(jié)點(diǎn)的數(shù)量的增加，整體的能耗曲線就大幅拉開(kāi)，其可能的原因在于TTDD是根據(jù)每一個(gè)源節(jié)點(diǎn)去設(shè)定網(wǎng)格進(jìn)行傳輸，因此當(dāng)源節(jié)點(diǎn)數(shù)量增加時(shí)，無(wú)形中增加其傳輸?shù)膹?fù)雜度，造成不必要的能量消耗。

3.2.2 不同節(jié)點(diǎn)數(shù)下的能耗比較

圖3 不同節(jié)點(diǎn)數(shù)的能耗

圖3為本文方法與TTDD在不同節(jié)點(diǎn)下的能耗比較，實(shí)驗(yàn)中，分別隨機(jī)部署 200、300、400、500個(gè)節(jié)點(diǎn)，從圖3中可以發(fā)現(xiàn)，一開(kāi)始這兩種方法所消耗的能量相差不遠(yuǎn)，但隨著節(jié)點(diǎn)數(shù)的增加，消耗能量開(kāi)始上升，但本文方法所消耗的能量始終少于TTDD，當(dāng)節(jié)點(diǎn)數(shù)愈大時(shí)，此現(xiàn)象愈趨明顯。

3.2.3 不同負(fù)載下的能耗比較 針對(duì)每一個(gè)轉(zhuǎn)發(fā)點(diǎn)所能服務(wù)的sink節(jié)點(diǎn)數(shù)量進(jìn)行比較，實(shí)驗(yàn)的環(huán)境為節(jié)點(diǎn)數(shù)200個(gè)，sink節(jié)點(diǎn) 為 20個(gè)，源節(jié)點(diǎn) 1個(gè)，轉(zhuǎn)發(fā)點(diǎn)服務(wù)量分別為1~5，在3種不同負(fù)載的數(shù)據(jù)集下進(jìn)行測(cè)試。由圖4可以發(fā)現(xiàn)，服務(wù)數(shù)量為1-3時(shí)，整體的平均能耗呈現(xiàn)微微下滑，但服務(wù)點(diǎn)數(shù)超過(guò)3之后，卻又開(kāi)始緩慢上升。因此我們的方法設(shè)每個(gè)轉(zhuǎn)發(fā)點(diǎn)最多服務(wù)的sink節(jié)點(diǎn)數(shù)為3。從這個(gè)實(shí)驗(yàn)我們可以看出分層路由的確可以降低能量的消耗。

圖4 不同Sink節(jié)點(diǎn)服務(wù)數(shù)的能耗

4 結(jié)論

支持移動(dòng)sink的無(wú)線傳感器網(wǎng)絡(luò)中，sink節(jié)點(diǎn)每進(jìn)行一次移動(dòng)，均需要重建路由。如果頻繁地重建路由，不僅造成不必要的能量消耗，而且大量的廣播消息容易造成網(wǎng)絡(luò)風(fēng)暴。針對(duì)上述問(wèn)題，本文提出一個(gè)結(jié)合聚類與分層路由概念的傳輸方式，用來(lái)解決因不斷重建路徑所消耗的問(wèn)題，利用轉(zhuǎn)發(fā)節(jié)點(diǎn)的方法來(lái)管理眾多節(jié)點(diǎn)，并適合插入層以降低轉(zhuǎn)發(fā)點(diǎn)的負(fù)載，進(jìn)而解決移動(dòng)sink所造成的泛洪問(wèn)題。本文所提出的方法與文獻(xiàn)中所提出的TTDD方法相比，能有效降低整體能耗，延長(zhǎng)無(wú)線傳感網(wǎng)路的生命時(shí)間。

[1]YE Fan,LUO Hai-yun,CHENG J,et al.A two-tier data dissemination model for large-scale wireless sensor networks[M].Proc of the 8th Annual International Conference on Mobile Computing and Networking.New York:ACM Press,2002:148-159.

[2]Hornsberger J,Shoja G C,Grid Routing:Designing for Reliability in Wireless Sensor Networks[C].Proceedings of the International Wireless Communications and Mobile Computing Conference,2006:281-286.

[3]Lin J,Chou P L,Chou C F,HCDD:Hierarchical Cluster-Based Data Dissemination in Wireless Sensor Networks with Mobile Sink[C].Proceedings of the International Wireless Communications and Mobile Computing Conference,2006:1189-1194.

TP 393

A

1674-1102(2011)03-0019-03

2011-04-29

安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目（kj2011z379,kj2011z378）;安徽省高校省級(jí)優(yōu)秀青年人才基金項(xiàng)目（2011SQRL146，2011SQRL162）；池州學(xué)院自然科研項(xiàng)目（2010ZR010）。

張蕾(1980－)，女，安徽銅陵人，銅陵學(xué)院數(shù)學(xué)與計(jì)算機(jī)系講師，碩士,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)路由算法；謝楊梅(1979-),女,安徽池州人，池州學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系講師,碩士,主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

[責(zé)任編輯：曹懷火]