張 蕾,謝楊梅

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

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

張 蕾1,謝楊梅2

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

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

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

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

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

1 傳感器網(wǎng)絡(luò)模型和初始拓撲結(jié)構(gòu)

在無線傳感器網(wǎng)絡(luò)中，節(jié)點隨機部署在一個矩形監(jiān)測區(qū)域中，區(qū)域中sink節(jié)點的位置和數(shù)目是可變的。算法首先通過K-means聚類算法建立初始分層路由，層中的上層節(jié)點管理下層節(jié)點。這樣可以減少當(dāng)sink節(jié)點移動時，重復(fù)發(fā)出通知消息所造成的泛濫，因為所需更改的路徑僅局限在少數(shù)節(jié)點上。

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

圖1 第一次聚類后的傳感器網(wǎng)絡(luò)拓撲

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

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

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

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

2.2 sink節(jié)點移動后路由的選擇和更新

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

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

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

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

3 實驗結(jié)果及分析

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

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

3.2 仿真結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)論

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

[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

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

張蕾(1980－)，女，安徽銅陵人，銅陵學(xué)院數(shù)學(xué)與計算機系講師，碩士,主要研究方向為無線傳感器網(wǎng)絡(luò)路由算法；謝楊梅(1979-),女,安徽池州人，池州學(xué)院數(shù)學(xué)與計算機科學(xué)系講師,碩士,主要研究方向為智能信息處理。

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