C-cast:傳感器網(wǎng)絡(luò)中無位置數(shù)據(jù)分發(fā)和發(fā)現(xiàn)技術(shù)*

李志剛，吳君青

(解放軍理工大學(xué)指揮自動(dòng)化學(xué)院，南京210007)

近年來，大規(guī)模無線傳感器網(wǎng)絡(luò)在很多關(guān)系到國(guó)計(jì)民生的應(yīng)用中得到廣泛的研究，比如科學(xué)數(shù)據(jù)收集，環(huán)境監(jiān)測(cè)，以及軍事偵察等領(lǐng)域[1－3]。一般來說，傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的電池容量、計(jì)算能力和存儲(chǔ)能力都是有限的，傳統(tǒng)網(wǎng)絡(luò)協(xié)議由于需要較多的存儲(chǔ)和較高的計(jì)算能力等原因所以一般不適合傳感器網(wǎng)絡(luò)的應(yīng)用[1]。設(shè)計(jì)輕量級(jí)的協(xié)議對(duì)傳感器網(wǎng)絡(luò)的實(shí)用性至關(guān)重要。在協(xié)議設(shè)計(jì)過程中，目前的研究大多基于傳感器網(wǎng)絡(luò)符合服務(wù)器－客戶端網(wǎng)絡(luò)模式，即在網(wǎng)絡(luò)中部署一個(gè)靜態(tài)的基站節(jié)點(diǎn)，其他節(jié)點(diǎn)通過多跳傳輸，周期性地向基站節(jié)點(diǎn)傳送感知數(shù)據(jù)[3]。不過，在一些應(yīng)用中，傳感器節(jié)點(diǎn)之間需要進(jìn)行對(duì)等的點(diǎn)對(duì)點(diǎn)數(shù)據(jù)傳輸和分發(fā)工作[4]。

關(guān)于傳感器網(wǎng)絡(luò)中對(duì)等節(jié)點(diǎn)的數(shù)據(jù)分發(fā)和發(fā)現(xiàn)問題已經(jīng)有一些相關(guān)的研究?，F(xiàn)有的工作可以分成兩類:基于位置的策略和無位置策略。相關(guān)工作TTDD[5]，GHT[6]，Double Rulings[7]和振蕩軌跡[8]，都屬基于位置的策略，如果每個(gè)節(jié)點(diǎn)都能獲知其位置信息的話，這些策略都可以取得良好的性能。在基于位置的策略中，感知到數(shù)據(jù)的節(jié)點(diǎn)可以將數(shù)據(jù)存儲(chǔ)到預(yù)先定義的位置附近某個(gè)節(jié)點(diǎn)R上(可以通過GHT獲得這個(gè)位置信息)，同時(shí)其他節(jié)點(diǎn)可以通過訪問該節(jié)點(diǎn)R來發(fā)現(xiàn)感知數(shù)據(jù)。但是定位算法[9－10]的局限性限制了基于位置策略的應(yīng)用。而在無位置策略中，假設(shè)每個(gè)節(jié)點(diǎn)不能獲知其位置信息，也不能獲知其他節(jié)點(diǎn)的位置信息，在沒有全局信息的假設(shè)下，就不能預(yù)先知道哪一個(gè)節(jié)點(diǎn)需要查詢數(shù)據(jù)，也不能確定將數(shù)據(jù)存儲(chǔ)到什么位置。因此為滿足有效的數(shù)據(jù)發(fā)現(xiàn)，需要在每個(gè)節(jié)點(diǎn)上存儲(chǔ)維護(hù)大量的全局信息。但是維護(hù)全局信息，需要很多能量、計(jì)算開銷和存儲(chǔ)資源。如果不維護(hù)全局信息，而采用簡(jiǎn)單的泛洪策略和rumor路由策略[11]，同樣會(huì)產(chǎn)生大量的冗余開銷。本文的目標(biāo)是設(shè)計(jì)一套輕量級(jí)的策略，允許在沒有位置和不需要太多拓?fù)湫畔⒌臈l件下，進(jìn)行數(shù)據(jù)的分發(fā)和發(fā)現(xiàn)。

本文提出的C-cast協(xié)議，只需要選擇兩個(gè)節(jié)點(diǎn)作為信標(biāo)節(jié)點(diǎn)[12]，利用它們?cè)诰W(wǎng)絡(luò)中構(gòu)建兩個(gè)獨(dú)立的輪廓覆蓋網(wǎng)絡(luò)(contour overlay network)，在此基礎(chǔ)上進(jìn)行數(shù)據(jù)分發(fā)和發(fā)現(xiàn)工作。C-cast可以達(dá)到基于位置信息的Double rulings策略的性能和效果。同時(shí)，協(xié)議的存儲(chǔ)開銷只是需要每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)跳步計(jì)數(shù)對(duì)，而不用存儲(chǔ)太多的信息。C-cast需要的只是節(jié)點(diǎn)鏈接信息而不需要測(cè)距和定位。同時(shí)C-cast路由可以達(dá)到負(fù)載均衡，避免在網(wǎng)絡(luò)中出現(xiàn)空洞[13]。

1 輪廓覆蓋網(wǎng)構(gòu)建

1.1 網(wǎng)絡(luò)模型

本文假設(shè)的網(wǎng)絡(luò)是大規(guī)模稠密網(wǎng)絡(luò)，節(jié)點(diǎn)按照泊松分布或者均勻分布部署在一個(gè)正方形的區(qū)域內(nèi)，且在傳感器網(wǎng)絡(luò)所在的區(qū)域內(nèi)任意畫一條曲線l，到l距離小于某一閾值d的所有節(jié)點(diǎn)集合滿足連通性。全網(wǎng)節(jié)點(diǎn)可以分為三類:數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)、數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)和中間節(jié)點(diǎn)。數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)為感知到數(shù)據(jù)的節(jié)點(diǎn)[5－8]。數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)為在無線傳感器網(wǎng)絡(luò)中，在某一時(shí)間間隔[T1，T2]中，發(fā)起數(shù)據(jù)查詢操作的節(jié)點(diǎn)。中間節(jié)點(diǎn)是指用于數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)與生產(chǎn)者節(jié)點(diǎn)進(jìn)行多跳數(shù)據(jù)轉(zhuǎn)發(fā)和存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)。本文假設(shè)任何節(jié)點(diǎn)都有可能成為數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)或者數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)。數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)和數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)構(gòu)成對(duì)等網(wǎng)絡(luò)[4－8，11]。

定義1數(shù)據(jù)查詢成功率:數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)發(fā)出的查詢消息能夠發(fā)現(xiàn)數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)或者數(shù)據(jù)摘要，則稱為一次數(shù)據(jù)查詢成功。否則稱為一次數(shù)據(jù)查詢失敗。數(shù)據(jù)查詢成功的次數(shù)占所有數(shù)據(jù)查詢次數(shù)的比例稱為數(shù)據(jù)查詢成功率。

1.2 輪廓覆蓋網(wǎng)

本文的工作，主要是利用兩個(gè)信標(biāo)節(jié)點(diǎn)來抽取整個(gè)網(wǎng)絡(luò)的拓?fù)浜玩溄有畔?。為方便下文的論述，稱其中一個(gè)信標(biāo)為藍(lán)色信標(biāo)，另一個(gè)為紅色信標(biāo)。兩個(gè)信標(biāo)都向網(wǎng)絡(luò)中其他節(jié)點(diǎn)廣播跳步計(jì)數(shù)消息。其他節(jié)點(diǎn)在收到跳步計(jì)數(shù)消息以后，分別計(jì)算到兩個(gè)信標(biāo)的最短跳步數(shù)。本節(jié)主要描述如何構(gòu)建和初始化兩個(gè)輪廓覆蓋網(wǎng)，暫時(shí)不考慮信標(biāo)的選擇過程，假設(shè)兩個(gè)信標(biāo)已經(jīng)選定。關(guān)于如何選擇信標(biāo)在下面的章節(jié)會(huì)有描述。信標(biāo)節(jié)點(diǎn)只在網(wǎng)絡(luò)初始階段起作用，在輪廓覆蓋網(wǎng)構(gòu)建以后，其能量消耗過程和其他節(jié)點(diǎn)是相似的。

首先為每個(gè)節(jié)點(diǎn)賦值一個(gè)跳步計(jì)數(shù)對(duì)(b，r)，b代表該節(jié)點(diǎn)到藍(lán)色信標(biāo)的跳步數(shù)，稱為bluehop數(shù);r代表該節(jié)點(diǎn)到紅色信標(biāo)的跳步數(shù)，稱為redhop數(shù)。(b，r)初始值為(bmax，rmax)，比如 bmax和 rmax都可以設(shè)置為127。跳步計(jì)數(shù)消息，M包括兩部分，第一部分為顏色標(biāo)識(shí)，用1個(gè)比特位來表示，比如說“1”代表藍(lán)色消息，“0”代表紅色消息;另一部分就是跳步計(jì)數(shù)器。當(dāng)一個(gè)節(jié)點(diǎn)收到消息M的時(shí)候，首先檢查M的顏色標(biāo)識(shí)。然后比較當(dāng)前跳步計(jì)數(shù)對(duì)中相同顏色標(biāo)識(shí)的跳步數(shù)與M的計(jì)數(shù)器的大小。如果節(jié)點(diǎn)的跳步數(shù)大于等于M.Hop+2，節(jié)點(diǎn)的跳步數(shù)則修改為M.Hop+1。在一個(gè)較短的時(shí)間內(nèi)，節(jié)點(diǎn)有可能收到多個(gè)具有相同顏色標(biāo)識(shí)的消息，那么節(jié)點(diǎn)只需要選擇具有最小跳步數(shù)的消息即可。如果節(jié)點(diǎn)修改了某種顏色的跳步數(shù)，則向其鄰居廣播一個(gè)消息，通知其鄰居節(jié)點(diǎn)它的當(dāng)前跳步數(shù)。在幾次迭代之后，所有的節(jié)點(diǎn)都會(huì)計(jì)算出到相應(yīng)的信標(biāo)的最短跳步數(shù)。

算法1 輪廓覆蓋網(wǎng)的建立1 對(duì)每個(gè)節(jié)點(diǎn)初始化bluehop=127，redhop=127;2 (a)藍(lán)色信標(biāo)廣播消息BM給所有的鄰居節(jié)點(diǎn)，其中BM.hop=0，BM.flag=blue;藍(lán)色信標(biāo)的 bluehop=0;(b)紅色信標(biāo)廣播消息RM給所有的鄰居節(jié)點(diǎn)，其中RM.hop=0，RM.flag=red;紅色信標(biāo)的 redhop=0;3 (a)當(dāng)節(jié)點(diǎn)u接收到一個(gè)藍(lán)色消息BM，如果(BM.hop+1＜u.bluehop)則 u.bluehop=BM.hop+1;否則丟掉 BM。(b)當(dāng)節(jié)點(diǎn)u接收到一個(gè)紅色消息RM，如果(RM.hop+1＜u.redhop)則 u.redhop=RM.hop+1;否則丟掉 RM。4 (a)節(jié)點(diǎn)u將BM.hop=BM.hop+1;并且將新的BM發(fā)送給鄰居節(jié)點(diǎn)。(b)節(jié)點(diǎn)u將RM.hop=RM.hop+1;并且將新的RM發(fā)送給鄰居節(jié)點(diǎn)。

以紅色信標(biāo)為例，所有的redhop為k的節(jié)點(diǎn)形成一個(gè)輪廓(contour)，記為CRk(對(duì)應(yīng)于藍(lán)色信標(biāo)的輪廓記為CBk)。所有根據(jù)紅色信標(biāo)形成的輪廓稱為紅色輪廓覆蓋網(wǎng)。在稠密網(wǎng)絡(luò)中，假設(shè)存在k'，使得所有位于輪廓CRk的節(jié)點(diǎn)都是連通的，其中k＜k'，k稱為 CRk的半徑;對(duì)于所有 k＞k'的輪廓 CRk有可能分成幾段，在這種情況下，可以通過邊界上的點(diǎn)輔助進(jìn)行路由，而且在正方形網(wǎng)絡(luò)中k'與k差別很小。所以在下面我們都假設(shè)位于同一輪廓上的節(jié)點(diǎn)都是連通的。對(duì)redhop為k(k＞0)的個(gè)體節(jié)點(diǎn)來說，如果k不是具有最大的redhop的節(jié)點(diǎn)，則其鄰居可以分為三種。第一種是k-hop鄰居，具有相同的redhop數(shù)，并同樣位于相同的輪廓CRk上;第二種為(k－1)-hop鄰居，為當(dāng)前節(jié)點(diǎn)的上一跳節(jié)點(diǎn);第三種為(k+1)-hop鄰居，為當(dāng)前節(jié)點(diǎn)的下一跳節(jié)點(diǎn)。輪廓覆蓋網(wǎng)建立以后，具有(b，r)節(jié)點(diǎn)簡(jiǎn)稱為節(jié)點(diǎn)(b，r)。節(jié)點(diǎn)(b，r)屬于兩條輪廓，一條為藍(lán)色輪廓CBb，一條為紅色輪廓CRr。節(jié)點(diǎn)不需要存儲(chǔ)輪廓上其他所有節(jié)點(diǎn)的信息。實(shí)際上可以將(b，r)看作一種虛擬坐標(biāo)。不過相比歐式距離空間的位置坐標(biāo)，該坐標(biāo)不需要精確測(cè)量節(jié)點(diǎn)之間的距離，而是完全基于節(jié)點(diǎn)之間的鏈接關(guān)系，能夠更準(zhǔn)確的反映節(jié)點(diǎn)的連接和拓?fù)湫畔?。?jié)點(diǎn)可以利用該坐標(biāo)來指導(dǎo)數(shù)據(jù)的分發(fā)存儲(chǔ)和發(fā)現(xiàn)過程。算法1描述了輪廓覆蓋網(wǎng)的建立過程，圖1中表示隨機(jī)選擇的信標(biāo)建立輪廓覆蓋網(wǎng)以后的情況。事實(shí)上兩個(gè)覆蓋網(wǎng)是重疊的。假設(shè)所有的屬于同一輪廓的節(jié)點(diǎn)都是連通的，可以定義下面一種新的數(shù)據(jù)轉(zhuǎn)發(fā)協(xié)議。

圖1 輪廓線的建立(信標(biāo)節(jié)點(diǎn)及跳步數(shù)為偶數(shù)的節(jié)點(diǎn)用粗點(diǎn)表示)

定義2C-cast:在輪廓覆蓋網(wǎng)中，節(jié)點(diǎn)(b，r)將數(shù)據(jù)傳送到輪廓CBb或者CRr的所有節(jié)點(diǎn)上，稱為一次C-cast路由。C-cast路由可以用來分發(fā)數(shù)據(jù)副本和查詢。

2 理想C-cast模型

在本章中，假設(shè)傳感器網(wǎng)絡(luò)部署在一個(gè)正方形的區(qū)域內(nèi)，節(jié)點(diǎn)稠密且均勻分布。文獻(xiàn)[12]的方法可以用來選擇兩個(gè)信標(biāo)節(jié)點(diǎn)，即首先隨機(jī)選擇一個(gè)節(jié)點(diǎn)A，然后選擇距離節(jié)點(diǎn)A最遠(yuǎn)的節(jié)點(diǎn)B作為紅色信標(biāo);選擇到節(jié)點(diǎn)B最遠(yuǎn)的節(jié)點(diǎn)C，然后選擇距離節(jié)點(diǎn)B和C之和最大的節(jié)點(diǎn)D為藍(lán)色節(jié)點(diǎn)，文獻(xiàn)[12]指出，在稠密均勻的正方形區(qū)域，該過程選擇的兩個(gè)信標(biāo)節(jié)點(diǎn)位于正方形同一側(cè)的頂點(diǎn)附近。在某些情況下和應(yīng)用中，甚至可以直接指定兩個(gè)節(jié)點(diǎn)作為信標(biāo)。本節(jié)假設(shè)藍(lán)色信標(biāo)位于正方形區(qū)域的左上角，紅色信標(biāo)位于正方形區(qū)域的左下角，稱具有這樣性質(zhì)的網(wǎng)絡(luò)為理想C-cast模型，見圖2。本章主要研究理想C-cast模型下的數(shù)據(jù)副本分發(fā)和查詢過程。

圖2 數(shù)據(jù)副本的四種分發(fā)策略(在基本查詢過程中也用到這四種策略)

2.1 數(shù)據(jù)副本分發(fā)過程

當(dāng)節(jié)點(diǎn)(b，r)感知到數(shù)據(jù)以后，則觸發(fā)數(shù)據(jù)副本分發(fā)過程。在該過程中，可以定義四種策略。分別為(a)RiB(Red First/Min Blue)，(b)RaB(Red First/Max Blue)，(c)BiR(Blue First/Min Red)，and(d)BaR(Blue First/Max Red)。圖2顯示了這四種策略。每個(gè)節(jié)點(diǎn)采用每種策略的概率都為25%。不失一般性，用RiB策略作為例子說明數(shù)據(jù)副本分發(fā)的過程。在策略RiB中，節(jié)點(diǎn)(b，r)需要做兩個(gè)決定。第一，決定首先沿紅色輪廓CRrC-cast數(shù)據(jù)。第二，在數(shù)據(jù)中加入通知所有位于紅色輪廓CRr上的節(jié)點(diǎn)尋找具有極大bluehop的節(jié)點(diǎn)的消息。如果節(jié)點(diǎn)M(m，r)發(fā)現(xiàn)自己的bluehop比所有鄰居的bluehop都要小，則M發(fā)起沿藍(lán)色輪廓CBm的C-cast。數(shù)據(jù)在經(jīng)過的節(jié)點(diǎn)上留下一個(gè)副本。該過程產(chǎn)生的紅色輪廓和藍(lán)色輪廓，由節(jié)點(diǎn)M連接在一起，形成一條路徑，稱為聯(lián)合C-cast路徑，簡(jiǎn)稱為C-cast路徑。設(shè)計(jì)四種策略的原因是為了滿足負(fù)載均衡。

2.2 數(shù)據(jù)查詢過程

如果某個(gè)節(jié)點(diǎn)成為數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)，則需要啟動(dòng)查詢過程。如果數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)采用類似于數(shù)據(jù)副本分發(fā)過程一樣的策略，則稱之為基本查詢過程。除此之外，也可以利用其他的一些策略進(jìn)行數(shù)據(jù)查詢工作。

基本查詢過程的思想是，當(dāng)數(shù)據(jù)生產(chǎn)者P將數(shù)據(jù)副本利用以上四種策略中的任意一種分發(fā)到相應(yīng)的C-cast路徑上以后，另一個(gè)節(jié)點(diǎn)Q作為消費(fèi)者節(jié)點(diǎn)需要查詢?cè)摂?shù)據(jù)。節(jié)點(diǎn)P的C-cast存儲(chǔ)路徑包括一段紅色輪廓CRr和一段藍(lán)色輪廓CBb?；静樵冞^程利用以上四種策略中的任意一種分發(fā)查詢信息。可以證明C-cast查詢路徑和C-cast存儲(chǔ)路徑是相交的，即C-cast查詢路徑和C-cast存儲(chǔ)路徑，至少共享一個(gè)節(jié)點(diǎn)。如果C-cast路徑為連續(xù)曲線，則可以很容易證明任意兩條路徑都相交于一點(diǎn)。在實(shí)際情況下，C-cast路徑是離散的，而不是連續(xù)的。下面的定理1保證了在離散的情況下任意兩條C-cast路徑仍然存在相交的節(jié)點(diǎn)。

定理1在理想C-cast模型中，任意兩條C-cast路徑至少相交于一個(gè)節(jié)點(diǎn)。(證明略)

定理1說明，如果數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)需要發(fā)現(xiàn)期望數(shù)據(jù)，只需要檢索所有在相同輪廓上的鄰居即可，而不需要考慮所有的鄰居，從而避免了向(k－1)-hop鄰居和(k+1)-hop鄰居轉(zhuǎn)發(fā)數(shù)據(jù)。

除了基本查詢過程，針對(duì)某些應(yīng)用設(shè)計(jì)了雙C-cast查詢策略。在雙 C-cast查詢中，節(jié)點(diǎn)(b，r)，在輪廓CBb和CRr上同時(shí)分發(fā)查詢信息。

3 隨機(jī)C-cast模型

出于網(wǎng)絡(luò)實(shí)際情況的考慮，信標(biāo)節(jié)點(diǎn)不一定位于網(wǎng)絡(luò)中的特殊位置，而是允許出現(xiàn)在任何位置，這種情況稱為隨機(jī)C-cast模型。

3.1 信標(biāo)選擇

在隨機(jī)C-cast模型中，依然假設(shè)網(wǎng)絡(luò)區(qū)域?yàn)檎叫螀^(qū)域。下面首先討論信標(biāo)的隨機(jī)選擇過程。

3.1.1 紅色信標(biāo)選擇

首先，在網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為紅色信標(biāo)。然后紅色信標(biāo)向網(wǎng)絡(luò)中的其他節(jié)點(diǎn)廣播跳步計(jì)數(shù)消息。如果中間節(jié)點(diǎn)發(fā)現(xiàn)不能再向其他節(jié)點(diǎn)發(fā)送計(jì)數(shù)消息，則逆向往紅色信標(biāo)發(fā)送ACK消息。通過ACK消息，紅色信標(biāo)可以計(jì)算網(wǎng)絡(luò)中最大的redhop數(shù)K。在沒有全局調(diào)度的情況下，可能有幾個(gè)節(jié)點(diǎn)同時(shí)發(fā)起紅色信標(biāo)競(jìng)爭(zhēng)的消息。

在這種情況下，這些節(jié)點(diǎn)可以按照時(shí)間戳或者節(jié)點(diǎn)ID進(jìn)行競(jìng)爭(zhēng)。

3.1.2 藍(lán)色信標(biāo)選擇

藍(lán)色信標(biāo)的選擇過程需要通過紅色信標(biāo)的輔助。當(dāng)紅色信標(biāo)計(jì)算出最大redhop數(shù)K以后，隨機(jī)按梯度路由選擇一條路徑發(fā)送關(guān)于K和K'的消息，其中K'為紅色信標(biāo)選取的不超過K的整數(shù)，當(dāng)消息抵達(dá)某個(gè)redhop=K'的節(jié)點(diǎn)上，消息停止，并且該redhop=K'的節(jié)點(diǎn)選為藍(lán)色信標(biāo)。藍(lán)色信標(biāo)同樣向網(wǎng)絡(luò)中其他節(jié)點(diǎn)廣播計(jì)數(shù)消息。同時(shí)利用piggyback消息將K和K'傳送給其他節(jié)點(diǎn)。我們下面重點(diǎn)研究如何確定K'。

3.2 相切輪廓策略TC

在隨機(jī)C-cast模型中，采用相切輪廓(tangent contours，TC)數(shù)據(jù)副本分發(fā)策略(如圖3所示)，TC類似于理想模型中的RiB和BiR。在TC策略中，數(shù)據(jù)生產(chǎn)者節(jié)點(diǎn)首先比較自己的bluehop和redhop數(shù)的大小。如果bluehop小于redhop，數(shù)據(jù)生產(chǎn)者采用BiR策略。如果redhop小于bluehop，數(shù)據(jù)生產(chǎn)者采用RiB策略。不過在隨機(jī)模型中，數(shù)據(jù)查詢過程采用同樣的TC策略，并不能保證100%的數(shù)據(jù)查詢成功率。數(shù)據(jù)查詢成功率主要受兩個(gè)信標(biāo)之間的跳步距離(即K')的影響。下面通過研究TC策略的最差情況，來分析信標(biāo)之間的跳步距離與數(shù)據(jù)查詢成功率的關(guān)系，并給出確定信標(biāo)跳步距離的啟發(fā)式算法。

圖3 隨機(jī)C-cast模型的數(shù)據(jù)副本分發(fā)

3.3 TC最差情況

3.3.1 網(wǎng)絡(luò)區(qū)域與紡錘體區(qū)域

假設(shè)兩個(gè)信標(biāo)之間的跳步數(shù)記為h，理論上如果網(wǎng)絡(luò)覆蓋的區(qū)域無限大，所有半徑小于h的輪廓會(huì)形成一個(gè)環(huán)，而且兩種顏色的輪廓在兩個(gè)信標(biāo)之間的區(qū)域相互重疊形成一個(gè)紡錘體區(qū)域。在如圖4中的紡錘體區(qū)域內(nèi)，如果某個(gè)紅色輪廓和藍(lán)色輪廓相切，那么兩個(gè)輪廓共享的節(jié)點(diǎn)滿足bluehop+redhop=h。紅色輪廓和藍(lán)色輪廓合稱為一個(gè)BR輪廓對(duì)。在圖4(a)中，任意兩個(gè)BR輪廓對(duì)在紡錘體區(qū)域相交于兩點(diǎn)，即假設(shè)所有的節(jié)點(diǎn)都落在該紡錘體之內(nèi)，并且信標(biāo)節(jié)點(diǎn)位于兩個(gè)圓心點(diǎn)上，則可以證明在這種模型下數(shù)據(jù)查詢成功率也可以達(dá)到100%。不過真實(shí)的網(wǎng)絡(luò)區(qū)域不是無限的，而且也不一定是紡錘體的部署形狀，所以真實(shí)的網(wǎng)絡(luò)區(qū)域和紡錘體區(qū)域不一定是重疊的(圖4(b))。下面論述紡錘體區(qū)域和網(wǎng)絡(luò)區(qū)域的重疊程度決定了數(shù)據(jù)查詢成功率。

圖4

3.3.2 最差情況下的K'值選取

因?yàn)榧t色信標(biāo)是隨機(jī)選取的，所以K值不是固定的，不過可以證明 K∈[Kd/2，Kd]，Kd為網(wǎng)絡(luò)的直徑。本節(jié)研究在K值未知的情況下如何確定K'值。

定義3信標(biāo)掃視區(qū)域。分別過兩個(gè)信標(biāo)點(diǎn)作垂直于兩個(gè)信標(biāo)連線的直線。這兩條直線將整個(gè)網(wǎng)絡(luò)區(qū)域分成三個(gè)部分。其中位于兩條直線之間的區(qū)域內(nèi)的節(jié)點(diǎn)被兩個(gè)信標(biāo)連線分成兩個(gè)子區(qū)域。在這兩個(gè)子區(qū)域中，其中覆蓋節(jié)點(diǎn)面積較大的一個(gè)區(qū)域稱為信標(biāo)掃視區(qū)域。其面積記為SA。圖5(a)中的四邊形ABEF為AB的信標(biāo)掃視區(qū)域。

圖5 相切輪廓策略最差情況證明示意圖

定義4信標(biāo)掃視半紡錘體區(qū)域。兩個(gè)信標(biāo)生成的紡錘體區(qū)域被兩個(gè)信標(biāo)連線等分為兩部分，這兩部分都稱為信標(biāo)掃視半紡錘體區(qū)域。圖5(b)中的半個(gè)紡錘體ORB即為RB的信標(biāo)掃視半紡錘體區(qū)域。

定理2假設(shè)兩個(gè)信標(biāo)之間的跳步距離為h，且h小于網(wǎng)絡(luò)的直徑Kd。當(dāng)兩個(gè)信標(biāo)位于正方形網(wǎng)絡(luò)區(qū)域的對(duì)角線上，且其中一個(gè)位于正方形區(qū)域的頂點(diǎn)位置，那么對(duì)于距離h，此時(shí)信標(biāo)掃視區(qū)域的面積最小。

證明:如圖 5(a)所示，對(duì)任意線段 AB，如果|AB|=|CD|，那么 |EE'|+|FF'|≥ |GG'|?SEE'FF'≥SGG'D?SACD=SGG'D/2≤SEE'FF'/2≤SAAB。

下面的公式描述網(wǎng)絡(luò)區(qū)域與紡錘體區(qū)域的重疊程度，

其中Sc為信標(biāo)掃視半紡錘體區(qū)域覆蓋的信標(biāo)掃視區(qū)域面積，SN為信標(biāo)掃視區(qū)域的面積。So為信標(biāo)掃視半紡錘體區(qū)域的面積。定理2描述了針對(duì)h，兩個(gè)信標(biāo)位置的最差情況。根據(jù)式(2)得出在最差情況下，網(wǎng)絡(luò)區(qū)域與紡錘體區(qū)域的重疊程度為，

其中L近似為正方形區(qū)域邊長(zhǎng)的跳步距離。當(dāng)0≤h≤L，r(h)的最大值約為50%;當(dāng)?shù)淖畲笾导s為52%，其中h≈1.1L。這意味著最差情況的下界當(dāng)h≈1.1L達(dá)到最大。因?yàn)榧t色信標(biāo)是隨機(jī)選取的，所以K∈[Kd/2，Kd]。K的期望值為，

當(dāng)r(E(K))≈51%，為期望最差情況的網(wǎng)絡(luò)區(qū)域與紡錘體區(qū)域的重疊程度。

最差情況網(wǎng)絡(luò)區(qū)域與紡錘體區(qū)域的重疊程度反映了任意一對(duì)BR輪廓的相交率的下界。在實(shí)際情況中相交率可以達(dá)到80%。因?yàn)樵谏厦娴募僭O(shè)和公式中，如果節(jié)點(diǎn)沒有被信標(biāo)掃視半紡錘體區(qū)域覆蓋，則認(rèn)為不能發(fā)現(xiàn)其他數(shù)據(jù)也不能被發(fā)現(xiàn)。在實(shí)際情況中即使節(jié)點(diǎn)位于信標(biāo)掃視半紡錘體區(qū)域以外，仍然有可能經(jīng)過繞路轉(zhuǎn)發(fā)抵達(dá)信標(biāo)掃視半紡錘體區(qū)域之內(nèi)。即使在輪廓被分成兩個(gè)段的情況下，同樣可以利用邊界點(diǎn)進(jìn)行繞路，以便達(dá)到數(shù)據(jù)發(fā)現(xiàn)的目的。即使在理想模型下，利用上面的公式得到的相交率也僅為60%，所以說公式3的結(jié)果是非常保守的。

根據(jù)以上結(jié)果，提出如何確定K'值的啟發(fā)算法。首先紅色信標(biāo)得到K值，并估計(jì)出L的值。如果K值小于1.1L，則K'設(shè)為 K;如果K 值大于1.1L，則 K'設(shè)為1.1L。下面給出如何估計(jì)L值的方法。

3.4 L值估計(jì)算法

假設(shè)L值在網(wǎng)絡(luò)部署以前沒有分配給每個(gè)節(jié)點(diǎn)，根據(jù)式(4)紅色信標(biāo)節(jié)點(diǎn)需要估計(jì)L值的大小。如果網(wǎng)絡(luò)是正方形區(qū)域且稠密的，則紅色信標(biāo)節(jié)點(diǎn)在收到的所有ACK中可以提取到4個(gè)K值，分別為K1＜K2＜K3＜K4。如圖6所示，下面的方程可以求解L的近似值。設(shè) x1＜x2＜x3＜x4，則滿足

方程 5 可以解出 x1，x2，x3，x4，易得 x1+x4=x2+x3=L。

圖6 L值估計(jì)

4 性能測(cè)試

本節(jié)討論C-cast的模擬測(cè)試結(jié)果。因?yàn)槔硐隒-cast模型在理論上能夠保證數(shù)據(jù)查詢成功率為100%，所以只針對(duì)隨機(jī)模型進(jìn)行了模擬。在模擬中，考慮了三種性能指標(biāo):數(shù)據(jù)查詢成功率、存儲(chǔ)開銷和負(fù)載均衡。雖然隨機(jī)C-cast模型可以用于其它形狀的網(wǎng)絡(luò)中，但為了方便起見，只研究和模擬了在正方形區(qū)域網(wǎng)絡(luò)的情況。使用擾動(dòng)網(wǎng)格拓?fù)鋪聿渴饌鞲衅鞴?jié)點(diǎn)。在擾動(dòng)網(wǎng)格拓?fù)渚W(wǎng)絡(luò)中，每個(gè)傳感器節(jié)點(diǎn)按照一定的擾動(dòng)因子偏離原來的網(wǎng)格點(diǎn)，擾動(dòng)因子的幅度為1 m～10 m。對(duì)于C-cast，假設(shè)節(jié)點(diǎn)沒有位置信息。為了模擬GHT和Double rulings，假設(shè)節(jié)點(diǎn)能夠通過定位算法來確定位置，定位的誤差是隨機(jī)產(chǎn)生的。節(jié)點(diǎn)的傳輸半徑為15 m。

4.1 數(shù)據(jù)查詢成功率

隨機(jī)C-cast模型中，首先我們通過模擬來驗(yàn)證數(shù)據(jù)查詢成功率受兩個(gè)信標(biāo)之間的跳步距離影響。在測(cè)試環(huán)境中部署了1 600個(gè)節(jié)點(diǎn)，并隨機(jī)生成50個(gè)數(shù)據(jù)生產(chǎn)者和50個(gè)數(shù)據(jù)消費(fèi)者節(jié)點(diǎn)。然后隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為紅色信標(biāo)節(jié)點(diǎn)，在不同的紅色輪廓上分別隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為藍(lán)色信標(biāo)節(jié)點(diǎn)。對(duì)每組紅色和藍(lán)色信標(biāo)，50個(gè)數(shù)據(jù)生產(chǎn)者根據(jù)C-cast路徑分發(fā)數(shù)據(jù)，50個(gè)數(shù)據(jù)消費(fèi)者利用基本查詢過程檢索數(shù)據(jù)。網(wǎng)絡(luò)的直徑為39跳。當(dāng)兩個(gè)信標(biāo)的距離介于20到30之間時(shí)，數(shù)據(jù)查詢成功率的平均值大于75%(圖7)。

圖7 藍(lán)色信標(biāo)和紅色信標(biāo)的不同跳步距離影響了平均數(shù)據(jù)查詢成功率

通過3.3節(jié)中的算法選擇兩個(gè)信標(biāo)之間的跳步距離，并利用邊界輔助查詢策略與GHT和rumor路由進(jìn)行比較。在GHT中，考慮了定位的誤差。通過模擬發(fā)現(xiàn)(圖8)，定位誤差會(huì)嚴(yán)重的影響GHT數(shù)據(jù)查詢成功率。這是因?yàn)樵贕HT中使用的是地理貪婪路由協(xié)議，即使在網(wǎng)絡(luò)中不存在空洞，由于定位誤差的影響，網(wǎng)絡(luò)中也會(huì)產(chǎn)生一些虛擬的空洞，造成局部極小值的發(fā)生。我們將誤差從1m逐步提高到9m，發(fā)現(xiàn)GHT的平均數(shù)據(jù)查詢率隨著誤差增大而降低。而C-cast和rumor路由不受定位誤差的影響。rumor路由的數(shù)據(jù)查詢成功率平均為67%，而C-cast的平均數(shù)據(jù)查詢成功率可以達(dá)到80%。因?yàn)镈ouble rulings的機(jī)制和GHT是一樣的，其數(shù)據(jù)查詢成功率也會(huì)受到定位誤差的影響。

4.2 存儲(chǔ)開銷

另一個(gè)值得關(guān)注的性能指標(biāo)為存儲(chǔ)開銷(圖9)。比較C-cast與Double rulings的存儲(chǔ)開銷。模擬不同規(guī)模的網(wǎng)絡(luò)中存儲(chǔ)開銷。對(duì)每種規(guī)模，進(jìn)行了1 000次測(cè)試。通過比較，C-cast的存儲(chǔ)開銷要稍微大于Double rulings，比如說在圖9中，當(dāng)網(wǎng)絡(luò)為3000個(gè)節(jié)點(diǎn)的時(shí)候，C-cast需要的存儲(chǔ)節(jié)點(diǎn)個(gè)數(shù)為170，而Double rulings為 140。不過在理論上 C-cast和Double rulings所需要的存儲(chǔ)節(jié)點(diǎn)的個(gè)數(shù)是同一規(guī)模的，即假設(shè)網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模為N，則一條存儲(chǔ)路徑的規(guī)模為O(N1/2)。因此說C-cast在存儲(chǔ)開銷上和Double rulings是同一水平。

圖8 GHT，rumor路由和 C-cast在(Kd=30，K=25)時(shí)的數(shù)據(jù)查詢成功率

圖9 一個(gè)數(shù)據(jù)生產(chǎn)者的存儲(chǔ)節(jié)點(diǎn)的個(gè)數(shù)

4.3 負(fù)載均衡

圖10 負(fù)載均衡比較

利用網(wǎng)格網(wǎng)絡(luò)拓?fù)鋪頊y(cè)試Double rulings，C-cast的負(fù)載均衡。網(wǎng)絡(luò)的規(guī)模為3600個(gè)節(jié)點(diǎn)。隨機(jī)產(chǎn)生50個(gè)數(shù)據(jù)生產(chǎn)者，然后分別利用Double rulings和C-cast來分發(fā)數(shù)據(jù)副本。圖10(a)為 Double rulings的負(fù)載狀況。Double rulings中每個(gè)節(jié)點(diǎn)的存儲(chǔ)小于10，網(wǎng)絡(luò)的中心位置的負(fù)載遠(yuǎn)遠(yuǎn)大于網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)負(fù)載。圖10(b)說明了C-cast的負(fù)載狀況，C-cast中每個(gè)節(jié)點(diǎn)的負(fù)載也小于10，但是在C-cast中整個(gè)網(wǎng)絡(luò)的負(fù)載更加平均一些。

綜上所述，通過模擬發(fā)現(xiàn)C-cast在沒有位置的情況下，最關(guān)鍵的數(shù)據(jù)查詢成功率是最好的，其余指標(biāo)能夠達(dá)到基于位置的策略相當(dāng)?shù)乃健?/p>

5 結(jié)論

針對(duì)大規(guī)模無線傳感器中對(duì)等節(jié)點(diǎn)的數(shù)據(jù)發(fā)現(xiàn)和傳輸問題，本文提出了C-cast協(xié)議，一種無位置的數(shù)據(jù)存儲(chǔ)和發(fā)現(xiàn)策略。該協(xié)議通過兩個(gè)信標(biāo)節(jié)點(diǎn)構(gòu)建輪廓覆蓋網(wǎng)，數(shù)據(jù)沿著輪廓根據(jù)不同的策略進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。該協(xié)議的優(yōu)勢(shì)是不依賴于節(jié)點(diǎn)的位置信息。本文提出了兩種C-cast網(wǎng)絡(luò)模型，理想C-cast模型和隨機(jī)C-cast模型。C-cast可以保證數(shù)據(jù)查詢成功率，同時(shí)能夠兼顧與基于位置策略等同的存儲(chǔ)開銷和負(fù)載均衡。未來的工作包括對(duì)C-cast中多數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)編碼和在稀疏網(wǎng)絡(luò)中的應(yīng)用。

[1]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].清華大學(xué)出版社，2005.

[2]盧漢良，李德駿，楊燦軍，等.深海海底觀測(cè)網(wǎng)絡(luò)信息采集監(jiān)測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].傳感技術(shù)學(xué)報(bào)，2011，24(3):407－411.

[3]樊鐳，龔聞天，施曉秋.大規(guī)模無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集與處理系統(tǒng)設(shè)計(jì)[J].傳感技術(shù)學(xué)報(bào)，2011，24(11):1611－1616.

[4]陶孜謹(jǐn)，酈蘇丹，徐金義，等.大規(guī)模無線傳感器網(wǎng)絡(luò)中面向ANY型查詢的能量高效數(shù)據(jù)分發(fā)算法[J].國(guó)防科技大學(xué)學(xué)報(bào)，2009，31(1):64－69.

[5]Luo H，Ye F，Cheng J，et al.TTDD:Two-Tier Data Dissemination in Large-Scale Wireless Sensor Networks[J].Wireless Networks，2005，11:161－175.

[6]Karp B，Ratnasamy S，Yin L，et al.GHT:A Geographic Hash Table for DataCentric Storage[C]//Proceedings of the First ACM international Workshop on Wireless Sensor Networks and Applications(WSNA)[C]//Atlanda，Georgia，USA，2002.

[7]Sarkar R，Zhu X，Gao J.Double Rulings for Information Brokerage in Sensor Networks[C]//Proceedings of the 12th ACM Annual International Conference on Mobile Computing and Networking(MobiCom)[C]//Los Angeles，CA，USA，2006.

[8]李志剛，肖儂，褚福勇.大規(guī)模無線傳感器網(wǎng)絡(luò)中基于振蕩軌跡的數(shù)據(jù)存儲(chǔ)與發(fā)現(xiàn)機(jī)制[J].計(jì)算機(jī)研究與發(fā)展，2010，47(11):1911－1918.

[9]Li M，Liu Y.Rendered Path:Range-FreeLocalization in Anisotropic Sensor Networks with Holes[C]//Proceedings of the 13th ACM Annual International Conference on Mobile Computing and Networking(MobiCom)[C]//2007.

[10]Yang Z，Liu Y.Quality of Trilateration:Confidence-Based Iterative Localization，presented at IEEE ICDCS [C]//Beijing，China，2008.

[11]Braginsky D，Estrin D.Rumor Routing Algorithm for Sensor Networks[C]//Proceedings of the 8th ACM Annual International Conference on Mobile Computing and Networking(MobiCom)[C]//Atlanda，Georgia，USA，2002.

[12]Chessa S，Caruso A，De S，et al.GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks[C]//Proceedings of the 24th IEEE Conference on Computer Communications(InfoCom)[C]//Miami，F(xiàn)L，USA，2005.

[13]Wu X B，Chen G，Sajal K Das.Avoiding Energy Holes in Wireless Sensor Networks with Nonuniform Node Distribution[C]//IEEE Transactions on Parallel and Distributed Systems[J].2008，19(5):710－720.