無線傳感器網(wǎng)絡(luò)多sink路由技術(shù)研究
2010-01-01 00:00:00徐晨曹磊章國安顧金媛
計算機應(yīng)用研究 2010年3期
摘 要:在介紹無線傳感器網(wǎng)絡(luò)路由協(xié)議的獨有特點后，給出了傳感器網(wǎng)絡(luò)多sink路由協(xié)議的分類方法，然后著重分析了當(dāng)前較為有代表性的多sink路由協(xié)議，在協(xié)議特點及其應(yīng)用范圍方面進行了研究與比較。最后，總結(jié)了多sink路由協(xié)議的研究的關(guān)鍵點及其發(fā)展趨勢。
關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); 路由協(xié)議; 多sink
中圖分類號:TP393 文獻標(biāo)志碼:A
文章編號:1001-3695(2010)03-0816-08
doi:10.3969/j.issn.1001-3695.2010.03.004
Overview of multiple sink routing protocols in wireless sensor networks
XU Chen， CAO Lei， ZHANG Guo-an， GU Jin-yuan
(School of Electronic Information， Nantong University， Nantong Jiangsu 226000， China)
Abstract:After introducing wireless sensor network routing the unique features of the agreement， this paper gave classification methods for the multi-sink sensor network routing protocol， and then focused on analysis of the current representative of the multi-sink routing protocols， the research and comparison on characteristic and their scope of application. Lastly， concluded the multi-sink routing protocols on the key points and its development trend.
Key words:wireless sensor networks; routing protocol; multiple sink
在無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)[1]中，sink節(jié)點又叫做網(wǎng)關(guān)節(jié)點，網(wǎng)絡(luò)中的傳感器節(jié)點采集環(huán)境變量并將它們傳送給sink節(jié)點，然后，sink節(jié)點通過無線方式接收各傳感器節(jié)點的數(shù)據(jù)并以有線或無線的方式將數(shù)據(jù)傳送給最終用戶計算機。 Sink是將傳感器網(wǎng)絡(luò)與現(xiàn)有的遠程通信基礎(chǔ)設(shè)施(PSTN、GSM、CDMA等)相互連接的無線裝置，也可看做是提取傳感器網(wǎng)絡(luò)信息的移動節(jié)點[2]。
隨著微機電、無線通信等關(guān)鍵支撐技術(shù)研究的持續(xù)發(fā)展，無線傳感器網(wǎng)絡(luò)的研究也進一步得到深化，無線傳感器網(wǎng)絡(luò)適用的領(lǐng)域也越發(fā)寬廣。有人適時地提出多媒體無線傳感器網(wǎng)絡(luò)的概念，以滿足人們在傳感器網(wǎng)絡(luò)平臺下對如圖像、語音，甚至視頻數(shù)據(jù)信息傳輸?shù)男枨骩3]。傳統(tǒng)傳感器網(wǎng)絡(luò)研究的重點是在能量嚴(yán)重受限的微型節(jié)點上如何實現(xiàn)簡單的環(huán)境數(shù)據(jù)(如光強、溫度、濕度等)采集、傳輸與處理，此時整個網(wǎng)絡(luò)數(shù)據(jù)速率較低，用戶對網(wǎng)絡(luò)延時、誤碼率并不敏感，但當(dāng)傳輸?shù)氖嵌嗝襟w信息時，用戶對傳輸?shù)膶崟r性、容錯性等將提出更高的要求。傳統(tǒng)的單sink網(wǎng)絡(luò)過于依賴惟一的sink節(jié)點，其實時性、可靠性等將不能滿足此類應(yīng)用的需要。
目前傳感器網(wǎng)絡(luò)的運用已經(jīng)取得一定的進展，但一般還是小規(guī)模、低密集度網(wǎng)絡(luò)模式。隨著無線傳感器網(wǎng)絡(luò)各項技術(shù)的成熟，大規(guī)模、高密度網(wǎng)絡(luò)布局將會成為可能，這時單sink節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)在能耗均衡性、可靠性等方面存在著諸多的弊端，顯得難以滿足傳感器網(wǎng)路今后發(fā)展的需求。多sink節(jié)點網(wǎng)絡(luò)架構(gòu)無疑可以較好地解決上述問題，它將越來越受到研究人員的關(guān)注。
目前，多sink傳感器網(wǎng)絡(luò)已經(jīng)出現(xiàn)一些應(yīng)用上的嘗試。在2008年初，中國南極考察隊克服低溫、高海拔和雪面極其松軟的困難，在Dome-A地區(qū)成功安裝上了由中國科學(xué)院遙感應(yīng)用研究所研發(fā)的無線傳感器網(wǎng)絡(luò)，為防止因通信故障造成的數(shù)據(jù)丟失，系統(tǒng)設(shè)計為雙基站(sink)系統(tǒng)，節(jié)點所發(fā)出的數(shù)據(jù)一方面被通信系統(tǒng)接收后傳回國內(nèi)，同時還被一臺值守系統(tǒng)接收存儲于本地，待下次考察隊到此時取回。在文獻[4]提到還用于布設(shè)于水下無線傳感器網(wǎng)絡(luò)系統(tǒng)等。這些應(yīng)用上的嘗試為多sink節(jié)點結(jié)構(gòu)網(wǎng)絡(luò)的研究工作提供了寶貴的經(jīng)驗。
1 無線傳感器網(wǎng)絡(luò)路由技術(shù)
無線傳感器網(wǎng)絡(luò)路由協(xié)議負(fù)責(zé)在sink節(jié)點與非sink節(jié)點間可靠地傳輸數(shù)據(jù)信息。路由協(xié)議的分類方法有很多種，根據(jù)路由協(xié)議采用的通信模式、路由結(jié)構(gòu)、路由建立時機、狀態(tài)維護、節(jié)點標(biāo)志和投遞方式等策略可將其分類為[5，6]單路徑路由協(xié)議和多路徑路由協(xié)議、平面路由(flat-based)和層次路由(hierarchical-based)、主動路由協(xié)議、按需路由協(xié)議、保證QoS和不保證QoS的路由協(xié)議以及整合了不止一種路由協(xié)議的混合路由協(xié)議等。
整體而言傳感器網(wǎng)絡(luò)在考慮其路由協(xié)議時，一般要考慮以下這些限制因素[6，7]:
a)節(jié)點布設(shè)。傳感器網(wǎng)絡(luò)中，節(jié)點的布設(shè)基本可以分為人工布設(shè)和隨機布設(shè)兩類。此時，節(jié)點布設(shè)的密集度將直接影響網(wǎng)絡(luò)的自組，太密集容易引起無線通信沖突，太稀疏又難免會存在監(jiān)測盲區(qū)，甚至部分節(jié)點無法接入整個網(wǎng)絡(luò)。
b)能量消耗。傳感器網(wǎng)絡(luò)中節(jié)點供電一般是微型電池，電能非常有限。對于網(wǎng)絡(luò)中每個具有感知、處理、通信能力的節(jié)點而言，每一項操作都要消耗一定的電能，而尤以通信消耗的能量最大。所以在設(shè)計一個路由算法時，要在滿足應(yīng)用要求的前提下，盡量簡化算法，使整個網(wǎng)絡(luò)獲得最大的生存周期。
c)數(shù)據(jù)報告方式。傳感器網(wǎng)絡(luò)中數(shù)據(jù)報告方式一般分為時間驅(qū)動、事件驅(qū)動、詢問驅(qū)動三種，或是它們的組合方式。時間驅(qū)動方式比較適合需要周期性監(jiān)測的應(yīng)用場合;事件驅(qū)動方式時，節(jié)點對由于特定突發(fā)事件導(dǎo)致的感知數(shù)據(jù)的變化作出快速的反應(yīng);詢問驅(qū)動方式是對基站或者網(wǎng)絡(luò)中的節(jié)點發(fā)出的詢問信息作出回應(yīng)的工作模式。很多路由算法使用了這三種方式中的兩個甚至三個，以達到網(wǎng)絡(luò)最佳工作性能。
d)節(jié)點/鏈路的同異構(gòu)性。一般傳感器網(wǎng)絡(luò)問題中，都是認(rèn)為網(wǎng)絡(luò)中所有的節(jié)點具有相同的處理、通信能力以及相同的能量，但是當(dāng)網(wǎng)絡(luò)中的節(jié)點間不是完全相同時，這時就需要重新考慮路由算法。
e)一定的容錯能力。無線通信本身易受環(huán)境的影響，加上傳感器節(jié)點常工作在較惡劣的環(huán)境中，節(jié)點失效問題也較常見，所以要想布設(shè)的傳感器網(wǎng)絡(luò)可靠地運作，就必須要求網(wǎng)絡(luò)具有一定的自動應(yīng)對突發(fā)情況的能力。
f)擴展性。傳感器網(wǎng)絡(luò)的節(jié)點一般較多，節(jié)點失效、失效節(jié)點恢復(fù)正常工作的現(xiàn)象基本是難以避免的，這樣就要求路由算法具有一定的可擴展性。另外，當(dāng)需要在原有部署網(wǎng)絡(luò)的基礎(chǔ)上擴大或減小網(wǎng)絡(luò)規(guī)模時，也要求網(wǎng)絡(luò)能在較小改造代價下完成整個網(wǎng)絡(luò)的升級工作。
g)傳輸媒質(zhì)。無線傳輸一般具有信道衰落嚴(yán)重、誤碼率高等特性，傳輸速率最多幾百kbps。傳輸媒質(zhì)是與MAC層的設(shè)計相關(guān)的，一般而言基于時分多址接入(TDMA)的方法比較節(jié)省能耗，如CSMA。
h)連通性。網(wǎng)絡(luò)連通性定義為網(wǎng)絡(luò)中各個節(jié)點可以連接的鄰節(jié)點數(shù)。傳感器網(wǎng)絡(luò)中，節(jié)點路由選擇常常依賴于其鄰節(jié)點信息，一個節(jié)點的鄰節(jié)點數(shù)直接影響路由的選擇。一般而言，網(wǎng)絡(luò)連通度越大，路由算法的選擇空間會變大，網(wǎng)絡(luò)的健壯性也越好。
i)覆蓋率。一般定義為網(wǎng)絡(luò)可以正常監(jiān)測的面積與整個目標(biāo)區(qū)域面積的百分比。對于不同的路由算法，可能網(wǎng)絡(luò)布設(shè)的初期覆蓋率還是基本相同的，但隨著各種路由在能耗、機制的不盡相同，網(wǎng)絡(luò)的覆蓋率將會發(fā)生變化，所以在選擇路由算法時要考慮到這點。
j)數(shù)據(jù)融合。傳感器網(wǎng)絡(luò)主要有三種存儲監(jiān)測數(shù)據(jù)的方式，分別是本地存儲(local storage)、外部存儲(external storage)和數(shù)據(jù)中心存儲(data-centric storage)[8，9]。
k)安全性。傳感器網(wǎng)絡(luò)本身是無線通信方式，這種開放性的網(wǎng)絡(luò)傳輸環(huán)境給網(wǎng)絡(luò)帶來了安全上的隱患。非法用戶的接入不僅會影響網(wǎng)絡(luò)的正常工作，也可能會導(dǎo)致系統(tǒng)數(shù)據(jù)的丟失與竄改，特別是現(xiàn)在基于無線傳感器網(wǎng)絡(luò)已經(jīng)開始向無線抄電能表、水表以及煤氣等民用領(lǐng)域推廣，網(wǎng)絡(luò)安全就會顯得尤為重要，而安全的路由協(xié)議是其關(guān)鍵要解決的問題。
l)服務(wù)質(zhì)量，即QoS(quality of service)。QoS的路由協(xié)議是指在路由建立時，考慮時延、丟包率等QoS 參數(shù)，即包含監(jiān)測數(shù)據(jù)的準(zhǔn)確度、實時性等。傳感器網(wǎng)絡(luò)是偏應(yīng)用的網(wǎng)絡(luò)，對于最終用戶而言，并不關(guān)心整個網(wǎng)絡(luò)的路由、數(shù)據(jù)融合等方面的具體過程，他們更關(guān)注數(shù)據(jù)的準(zhǔn)確性與實時性，所以QoS越來越被研究人員所重視。
2 無線傳感器網(wǎng)絡(luò)多sink路由協(xié)議分析
目前，單sink傳感器網(wǎng)絡(luò)路由研究已經(jīng)取得了很多喜人的成果，但它們也難免存在一些弊端，主要有以下幾方面:
a)單sink節(jié)點傳感器網(wǎng)絡(luò)無法處理sink節(jié)點的失效問題，sink節(jié)點的失效會帶來整個網(wǎng)絡(luò)的癱瘓，即整個網(wǎng)絡(luò)的可靠性較差。
b)所有數(shù)據(jù)都必須沿著惟一sink節(jié)點方向的路徑進行單跳或多跳傳送，這樣勢必會造成sink節(jié)點附近的節(jié)點能量消耗過快，嚴(yán)重影響到傳感器網(wǎng)絡(luò)的使用壽命，即網(wǎng)絡(luò)能耗嚴(yán)重失衡[10，11]。
c)文獻[11]還認(rèn)為單sink節(jié)點網(wǎng)絡(luò)一般只考慮了到達sink節(jié)點的跳數(shù)或者該路徑上進行數(shù)據(jù)傳送時的總體能量消耗，其選擇結(jié)果一般是最短路徑，而對于路徑上節(jié)點的通信能力(能量剩余情況)考慮不夠。
d)文獻[12]考慮到sink節(jié)點移動將導(dǎo)致網(wǎng)絡(luò)能耗過大與通信沖突問題。
e)單sink網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較復(fù)雜時數(shù)據(jù)融合變得過于復(fù)雜[13]，合理地增加網(wǎng)絡(luò)中的sink節(jié)點數(shù)將大大簡化數(shù)據(jù)融合的復(fù)雜度。
f)不同的用戶(sink)可能需要不同的環(huán)境變量(溫度、濕度、光強等)或者不同格式(圖像、聲音、視頻等)的數(shù)據(jù)信息，如何有效地控制網(wǎng)絡(luò)中的數(shù)據(jù)流，這些問題都可以考慮在網(wǎng)絡(luò)中布設(shè)多sink節(jié)點的方法來解決。
另外，LEACH[14]協(xié)議、PEGASIS[15]協(xié)議分簇后，簇頭節(jié)點跟sink節(jié)點是一跳直接通信的，單sink節(jié)點必將要求距其較遠的簇頭節(jié)點大功率通信，這樣不僅需要消耗過多的節(jié)點能源，且長距離傳輸所帶來的干擾問題也是不能忽視的。這時可以利用多sink的分散性，網(wǎng)絡(luò)中的簇頭節(jié)點只須將數(shù)據(jù)傳送給較近的sink節(jié)點便可較好地解決這個問題。在一些基于地理位置的路由協(xié)議(GPSR、TPGF)中，普遍存在的路由hole問題，有望在多sink節(jié)點網(wǎng)絡(luò)結(jié)構(gòu)下得到有效解決。
由此可見，多sink架構(gòu)具有穩(wěn)定性、有效性、健壯性、便于管理、能耗更均衡等優(yōu)點，多sink節(jié)點傳感器網(wǎng)絡(luò)路由極具研究價值。
2.1 多sink路由協(xié)議的分類
目前，多sink路由協(xié)議的研究工作還處于起步階段，更沒有統(tǒng)一的分類標(biāo)準(zhǔn)，除了一般傳感器網(wǎng)絡(luò)路由協(xié)議的分類方法外，可以考慮以下一些分類方法:
a)根據(jù)sink節(jié)點固定地點布設(shè)或者隨機布設(shè)，可將多sink路由協(xié)議分為固定位置布設(shè)多sink路由協(xié)議與隨機布設(shè)多sink路由協(xié)議[16]。由于sink節(jié)點數(shù)目有限，為了便于維護，也可以考慮采用人工固定放置的方式來布設(shè)sink節(jié)點。圖1即為sink節(jié)點由人工指定位置布設(shè)。
b)傳感器網(wǎng)絡(luò)中，sink節(jié)點可以運動也可以靜止，可以根據(jù)sink運動與否將多sink路由協(xié)議分為動態(tài)多sink路由協(xié)議與靜止多sink路由協(xié)議。圖2即為動態(tài)多sink傳感器網(wǎng)絡(luò)結(jié)構(gòu)。
c)根據(jù)源節(jié)點是否跟固定sink進行相互間數(shù)據(jù)通信，可以分為固定對象多sink路由協(xié)議與動態(tài)對象多sink路由協(xié)議。文獻[17]中就是動態(tài)對象多sink路由協(xié)議，該種路由協(xié)議與固定對象多sink路由協(xié)議相比具有更好的組網(wǎng)靈活性，網(wǎng)絡(luò)健壯性也較好，但組網(wǎng)操作過程較復(fù)雜。而對于基于地理位置的多sink路由策略而言[12]，則基本是固定對象多sink路由協(xié)議。
d)依據(jù)傳感器節(jié)點是否異構(gòu)或同構(gòu)，將其分為節(jié)點同構(gòu)多sink路由協(xié)議與節(jié)點異構(gòu)多sink路由協(xié)議。同構(gòu)即所有感知節(jié)點具有相同的初始能量、通信射程以及環(huán)境變量(溫度、濕度、聲波等)感知能力，即感知能力相同。在異構(gòu)多sink網(wǎng)絡(luò)中，各個sink節(jié)點可以只負(fù)責(zé)接收處理自己感興趣的感知數(shù)據(jù)，使網(wǎng)絡(luò)的管理得以簡化，但是組網(wǎng)過程相對會變得復(fù)雜。
e)Sink節(jié)點間的通信方式可以是有線方式，也可以是無線方式。有線方式將簡化sink節(jié)點間的通信過程的復(fù)雜度，提高通信的可靠性，但無線方式將使sink節(jié)點的布設(shè)更具靈活性。
f)數(shù)據(jù)融合方式，也可分為三種基本數(shù)據(jù)融合方式，即本地存儲、外部存儲和數(shù)據(jù)中心存儲，如圖3所示。但這里要注意的是傳送到多個sink節(jié)點的數(shù)據(jù)，如何適時、適地(節(jié)點)進行數(shù)據(jù)融合操作。
另外在多sink節(jié)點傳感器網(wǎng)絡(luò)中，路由考慮的重點還是各個sink間的協(xié)作，所以在路由分類時考慮最多的還是這種協(xié)作之間的差別。
2.2 多sink節(jié)點網(wǎng)絡(luò)設(shè)計問題
文獻[18]認(rèn)為網(wǎng)絡(luò)拓?fù)湓O(shè)計問題包括數(shù)據(jù)源終端與目的終端的布設(shè)位置、最大通信量要求、時延要求、可靠性要求、網(wǎng)絡(luò)設(shè)備的成本等，并討論了集中器布設(shè)問題(concentrator location problem)、終端配置問題(terminal assignment problem)、樞紐布置圖問題(terminal layout problem，即強迫最小生成樹問題)、分布式網(wǎng)絡(luò)拓?fù)洳贾脠D問題(distributed network topological layout problem)，還有骨干節(jié)點布設(shè)問題(backbone node location problem)。
文獻[19]指出PLP(plant location problem)[20]、CLP(concentrator location problem)[18，21]等所針對問題與含有多sink傳感器網(wǎng)絡(luò)節(jié)點布設(shè)的問題存在一些差異。例如，sink節(jié)點布設(shè)的變化性、sink節(jié)點與感知節(jié)點之間是通過多跳的方式進行通信的以及sink節(jié)點的能力是指其數(shù)據(jù)處理能力而不是其作為集中器時可用的端口數(shù)。文中還將大規(guī)模傳感器網(wǎng)絡(luò)中分簇問題以及sink節(jié)點的布設(shè)問題統(tǒng)稱為多sink傳感器網(wǎng)絡(luò)設(shè)計問題。sink節(jié)點的布設(shè)數(shù)目、布設(shè)位置都將直接關(guān)系著網(wǎng)絡(luò)的生存周期，每個sink節(jié)點周圍的節(jié)點由于要作為中間路由節(jié)點，一般能耗較大，它們能正常工作時間的長短直接關(guān)系著整個網(wǎng)絡(luò)的生命周期。但是網(wǎng)絡(luò)布設(shè)前，網(wǎng)絡(luò)設(shè)計者一般會先根據(jù)成本、覆蓋度等因素確定所要布設(shè)的sink節(jié)點數(shù)。文獻[19]將在知道sink節(jié)點數(shù)之后，如何部署sink節(jié)點位置的問題稱為CLB問題(best sink location)，描述了傳感器網(wǎng)絡(luò)所需最小操作時間，最后用時間約束來考慮多sink節(jié)點布設(shè)問題。文獻[22]則將網(wǎng)絡(luò)分為樹結(jié)構(gòu)，考慮各個節(jié)點在樹結(jié)構(gòu)中的級別以及每個節(jié)點的子節(jié)點數(shù)來構(gòu)建多sink節(jié)點的網(wǎng)絡(luò)拓?fù)??？傊绾螌崿F(xiàn)各個sink節(jié)點間的互相協(xié)調(diào)是關(guān)鍵。
實際應(yīng)用中，要根據(jù)具體應(yīng)用環(huán)境來設(shè)計合適的傳感器網(wǎng)絡(luò)，比如軍事應(yīng)用中，就比較適合隨機布撒sink節(jié)點的網(wǎng)絡(luò)布設(shè)方式;而像森林環(huán)境監(jiān)測等網(wǎng)絡(luò)布設(shè)面積較大的應(yīng)用中，各個sink節(jié)點固定布設(shè)于整個布設(shè)網(wǎng)絡(luò)的邊緣地帶則比較適合。總而言之，與單sink節(jié)點網(wǎng)絡(luò)初始化組網(wǎng)是由單個sink來控制的且路由整體方向固定不同的是，多sink路由一般需要整個網(wǎng)絡(luò)中的多個sink節(jié)點互相協(xié)調(diào)，以完成單sink無法有效實現(xiàn)的網(wǎng)絡(luò)應(yīng)用場合。
2.3 典型多sink路由協(xié)議分析
1)MRMS協(xié)議[16]
Chen Yue-quan等人提出MRMS (multipath routing in large scale sensor networks with multiple sink nodes)多sink節(jié)點路由協(xié)議。針對傳輸路徑選擇、高能效的動態(tài)分簇維持以及路徑切換問題，提出了一種新的基于鄰節(jié)點間距離到相應(yīng)sink的跳數(shù)以及節(jié)點剩余能量信息的路徑開銷度量算法。該協(xié)議主要分為三個部分:
a)拓?fù)浒l(fā)現(xiàn)。拓?fù)錁?gòu)建算法是參考TopDisc[23]拓?fù)浒l(fā)現(xiàn)算法，再綜合考慮鄰節(jié)點的距離到相應(yīng)sink的跳數(shù)以及節(jié)點剩余能量信息，所提出的高能效的拓?fù)錁?gòu)建算法。 TopDisc算法首先找到一批級別較高的節(jié)點(distinguished nodes)，再利用所有鄰節(jié)點信息大致構(gòu)建網(wǎng)絡(luò)的拓?fù)?。只有這些級別較高的節(jié)點才回應(yīng)拓?fù)浒l(fā)現(xiàn)探測信息，這樣就有效減少了網(wǎng)絡(luò)中的信息重疊現(xiàn)象。最后將形成以監(jiān)視節(jié)點為根的樹狀網(wǎng)絡(luò)結(jié)構(gòu)。
b)分簇維持。此階段簇內(nèi)節(jié)點輪流作為簇頭。在此過程中，每個簇內(nèi)只須維護當(dāng)前跳數(shù)以及相應(yīng)sink節(jié)點，這就意味著簇頭節(jié)點無須維護簇內(nèi)子節(jié)點信息，大大簡化了分簇維護負(fù)擔(dān)。
c)路徑重新選擇。當(dāng)原先的數(shù)據(jù)傳輸路徑能耗過多(超過門限值)以后，就重新選擇傳輸路徑甚至接收數(shù)據(jù)的sink節(jié)點。
通過實驗，該協(xié)議相較于直接洪泛、Voronoi算法以及TopDisc算法，分別延長網(wǎng)絡(luò)生存時間約3、2以及0.3倍。 MRMS協(xié)議針對大規(guī)模布設(shè)傳感器網(wǎng)絡(luò)，而分層的網(wǎng)絡(luò)架構(gòu)也更適合于此類網(wǎng)絡(luò)?？梢灶A(yù)見，多sink層次性網(wǎng)絡(luò)架構(gòu)是未來大規(guī)模傳感器網(wǎng)絡(luò)的發(fā)展方向。
2)TTDD-MS協(xié)議[12]。
Ye Fan等人考慮到sink節(jié)點移動將導(dǎo)致網(wǎng)絡(luò)能耗過大與通信沖突問題，提出雙重數(shù)據(jù)分發(fā)(two-tier data dissemination，TTDD)方法來解決高效的多個移動sink節(jié)點數(shù)據(jù)傳輸?shù)膯栴}，且此方法具有較好的可升級性。在TTDD中，每個可能的數(shù)據(jù)資源節(jié)點事先建立一個格柵，這種格柵結(jié)構(gòu)保證了移動的sink節(jié)點能通過不斷地發(fā)出洪泛詢問，持續(xù)地接收到其所在格柵的數(shù)據(jù)信息。當(dāng)傳感器節(jié)點靜止且位置已知的情況下，采用格柵的方法將會使整個網(wǎng)絡(luò)維持低的數(shù)據(jù)交疊(overhead，即節(jié)點先后收到監(jiān)控同一區(qū)域的多個節(jié)點發(fā)送的幾乎相同的數(shù)據(jù))。
TTDD基本思路為:在寬闊的目標(biāo)區(qū)域布設(shè)密集度較高的傳感器節(jié)點，這些無線射程有限的節(jié)點以多跳方式進行組網(wǎng);每個節(jié)點通過GPS或節(jié)點定位技術(shù)[24，25]獲知其自身位置。此時，移動的sink節(jié)點一般不知道其自身位置;當(dāng)有一個行為觸發(fā)(時間、事件或查詢)時，在其周圍的節(jié)點協(xié)同處理該信號，最后選擇其中一個節(jié)點作為資源節(jié)點發(fā)送數(shù)據(jù)報告;sink節(jié)點通過發(fā)送詢問信息去收集感知數(shù)據(jù)。此時，在目標(biāo)區(qū)域周圍的sink節(jié)點可能不止一個，數(shù)目還可能不斷變化。
TTDD基本步驟如下:
a)格柵構(gòu)建。一個資源節(jié)點首先將目標(biāo)平面區(qū)域劃分為一個寫單元格柵，每個格柵都是長和寬為a的正方形，其自身位于格柵的交叉點。源節(jié)點將要傳送的數(shù)據(jù)信息告知其他所有可以延伸到的格柵交叉點，這時這些交叉點又可稱為格柵中的資源分發(fā)點。此時，對于一個位置為Ls=(x， y)源節(jié)點而言，資源分發(fā)點的坐標(biāo)則為Lp=(xi，yi)。其中:
{xi=x+i#8226;a， yi=y+j#8226;a; i，j=±1，±2，±3，…}(1)
接著，每個源節(jié)點不斷將自身的位置信息Ls與單元格的邊長a告知其相鄰的四個格柵交叉點。數(shù)據(jù)傳輸?shù)姆绞绞遣捎没诘乩砦恢玫呢澙非跋蛩惴āＷ詈髷?shù)據(jù)被輸出給距離Lp最近的鄰節(jié)點。
b)雙重數(shù)據(jù)詢問與分發(fā)。TTDD基于虛擬格柵結(jié)構(gòu)，當(dāng)sink節(jié)點需要數(shù)據(jù)時，向本地區(qū)域廣播詢問信息，最終sink節(jié)點獲知鄰近數(shù)據(jù)分發(fā)點。為了控制sink節(jié)點質(zhì)詢信息的盲目傳播，還規(guī)定了最大傳播半徑。最終該鄰近數(shù)據(jù)分發(fā)節(jié)點，通過中間數(shù)據(jù)分發(fā)點建立sink節(jié)點與資源節(jié)點間的連接。一旦資源節(jié)點收到鄰近數(shù)據(jù)分發(fā)點傳輸?shù)膕ink節(jié)點的質(zhì)詢信息，便將要傳輸?shù)臄?shù)據(jù)發(fā)送給該數(shù)據(jù)分發(fā)點。
TTDD的網(wǎng)絡(luò)數(shù)據(jù)重疊量與網(wǎng)絡(luò)規(guī)模、sink節(jié)點數(shù)目以及傳感器節(jié)點的移動速率成反比，且與面向sink數(shù)據(jù)傳輸方式(SODD)[26，27]相比，格柵結(jié)構(gòu)大大簡化了數(shù)據(jù)傳輸?shù)奶幚磉^程。 但是格柵的維持過程復(fù)雜，能耗問題也是不容忽視的問題。
3)Voronoi scoping協(xié)議[28]
Henri Dubois-Ferriere等人認(rèn)為多sink傳感器網(wǎng)絡(luò)中如何限制每個sink所發(fā)出的詢問信息是個關(guān)鍵問題，于是用一個簡單實用的Voronoi scoping算法來限制每個sink節(jié)點的消息的傳播。每個sink節(jié)點的詢問信息只發(fā)送給該sink節(jié)點的Voronoi分簇中的子節(jié)點，這樣就達到了每個查詢信息將被傳送給盡量少的數(shù)據(jù)采集節(jié)點的目的。另外，該算法無須額外的通信過程去完成Voronoi分簇過程，網(wǎng)絡(luò)數(shù)據(jù)重疊程度也將不會因為網(wǎng)絡(luò)規(guī)模以及sink節(jié)點數(shù)目的增長而發(fā)生變化。
Voronoi scoping算法的幾個關(guān)鍵點包括:
a)距離度量與sink節(jié)點數(shù)據(jù)的聚集。為了讓中間節(jié)點將數(shù)據(jù)傳送給距其最近的sink節(jié)點，此處用節(jié)點間跳數(shù)來表示距離。
b)符號表示。將整個網(wǎng)絡(luò)按圖論理論表示成G=(N， E)。其中:N表示所有源節(jié)點數(shù)目m與目的節(jié)點的數(shù)目s之和，E表示一條鏈路的權(quán)重系數(shù)。用dij表示節(jié)點i與j間的最短路徑距離，則sink節(jié)點k所對應(yīng)的Voronoi分簇可以表示成
Vk={i:minj∈s di，j=di，k}(2)
c)樹生成。從sink節(jié)點發(fā)出的路由廣播包含有跳數(shù)域。廣播過程結(jié)束后，所有節(jié)點獲得其父節(jié)點以及到相應(yīng)sink節(jié)點的跳數(shù)信息，再根據(jù)這些信息反向生成數(shù)據(jù)聚合樹。與AODV相似，在數(shù)據(jù)傳輸過程中利用數(shù)據(jù)的序列號信息剔除重復(fù)數(shù)據(jù)，有效減少了數(shù)據(jù)重疊現(xiàn)象。
d)路由接入與查詢分發(fā)。查詢分發(fā)與樹結(jié)構(gòu)是截然不同的，查詢是單向的傳輸，但是一般情況下，查詢與路由廣播包是作為一個整體被發(fā)送的，Voronoi scoping算法即是采用這種方式。
該協(xié)議具有簡單的數(shù)據(jù)傳播執(zhí)行過程，且每個節(jié)點只需少量字節(jié)操作，但Voronoi分簇是其要解決的關(guān)鍵問題。
4)PAMR協(xié)議[29]
Pietro Ciciriello等人針對多sink傳感器網(wǎng)絡(luò)中，數(shù)據(jù)傳輸不同于一般傳統(tǒng)單sink網(wǎng)中數(shù)據(jù)是以多點到單點(many-to-one)方式進行傳輸，而是多點到多點(many-to-many)方式的問題，提出周期性的消息適應(yīng)路由PAMR(periodic adaptation of the message routes)，主要目的是盡量減少網(wǎng)絡(luò)連接的操作。該協(xié)議設(shè)想每個數(shù)據(jù)源節(jié)點(可能不止一個)到相應(yīng)sink節(jié)點具有相互獨立的樹狀結(jié)構(gòu)，此時，一條連接已知源節(jié)點與相應(yīng)sink的路徑將被建立。
PAMR借鑒多商品流網(wǎng)絡(luò)設(shè)計問題來解決傳感器網(wǎng)絡(luò)設(shè)計高效性、分散性問題，并提出根sink節(jié)點周期適應(yīng)路由，解決了分散性問題。適應(yīng)算法包括選擇不同鄰節(jié)點作為建立與給定sink節(jié)點連接的父節(jié)點。適應(yīng)算法的執(zhí)行由本地一個節(jié)點通過對由其鄰節(jié)點發(fā)布的信息構(gòu)成的特征矩陣q(n， s)的估值來決定。其中n是該節(jié)點的鄰節(jié)點，s是相應(yīng)sink節(jié)點，即當(dāng)sink節(jié)點s的鄰節(jié)點中q值變得最大時，節(jié)點改變其父節(jié)點。這樣，該節(jié)點便可便捷地將數(shù)據(jù)傳送給新的鄰父節(jié)點。
該協(xié)議非常適合數(shù)據(jù)量較少的傳感器網(wǎng)絡(luò)應(yīng)用場合。實驗表明，該路由協(xié)議相比于沒有適應(yīng)機制的路由可以減少50%的數(shù)據(jù)交疊，即有效減少了節(jié)點先后收到監(jiān)控同一區(qū)域的多個節(jié)點發(fā)送的幾乎相同的數(shù)據(jù)。
5)SDMR-MS協(xié)議[30]
Winston K.G. Seah等人提出一種虛擬(virtual)sink節(jié)點架構(gòu)的傳感器網(wǎng)絡(luò)模型(圖4)，目的是通過定義一組空間上變化的物理節(jié)點來減輕選擇鄰近sink節(jié)點時所造成的競爭，在此基礎(chǔ)上提出了適用于多sink的空分多路徑路由SDMR-MS(spatially-diverse multi-path routing for multi-sink)。
a)虛擬sink節(jié)點架構(gòu)。為減少多徑效應(yīng)以及信道間的沖突，數(shù)據(jù)以星放射狀(starburst)方式傳送給布設(shè)于網(wǎng)絡(luò)邊緣的sink節(jié)點，這些sink節(jié)點組成虛擬sink節(jié)點組。感知節(jié)點與sink構(gòu)成的多層次網(wǎng)絡(luò)拓?fù)湟约熬植繑?shù)據(jù)融合節(jié)點選擇，保證了網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)至少能傳送給一個sink節(jié)點。這些數(shù)據(jù)融合節(jié)點將組成一個mesh網(wǎng)絡(luò)負(fù)責(zé)將數(shù)據(jù)傳輸給相應(yīng)的sink節(jié)點。
b)多路徑數(shù)據(jù)傳輸。當(dāng)網(wǎng)絡(luò)是兩個層次時，在低層次網(wǎng)絡(luò)內(nèi)部通過健壯性較好的多路徑數(shù)據(jù)傳輸算法實現(xiàn)感知節(jié)點與本地數(shù)據(jù)融合節(jié)點間的n個路徑的連接，n可以隨著待傳數(shù)據(jù)的重要性而相應(yīng)調(diào)整。同樣，局部數(shù)據(jù)融合節(jié)點也會在由自身所組成的mesh網(wǎng)絡(luò)中建立到相應(yīng)sink節(jié)點的多條多跳路徑。
c)路徑重定義與重傳。多徑路由協(xié)議一般都會在源節(jié)點與sink節(jié)點間建立多條路由，所以路由選擇時會存在競爭問題;當(dāng)互相競爭路由的目的sink節(jié)點相同時，競爭現(xiàn)象將會更加嚴(yán)重。此時，用冗余路徑的方法是基本沒有效果的，重傳的方法甚至?xí)又馗偁帯Ｓ谑?，文中給出一種解決方案:感知節(jié)點通過空間上不同的路由同時向多個sink節(jié)點發(fā)送一個數(shù)據(jù)包，只要這個包發(fā)送到任何一個sink，則說明傳輸是成功的，如圖5所示。這相當(dāng)于ARQ(automatic repeat request)，這樣比直接用ARQ大大減小了反應(yīng)時間并減少了數(shù)據(jù)包的傳輸量，節(jié)省了能耗。
該方案主要針對干擾嚴(yán)重的無線工作環(huán)境，特別適用于多徑效應(yīng)嚴(yán)重的室內(nèi)、水下傳感器網(wǎng)絡(luò)等無線傳輸環(huán)境。
6)PBR協(xié)議[31]
Meng Min等人提出PBR(priority based routing)多sink路由協(xié)議，該協(xié)議是基于能量級別的多sink路由協(xié)議。PBR多sink傳感器網(wǎng)絡(luò)結(jié)構(gòu)如圖6所示。能量級別定義為節(jié)點在當(dāng)前所剩電能，能夠向鄰節(jié)點傳輸數(shù)據(jù)的次數(shù);路徑能量級別定義為一個節(jié)點到目標(biāo)sink節(jié)點整個路徑的最小能耗。該協(xié)議綜合考慮了節(jié)點能量級別與路徑能量級別，所以該協(xié)議能耗較均衡，大大延長了整個網(wǎng)絡(luò)的生存周期。
當(dāng)網(wǎng)絡(luò)中有資源節(jié)點i， sink節(jié)點的數(shù)目為k個，則從節(jié)點i到sink節(jié)點j的能耗可表示為cost(vi，vj);用Si，j表示i到j(luò)的路徑能量級別，此時，節(jié)點i到所有sink節(jié)點k的最大數(shù)據(jù)傳輸能耗為
max[costn(vi，vk)](3)
歸一化，有costn(vi，vj)/max[costn(vi，vk)]，則PBR可以表示為maxn(max[costn(vi，vk)]/cost(vi，vj))α×(si，j)β(4)
其中:α、β是影響因子。
PBR中，sink固定布設(shè)于網(wǎng)絡(luò)的邊界處，考慮了能耗與通信量，所以有效均衡了網(wǎng)絡(luò)中節(jié)點的能耗，從而最終延長了網(wǎng)絡(luò)的生命周期。 本文并沒有考慮如何合理地固定布設(shè)sink節(jié)點。
7)MMHR協(xié)議[32]
Ryouhei Kawano等人提出MMHR(minimize multihop routing)多sink路由算法，主旨是最小化每個傳感器節(jié)點到sink節(jié)點間的通信跳數(shù)。針對數(shù)據(jù)包傳輸過程中的包沖突問題，引入分色算法解決基于TDMA通信的通信沖突問題，該算法主要包括拓?fù)錁錁?gòu)建、時間槽分配、跳數(shù)計算三部分。此時，每個節(jié)點需要完成維持和更新鄰節(jié)點列表、為構(gòu)建到多sink的最短路徑確定自身等級和父節(jié)點、將感知數(shù)據(jù)傳輸給父節(jié)點以及為避免包傳輸沖突利用分色算法完成時間槽分配。網(wǎng)絡(luò)中的數(shù)據(jù)包幀格式如圖7所示。
IDcolorlevelneighbor IDsBS IDBS hoppacket receiving
圖7 PBR協(xié)議中數(shù)據(jù)幀結(jié)構(gòu)
其中:ID表示節(jié)點標(biāo)志符;color表示節(jié)點分配顏色;level表示節(jié)點的等級;neighbor IDs表示鄰居節(jié)點標(biāo)志符;BS ID表示sink節(jié)點標(biāo)志符;BS hop表示節(jié)點與sink節(jié)點間跳數(shù);packet receiving表示接收到的數(shù)據(jù)包。
時間槽分配中所使用的分色算法引入了圖論中的色數(shù)概念，即為所有區(qū)域內(nèi)節(jié)點分配最少的不同顏色，如節(jié)點顏色區(qū)別于其鄰節(jié)點顏色。時間槽分配與顏色分配有相似之處，于是，網(wǎng)絡(luò)中的時間槽分配的問題就變成了組合優(yōu)化問題。MMHR中分配給每個節(jié)點的時間槽必須不同于其兩跳內(nèi)鄰節(jié)點所獲得的時間槽。首先，每個節(jié)點生成其一跳與兩跳內(nèi)的且級別等于或高于其自身的鄰節(jié)點列表;接著，每個節(jié)點偵測包沖突，發(fā)現(xiàn)沖突就不發(fā)送數(shù)據(jù)包。包沖突的檢測是通過監(jiān)測壓值來實現(xiàn)的，壓值表明了時間段內(nèi)發(fā)生包沖突的次數(shù)。需要注意的是，為了有效避免sink節(jié)點間的包沖突，每個sink節(jié)點分發(fā)惟一的時間槽。
該算法具有較高的sink連通度，自組織的時間槽分配成功率高于90%，算法有效性較好，比較適合于sink節(jié)點固定布設(shè)于網(wǎng)絡(luò)邊緣的多sink網(wǎng)絡(luò)應(yīng)用場合，如PBR協(xié)議。
8)OMPER協(xié)議[33]
Haeyong Kim等人將多sink節(jié)點布設(shè)以及多sink情況下如何選擇路由問題歸結(jié)為線性規(guī)劃模型(linear programming model)，以此尋求多sink節(jié)點的最佳部署以及優(yōu)化整個網(wǎng)絡(luò)流量。
兩種線性規(guī)劃:a)假定sink節(jié)點靜止且節(jié)點數(shù)量固定，用于對網(wǎng)絡(luò)通信量進行優(yōu)化;b)限定了sink節(jié)點數(shù)目的極大值，對于sink節(jié)點的動靜于具體個數(shù)問題沒有作出具體要求，它可同時用于多sink節(jié)點布設(shè)以及多sink情況下如何選擇路由問題。
文中將所有節(jié)點分為:a)應(yīng)用傳感器節(jié)點ASN(application sensor node)，它們作為簇內(nèi)子節(jié)點工作在低功耗狀態(tài)下，負(fù)責(zé)將感知信息傳送給相應(yīng)的AFN或直接傳輸給基站(sink節(jié)點);b)聚合節(jié)點AFN(aggregation and forwarding node)，負(fù)責(zé)聚合從ASN節(jié)點接收到的數(shù)據(jù)，并將處理后的結(jié)果傳送給相應(yīng)的基站(sink節(jié)點)。 如圖8所示， 整個網(wǎng)絡(luò)是分層結(jié)構(gòu)。
該方案比那些已知最小深度樹多sink方法(aware minimum depth tree scheme)具有更好的網(wǎng)絡(luò)生存周期及公平性。
9)PWave協(xié)議[17]
Liu Hai-yang等人提出PWave多sink路由協(xié)議，該協(xié)議包括一種分布式、可擴展的勢場估計算法以及似然概率前傳策略，以確保在動態(tài)網(wǎng)絡(luò)中仍能保持較低的數(shù)據(jù)重疊，并具有較強的網(wǎng)絡(luò)自修復(fù)能力。
設(shè)SN且DN，N是網(wǎng)絡(luò)中布設(shè)的所有傳感器節(jié)點，S是網(wǎng)絡(luò)中布設(shè)的資源節(jié)點，D為所有作為目的節(jié)點的sink節(jié)點。對于每個源節(jié)點s∈S，用Is表示通過s節(jié)點或者其自身生成數(shù)據(jù)的速率?？紤]網(wǎng)內(nèi)中間節(jié)點處理的勢位(potential)可能會改變通過它們的數(shù)據(jù)流量，對于每一個可能的中間節(jié)點x∈(N-D)，當(dāng)Ix>0表示該數(shù)據(jù)流是由節(jié)點x自身生成的，而Ix<0則表示數(shù)據(jù)流將由x節(jié)點轉(zhuǎn)發(fā)。當(dāng)x∈N時，用Z(x)表示其鄰節(jié)點。根據(jù)流量守恒定律，對每個非sink節(jié)點而言，流入一個節(jié)點的數(shù)據(jù)流的速率與從該節(jié)點輸出的數(shù)據(jù)流相等，可表示為
∑y∈Z(x)Ix，y=Ix，x∈(N-D)(5)
每個非sink節(jié)點數(shù)據(jù)流分配可表示為
Ix，y=(Vx-Vy)/Rx，y(6)
由式(6)可見，任一個節(jié)點x只會將它的數(shù)據(jù)發(fā)送給一個更低勢位(Vx 實驗結(jié)果顯示，該路由算法與Directed Diffusion協(xié)議[34]相比，可使網(wǎng)絡(luò)生存周期增長2.7~8倍。 10)PDE協(xié)議[35] Mehdi Kalantari等人將類似于靜電理論中的麥克斯韋(Maxwell)公式的偏微分方程(PDE)用于解決網(wǎng)絡(luò)中多個接收端(sink)的網(wǎng)絡(luò)優(yōu)化問題。首先將整個網(wǎng)絡(luò)劃分為多個小的區(qū)域，每個區(qū)域?qū)?yīng)一個sink，如圖9所示;定義一個封閉的矢量場，進而可以推導(dǎo)出一個純量函數(shù)的梯度的形式(即勢函數(shù))。 介紹了如何優(yōu)化分配到各個sink節(jié)點的通信負(fù)載，此時對于位于任何位置的sink節(jié)點而言勢函數(shù)的值是相等的。 當(dāng)網(wǎng)絡(luò)中有多個sink節(jié)點時，整個網(wǎng)絡(luò)通信負(fù)載可以用以下等式表示，所以可將網(wǎng)絡(luò)優(yōu)化問題轉(zhuǎn)換為求下式的最小值。 J(D)=∫A K(x，y)|D(x，y)|2dxdy(7) 其中: #8226;D(x，y)=ρ(x，y)，Dn(x，y)=0，(x，y)∈B， =xi⌒+yj⌒，ρ(x，y)=r(x，y)-∑Mi=1ωiδ(x-xi)δ(y-yi) 其中:A是節(jié)點布設(shè)的平面區(qū)域;定義D為A中的矢量場以表示網(wǎng)絡(luò)中的負(fù)載強度矢量;B為A的邊界點集合;ρ(x，y)表示網(wǎng)絡(luò)中消息產(chǎn)生的空間速率密度;M表示目的節(jié)點(sink)的數(shù)目;(xi，yi)表示第i個目的節(jié)點的位置;r(x，y)表示了單位區(qū)域單位時間內(nèi)產(chǎn)生的消息量;ωi是權(quán)重系數(shù)?？梢?，在多sink節(jié)點網(wǎng)絡(luò)中問題的復(fù)雜度在于優(yōu)化問題不僅要考慮D，還要兼顧權(quán)重值ω1，ω2，…，ωM。 11)ORMMA-WSN協(xié)議[36] Arturas Lukosius提出一種機會路由算法ORMMA-WSN(opportunistic routing in multi-sink mobile Ad hoc wireless sensor networks)，該路由協(xié)議是單播的多跳路由協(xié)議。單址廣播(unicast)是指向單一網(wǎng)絡(luò)地址的傳送，這是與廣播(傳送到全部網(wǎng)絡(luò)地址)和多址廣播(傳送到選定的網(wǎng)絡(luò)地址)相比較而言的。該協(xié)議是屬于機會路由(opportunistic routing)的方法，即在缺少端到端直接數(shù)據(jù)傳輸鏈路的情況下，數(shù)據(jù)發(fā)送端等待一個較好的時機將待傳送數(shù)據(jù)發(fā)送出去。該算法中每個節(jié)點周期性地判斷自身是否該將數(shù)據(jù)傳送給其他節(jié)點，此時影響判定標(biāo)準(zhǔn)的因素包括節(jié)點當(dāng)前位置、與鄰近節(jié)點的拓?fù)潢P(guān)系以及自身相對于其所對應(yīng)sink節(jié)點的運動方向。具體而言，這些參數(shù)通過測量來自sink節(jié)點的接收信號強度指示值(received signal strength indicator，RSSI)和移動梯度值(mobility gradient，MG)來獲得的。其中RSSI值的大小表示了節(jié)點與sink節(jié)點的距離遠近，在周期性獲得一些RSSI值之后，節(jié)點就可以計算出一個MG。 ORMMA-WSN是基于地理位置路由協(xié)議的，節(jié)點首先要知道其鄰近節(jié)點及其自身的位置信息，還要知道各個鏈路的質(zhì)量信息。不止一個鄰節(jié)點時，根據(jù)節(jié)點的可用性選擇下一跳節(jié)點，網(wǎng)絡(luò)層負(fù)責(zé)選擇距離目的節(jié)點最近的中間節(jié)點。 因為要用間歇的連接并獲知各個節(jié)點的當(dāng)前狀況，以此作為完成高效/可靠的路由的依據(jù)，所以每個節(jié)點需周期性地獲知自身的移動信息，包括從sink節(jié)點收到的beacon消息攜帶的RSSI計算出MG，以及最佳鄰節(jié)點BNN(best neighbor node)與最佳sink節(jié)點BS(best sink)的信息。 具體而言，RSSI的值取的是所有接收到的數(shù)據(jù)包RSSI值的均值。MG是關(guān)于移動節(jié)點相對于sink節(jié)點的移動方向性，即MG=sign(RSSI2-RSSI1) 。當(dāng)MG=-1，表示移動方向是背離相應(yīng)sink節(jié)點的方向;當(dāng)MG=0，表示節(jié)點靜止;當(dāng)MG=1，表示移動方向是靠近sink節(jié)點的方向。 圖10是ORMMA-WSN路由算法路徑選擇的過程。 該協(xié)議適用于網(wǎng)絡(luò)連接時斷時續(xù)的應(yīng)用場合，數(shù)據(jù)傳輸可靠性較好。OPNET仿真結(jié)果表明，相比于典型的單sink的AODV路由算法，能有效減少通信沖突概率，明顯減小了網(wǎng)絡(luò)的負(fù)載，網(wǎng)絡(luò)延時也比較小。 3 多sink路由協(xié)議比較 多sink路由協(xié)議比較結(jié)果如表1所示。 表1 多sink路由協(xié)議特點比較 多sink路由算法固定布設(shè)隨機布設(shè)靜止動態(tài)固定對象動態(tài)對象平面型層次型 MRMS√√√√ TTDD-MS√√√√ Voronoi scoping√√√ PAMR√√√ SDMR-MS√√√ PBR√√√√ MMHR√√ OMPER√√√√ PWave√√√√ PDE√√√√ ORMMA-WSN√√√ 由表1可見，目前大部分多sink路由協(xié)議中，sink節(jié)點是固定布設(shè)的。此時，如何有效合理地布設(shè)sink節(jié)點是亟待解決的問題，文獻[37，38]對sink布設(shè)進行了討論。此外，絕大多數(shù)傳感器網(wǎng)絡(luò)多sink路由協(xié)議在路由建立過程中固定sink對象， 如源節(jié)點將固定sink節(jié)點作為自己的目的節(jié)點，此種策略沒有充分利用多sink節(jié)點的分散性、多選擇性，影響了網(wǎng)絡(luò)組網(wǎng)的靈活性。由于多sink節(jié)點大多是針對大規(guī)模傳感器網(wǎng)絡(luò)環(huán)境，而基于網(wǎng)絡(luò)分簇的層次型路由協(xié)議比較適合于大規(guī)模傳感器網(wǎng)絡(luò)，所以目前多sink路由協(xié)議大部分是基于網(wǎng)絡(luò)分層思想的。 4 結(jié)束語 目前，多sink路由協(xié)議還比較少，但隨著人們對大型傳感器網(wǎng)絡(luò)的應(yīng)用需求越加迫切，以及研究人員對于傳感器網(wǎng)絡(luò)研究的不斷深入，多sink節(jié)點的傳感器網(wǎng)絡(luò)必將迎來新的發(fā)展。 網(wǎng)絡(luò)連接的斷續(xù)性、移動性以及功率控制是一般傳感器網(wǎng)絡(luò)路由最大的挑戰(zhàn)，除此以外，多sink網(wǎng)絡(luò)中比較受關(guān)注的是網(wǎng)絡(luò)規(guī)模與sink節(jié)點數(shù)目之間的最優(yōu)化。多sink節(jié)點路由的發(fā)展趨勢主要包括: a)盡量減少網(wǎng)絡(luò)通信量。由于WSN中節(jié)點間的通信能耗較大，在路由協(xié)議中應(yīng)盡量減少數(shù)據(jù)通信過程。特別是對于多sink情況下，不僅感知節(jié)點間需要通信，一般sink節(jié)點間也需通過通信協(xié)調(diào)之間的路由建立過程，如何有效減少網(wǎng)絡(luò)通信量至關(guān)重要。文獻[32]研究了針對多sink網(wǎng)絡(luò)數(shù)據(jù)融合技術(shù)。 b)確保通信量負(fù)載均衡。平衡節(jié)點能耗，延長網(wǎng)絡(luò)生存期是多sink節(jié)點網(wǎng)絡(luò)設(shè)想需要解決的關(guān)鍵問題，通過節(jié)點到多個sink的多路徑路由策略使各個節(jié)點分擔(dān)數(shù)據(jù)傳輸任務(wù)。相對于單sink節(jié)點的多路徑路由方法，多sink的架構(gòu)有效解決了單sink節(jié)點鄰近節(jié)點高負(fù)載、易失效的問題，更具多路徑組網(wǎng)的靈活性。多sink節(jié)點功率控制問題[39]往往是多sink路由需要解決的關(guān)鍵問題。 c)路由協(xié)議應(yīng)具有容錯性。由于WSN節(jié)點容易發(fā)生故障，如何確保及時地在路由出現(xiàn)故障時能夠盡快發(fā)現(xiàn)甚至恢復(fù)路由是必須要考慮的問題。多個sink本身就加大了網(wǎng)絡(luò)對于sink節(jié)點失效的健壯性，并為普通節(jié)點提供了更多的數(shù)據(jù)傳輸目的sink節(jié)點數(shù)，一條傳輸路徑失效，一般可以很快建立新的傳輸路徑。 d)路由協(xié)議應(yīng)具有一定的安全機制。由于WSN固有的開放性應(yīng)用環(huán)境，其路由協(xié)議極易受到安全威脅。目前的路由協(xié)議很少考慮安全問題，但一些應(yīng)用中必須考慮安全機制，如Zigbee抄表系統(tǒng)等。由于傳感器節(jié)點本身數(shù)據(jù)處理能力有限，不可能每個節(jié)點都去完成較復(fù)雜的數(shù)據(jù)加解密運算，此時，可以考慮多sink節(jié)點協(xié)調(diào)處理的網(wǎng)絡(luò)安全機制。 文獻[40]指出還要考慮通過節(jié)點的流量大小、數(shù)據(jù)通道選擇與競爭、數(shù)據(jù)速率限制等因素，這些都為多sink路由算法的實現(xiàn)帶來了很大的難度。但多sink網(wǎng)絡(luò)結(jié)構(gòu)中，多sink相互協(xié)作，更具健壯性、能耗更均衡，且多sink路由協(xié)議一般容易與單sink路由算法相兼容，多sink架構(gòu)為傳感器網(wǎng)絡(luò)大規(guī)模應(yīng)用提供了可能，必將受到研究人員的更多關(guān)注。 參考文獻: [1]AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y，et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，38(4):393-422. [2]KAHN J， KATZ R， PISTER K. Next century challenges: mobile networking for smart dust[C]//Proc of Annual International Conference on Mobile Computing and Networking. New York: ACM Press， 1999:271-278. [3]馬黃東，陶丹. 多媒體傳感器網(wǎng)絡(luò)及其研究進展[J].軟件學(xué)報， 2006，17(9):2013-2028. [4]CUI Jun-hong. Building autonomous underwater sensor networks:overview，archievements，plans[EB/OL].http://uwsn.engr.uconn.edu/annual07/UMSN_annual07_overview_CUI.pdf. [5]唐勇，周明天，張欣. 無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進展[J]. 軟件學(xué)報，2006，17(3):410-421. [6]AL-KARAKI J N， KAMAL A E. Routing techniques in wireless sensor networks: a survey[J]. Wireless Communications， 2004，11(6):6-28. [7]CHANG J H， TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Trans on Networking， 2004，12(4):609-619. [8]GOVINDAN R， HELLERSTEIN J， HONG W，et al. The sensor network as a database，TR02-771[R].California:University of Southern California， 2002. [9]KARP B， KUNG H. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th Annual International Confe-rence on Mobile Computing and Networking. Boston: ACM Press， 2000:243-254. [10]韓鵬，吳華鋒，任久春，等. 多sink 動態(tài)傳感器網(wǎng)絡(luò)主動式分層定位方法[J].通信學(xué)報，2007，28(11):44-50. [11]吳中博，樊小泊，陳紅. 基于能量水平的多Sink節(jié)點傳感器網(wǎng)絡(luò)路由算法[J].計算機研究與發(fā)展，2008，45(1):41-46. [12]YE Fan， LUO Hai-yun， CHENG J，et al. A two-tier data dissemination model for large-scale wireless sensor networks[C]//Proc of the 8th Annual International Conference on Mobile Computing and Networking. New York: ACM Press， 2002:148-159. [13]ROMER K. Distributed mining of spatio-temporal event patterns in sensor networks[C]//Proc of Workshop on Middleware for Sensor Networks. San Francisco: IEEE Computer Society， 2006:103-116. [14]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proc of Hawaii International Conference on System Sciences. San Francisco: IEEE Computer Society， 2000:3005-3014. [15]LINDSEY S， RAGHAVENDRA C S.PEGASIS: power efficient gathering in sensor information systems[C]//Proc of IEEE Aerospace Conference. San Francisco: IEEE Computer Society， 2002:1-6. [16]CHEN Yue-quan， CHAN E， HAN Song. Energy efficient multipath routing in large scale sensor networks with multiple sink nodes[C]//Proc of the 6th International Workshop on Advanced Parallel Processing Techniques. Berlin: Springer， 2005:390-399. [17]LIU Hai-yang， ZHANG Zhi-li， SRIVASTAVA J， et al. PWave: a multi-source multi-sink anycast routing framework for wireless sensor networks[C]//Proc of the 6th Networking Conference. Berlin: Springer， 2007:179-190. [18]GAVISH B. Topological design of computer communication networks-the overall design problem[J]. European Journal of Operations Research， 1992，58(2):149-172. [19]ILKER OYMAN E， ERSOY C. Multiple sink network design problem in large scale wireless sensor networks[C]//Proc of IEEE International Conference on Communications. San Francisco: IEEE Compu-ter Society， 2004:3663-3667. [20]ALCOUFFE A， MURATET G. Optimal location of plants[J]. Ma-nagement Science， 1976，23(3):267-274. [21]BOORSTYN R R， FRANK H. Large-scale network topological optimization[J]. IEEE Trans on Communications， 1977，25(1):29-47. [22]BURATTIC，VERDONE R. Tree-based topology design for multi-sink wireless sensor networks[C]//Proc of the 18th IEEE International Symposium on Personal， Indoor and Mobile Radio Communications. San Francisco: IEEE Computer Society， 2007:1-5. [23]DEB B，BHATNAGAR S， NATH B. A topology discovery algorithm for sensor networks with applications to network management[R]. Pasadena， USA: Rutgers University， 2001. [24]王福豹，史龍，任豐原. 無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報，2005，16(5):857-868. [25]WANG S S， SHIH K P， CHANG C Y. Distributed direction-based localization in wireless sensor networks[J]. Computer Communications， 2007，30(6):1424-1439. [26]COFFIN D， HOOK D V， McGARRY S，et al. Declarative Ad hoc sensor networking[C]//Proc of SPIE Integrated Command Environments. Bellingham:International Society for Optical Engineering， 2000:109-120. [27]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual International Conference on Mobile Computing and Networking. Boston: ACM Press， 2000:56-67. [28]DUBOIS-FERRIERE H， ESTRIN D，STATHOPOULOS T. Efficient and practical query scoping in sensor networks[C]//Proc of IEEE International Conference on Mobile Ad hoc and Senser Systems. 2004:564-566. [29]BOUKERCHE A， MARTIROSYAN A. Efficient routing from multiple sources to multiple sinks in wireless sensor networks[C]//Proc of the 4th ACM Workshop on Performance Evaluation of Wireless Ad hoc， Sensor， and Ubiquitous Networks. New York: ACM Press， 2007:82-86. [30]SEAH W K G， TAN H P. Multipath virtual sink architecture for wireless sensor networks in harsh environments[C]//Proc of the 1st International Conference on Integrated Internet Ad hoc and Sensor Networks. New York: ACM Press， 2006:1-6. [31]MENG Min， XU Hui， WU Xiao-ling， et al. PBR: priority based routing in multi-sink sensor networks[C]//Proc of International Conference on Wireless Networks.Las Vegas: CSREA Press， 2007:25-28. [32]KAWANO R， MIYAZAKI T. Distributed data aggregation in multi-sink sensor networks using a graph coloring algorithm[C]//Proc of the 22nd International Conference on Advanced Information Networking and Applications. Los Alamitos: IEEE Computer Society， 2008:934-940. [33]KIM H， SEOK Y， CHOI N，et al. Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks[C]//Proc of International Conference on Information Networking， Convergence in Broadband and Mobile Networking. Berlin:Springer， 2005:264-274. [34]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual International Conference on Mobile Computing and Networking. Boston: ACM Press， 2000:56-67. [35]KALANTARI M， SHAYMAN M. Design optimization of multi-sink sensor networks by analogy to electrostatic theory[C]//Proc ofIEEE Wireless Communications and Networking Conference. New Orleans: IEEE Communication Society， 2006:431-438. [36]LUKOSIUS A. Opportunistic routing in multi-sink mobile Ad hoc wireless sensor networks[D]. Bremen:University of Bremen， 2007. [37]VINCZE Z， VIDA R， VIDACS A. Deploying multiple sinks in multi-hop wireless sensor networks[C]//Proc of IEEE International Confe-rence on Pervasive Services. 2007:55-63. [38]VINCZE Z， VIDA R， VIDACS A. On the efficiency of local information-based sink deployment in heterogeneous environments[C]//Proc of the 2nd International Workshop on Wireless Sensor Networks. 2007. [39]WENNING B L， LUKOSIUS A， TIMM-GIEL A，et al. Opportunistic distance-aware routing in multi-sink mobile wireless sensor networks[C]//Proc of ICT-Mobile Summit Conference. Dublin: International Information Management Corporation， 2008. [40]YUEN K， LI Bao-chun， LIANG Ben. Distributed data gathering in multi-sink sensor networks with correlated sources[C]//Proc of the 5th IFIP Networking Conference.Berlin:Springer， 2006:868-879.
