李志剛，吳君青

(解放軍理工大學指揮自動化學院，南京210007)

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

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

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

1 輪廓覆蓋網構建

1.1 網絡模型

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

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

1.2 輪廓覆蓋網

本文的工作，主要是利用兩個信標節(jié)點來抽取整個網絡的拓撲和鏈接信息。為方便下文的論述，稱其中一個信標為藍色信標，另一個為紅色信標。兩個信標都向網絡中其他節(jié)點廣播跳步計數消息。其他節(jié)點在收到跳步計數消息以后，分別計算到兩個信標的最短跳步數。本節(jié)主要描述如何構建和初始化兩個輪廓覆蓋網，暫時不考慮信標的選擇過程，假設兩個信標已經選定。關于如何選擇信標在下面的章節(jié)會有描述。信標節(jié)點只在網絡初始階段起作用，在輪廓覆蓋網構建以后，其能量消耗過程和其他節(jié)點是相似的。

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

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

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

圖1 輪廓線的建立(信標節(jié)點及跳步數為偶數的節(jié)點用粗點表示)

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

2 理想C-cast模型

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

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

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

當節(jié)點(b，r)感知到數據以后，則觸發(fā)數據副本分發(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顯示了這四種策略。每個節(jié)點采用每種策略的概率都為25%。不失一般性，用RiB策略作為例子說明數據副本分發(fā)的過程。在策略RiB中，節(jié)點(b，r)需要做兩個決定。第一，決定首先沿紅色輪廓CRrC-cast數據。第二，在數據中加入通知所有位于紅色輪廓CRr上的節(jié)點尋找具有極大bluehop的節(jié)點的消息。如果節(jié)點M(m，r)發(fā)現自己的bluehop比所有鄰居的bluehop都要小，則M發(fā)起沿藍色輪廓CBm的C-cast。數據在經過的節(jié)點上留下一個副本。該過程產生的紅色輪廓和藍色輪廓，由節(jié)點M連接在一起，形成一條路徑，稱為聯合C-cast路徑，簡稱為C-cast路徑。設計四種策略的原因是為了滿足負載均衡。

2.2 數據查詢過程

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

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

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

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

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

3 隨機C-cast模型

出于網絡實際情況的考慮，信標節(jié)點不一定位于網絡中的特殊位置，而是允許出現在任何位置，這種情況稱為隨機C-cast模型。

3.1 信標選擇

在隨機C-cast模型中，依然假設網絡區(qū)域為正方形區(qū)域。下面首先討論信標的隨機選擇過程。

3.1.1 紅色信標選擇

首先，在網絡中隨機選擇一個節(jié)點作為紅色信標。然后紅色信標向網絡中的其他節(jié)點廣播跳步計數消息。如果中間節(jié)點發(fā)現不能再向其他節(jié)點發(fā)送計數消息，則逆向往紅色信標發(fā)送ACK消息。通過ACK消息，紅色信標可以計算網絡中最大的redhop數K。在沒有全局調度的情況下，可能有幾個節(jié)點同時發(fā)起紅色信標競爭的消息。

在這種情況下，這些節(jié)點可以按照時間戳或者節(jié)點ID進行競爭。

3.1.2 藍色信標選擇

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

3.2 相切輪廓策略TC

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

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

3.3 TC最差情況

3.3.1 網絡區(qū)域與紡錘體區(qū)域

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

圖4

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

因為紅色信標是隨機選取的，所以K值不是固定的，不過可以證明 K∈[Kd/2，Kd]，Kd為網絡的直徑。本節(jié)研究在K值未知的情況下如何確定K'值。

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

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

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

定理2假設兩個信標之間的跳步距離為h，且h小于網絡的直徑Kd。當兩個信標位于正方形網絡區(qū)域的對角線上，且其中一個位于正方形區(qū)域的頂點位置，那么對于距離h，此時信標掃視區(qū)域的面積最小。

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

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

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

其中L近似為正方形區(qū)域邊長的跳步距離。當0≤h≤L，r(h)的最大值約為50%;當的最大值約為52%，其中h≈1.1L。這意味著最差情況的下界當h≈1.1L達到最大。因為紅色信標是隨機選取的，所以K∈[Kd/2，Kd]。K的期望值為，

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

最差情況網絡區(qū)域與紡錘體區(qū)域的重疊程度反映了任意一對BR輪廓的相交率的下界。在實際情況中相交率可以達到80%。因為在上面的假設和公式中，如果節(jié)點沒有被信標掃視半紡錘體區(qū)域覆蓋，則認為不能發(fā)現其他數據也不能被發(fā)現。在實際情況中即使節(jié)點位于信標掃視半紡錘體區(qū)域以外，仍然有可能經過繞路轉發(fā)抵達信標掃視半紡錘體區(qū)域之內。即使在輪廓被分成兩個段的情況下，同樣可以利用邊界點進行繞路，以便達到數據發(fā)現的目的。即使在理想模型下，利用上面的公式得到的相交率也僅為60%，所以說公式3的結果是非常保守的。

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

3.4 L值估計算法

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

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

圖6 L值估計

4 性能測試

本節(jié)討論C-cast的模擬測試結果。因為理想C-cast模型在理論上能夠保證數據查詢成功率為100%，所以只針對隨機模型進行了模擬。在模擬中，考慮了三種性能指標:數據查詢成功率、存儲開銷和負載均衡。雖然隨機C-cast模型可以用于其它形狀的網絡中，但為了方便起見，只研究和模擬了在正方形區(qū)域網絡的情況。使用擾動網格拓撲來部署傳感器節(jié)點。在擾動網格拓撲網絡中，每個傳感器節(jié)點按照一定的擾動因子偏離原來的網格點，擾動因子的幅度為1 m～10 m。對于C-cast，假設節(jié)點沒有位置信息。為了模擬GHT和Double rulings，假設節(jié)點能夠通過定位算法來確定位置，定位的誤差是隨機產生的。節(jié)點的傳輸半徑為15 m。

4.1 數據查詢成功率

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

圖7 藍色信標和紅色信標的不同跳步距離影響了平均數據查詢成功率

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

4.2 存儲開銷

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

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

圖9 一個數據生產者的存儲節(jié)點的個數

4.3 負載均衡

圖10 負載均衡比較

利用網格網絡拓撲來測試Double rulings，C-cast的負載均衡。網絡的規(guī)模為3600個節(jié)點。隨機產生50個數據生產者，然后分別利用Double rulings和C-cast來分發(fā)數據副本。圖10(a)為 Double rulings的負載狀況。Double rulings中每個節(jié)點的存儲小于10，網絡的中心位置的負載遠遠大于網絡邊緣的節(jié)點負載。圖10(b)說明了C-cast的負載狀況，C-cast中每個節(jié)點的負載也小于10，但是在C-cast中整個網絡的負載更加平均一些。

綜上所述，通過模擬發(fā)現C-cast在沒有位置的情況下，最關鍵的數據查詢成功率是最好的，其余指標能夠達到基于位置的策略相當的水平。

5 結論

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

[1]孫利民，李建中，陳渝，等.無線傳感器網絡[M].清華大學出版社，2005.

[2]盧漢良，李德駿，楊燦軍，等.深海海底觀測網絡信息采集監(jiān)測系統(tǒng)設計與實現[J].傳感技術學報，2011，24(3):407－411.

[3]樊鐳，龔聞天，施曉秋.大規(guī)模無線傳感器網絡數據收集與處理系統(tǒng)設計[J].傳感技術學報，2011，24(11):1611－1616.

[4]陶孜謹，酈蘇丹，徐金義，等.大規(guī)模無線傳感器網絡中面向ANY型查詢的能量高效數據分發(fā)算法[J].國防科技大學學報，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ī)模無線傳感器網絡中基于振蕩軌跡的數據存儲與發(fā)現機制[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，FL，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.