無線自組織傳感網(wǎng)鄰居節(jié)點(diǎn)檢測協(xié)議及其實(shí)現(xiàn)

林 炳，仇 建

(杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)研究所，浙江杭州310018)

0 引言

定義兩個具有有效通信鏈路的節(jié)點(diǎn)互稱為鄰居，可以用一個固定半徑來表示節(jié)點(diǎn)有效通信范圍，而所有在此范圍內(nèi)的節(jié)點(diǎn)都是其鄰居，這個模型被稱為盤狀模型［1］。在分布式傳感網(wǎng)初始化之前，節(jié)點(diǎn)沒有任何鄰居信息，無法形成網(wǎng)絡(luò)。為實(shí)現(xiàn)傳感網(wǎng)自組織、路由選擇、介質(zhì)訪問控制和數(shù)據(jù)聚合等工作，鄰居節(jié)點(diǎn)檢測必不可少。之前，已經(jīng)有不少研究人員在這個問題上進(jìn)行了一定的研究，比如最佳鏈路狀態(tài)路由［2］和按需自組織路由［3］等路由協(xié)議方案。由于傳感網(wǎng)的能量受限，一些減少鄰居查找耗費(fèi)時(shí)間以降低能耗的擴(kuò)展方案也被相繼提出。例如，為使鄰居檢測過程更加適應(yīng)高移動性網(wǎng)絡(luò)，鄰居信息更新頻率可自適應(yīng)調(diào)整［4］，通過鏈路層反饋的鄰居檢測方法也是達(dá)到快速鄰居檢測的一種擴(kuò)展方案［5］。但是，以上方法存在幾個比較普遍的問題，包括探測率不足、耗時(shí)過久、能耗較高等。為解決以上問題，本文提出了一種改進(jìn)的鄰居檢測方案，并建立以接收端為視角的鄰居檢測分析模型，使其能適用于大部分實(shí)際情況，并利用網(wǎng)絡(luò)仿真和測試床檢測對其進(jìn)行驗(yàn)證。

1 方案描述

本文提出的鄰居檢測方案采取隨機(jī)選擇時(shí)間片的方式廣播Hello控制包形成單方向鄰居檢測，并通過重復(fù)廣播來提高鄰居檢測概率。

1.1 網(wǎng)絡(luò)模型和參數(shù)定義

傳感網(wǎng)節(jié)點(diǎn)由于沒有預(yù)先分配信道，每個節(jié)點(diǎn)通過隨機(jī)時(shí)間接入信道來廣播控制數(shù)據(jù)包以交換名片信息，從而實(shí)現(xiàn)鄰居檢測。為便于方案描述，提出以下假設(shè):

(1)網(wǎng)絡(luò)同質(zhì)，單位密度為ρ個節(jié)點(diǎn)隨機(jī)分布在一個二維平面內(nèi)。節(jié)點(diǎn)具有相同傳輸功率和接受半徑，因此每個節(jié)點(diǎn)的有效無線電接收范圍都等于r;

(2)信道按時(shí)間劃分成多個時(shí)間片，每個時(shí)間片的長度等于傳輸持續(xù)時(shí)間加上包的最長傳輸延遲;

(3)所有節(jié)點(diǎn)完全同步，數(shù)據(jù)包傳輸都發(fā)生在一個特定的時(shí)間片內(nèi);

(4)數(shù)據(jù)包丟失的唯一原因是碰撞，或稱之為兩跳鄰居同步傳輸干擾。以接收者的角度來說，兩跳干擾等同于兩個一跳鄰居同時(shí)傳輸，此假設(shè)有益于之后分析;

(5)簡單來講，定義一跳鄰居和兩跳鄰居的平均值分別為N1和N2。T個連續(xù)時(shí)間片組成一個幀。經(jīng)過n個幀的時(shí)間后，檢測到N1個一跳節(jié)點(diǎn)和N2個兩跳節(jié)點(diǎn)的概率分別為p1(n)和p2(n)。

1.2 鄰居檢測過程

作為發(fā)送方，每個節(jié)點(diǎn)從每幀中隨機(jī)選擇一個時(shí)間片，廣播包含自身ID和當(dāng)前單跳鄰居ID的信息包。因?yàn)闊o法實(shí)現(xiàn)預(yù)先規(guī)劃，碰撞無法避免從而部分包傳輸失敗。隨著多次重傳，更多的單跳鄰居能夠成功接收該節(jié)點(diǎn)發(fā)送的信息。

作為接收方，一旦節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)發(fā)送來的鄰居信息包，它將存儲傳輸節(jié)點(diǎn)的ID至單跳鄰居表中。而鄰居信息包中存放的單跳鄰居ID被識別為臨時(shí)兩跳鄰居，并存儲在臨時(shí)兩跳鄰居表內(nèi)。這些臨時(shí)兩跳鄰居可能與接收節(jié)點(diǎn)直接通信，從而確認(rèn)為單跳鄰居。在整個過程結(jié)束后，通過排除單跳鄰居ID號，可以記錄正確的兩跳鄰居表。

2 理論分析

作為檢測兩跳鄰居的基本步驟，將逐步分析一跳鄰居檢測模型，以確定最佳的幀結(jié)構(gòu)。雖然已經(jīng)對這種情況做出推導(dǎo)［6］，但本文的分析是從接收者的角度出發(fā)，如圖1所示的節(jié)點(diǎn)A，解決該情況提供了更好的方法。

從圖1中可以很清楚地發(fā)現(xiàn)，節(jié)點(diǎn)A能在特定的時(shí)間片成功接收的條件是，當(dāng)且僅當(dāng)節(jié)點(diǎn)B－F中的一個選擇了這個特定時(shí)間片廣播信號包，并且其他任何一跳鄰居(N1－1)節(jié)點(diǎn)和節(jié)點(diǎn)A本身都必須保持沉默。例如，節(jié)點(diǎn)C和E選中了第一個幀內(nèi)的相同時(shí)間片，那么節(jié)點(diǎn)A將不能收到兩者的信號包。每個節(jié)點(diǎn)選中某個時(shí)間片的概率是1/T，T是一個幀包含的隨機(jī)進(jìn)入信道的時(shí)間片數(shù)量。因此，單個幀時(shí)間內(nèi)任意節(jié)點(diǎn)被檢測為鄰居的概率是。p=(1 －1/T)N1。

在整個網(wǎng)絡(luò)范圍內(nèi)，這個概率就等于單個幀時(shí)間內(nèi)檢測到的一跳鄰居數(shù)量占總鄰居數(shù)的平均百分比:

圖1 一跳鄰居檢測插圖

推而廣之，經(jīng)過n個幀時(shí)間后單跳鄰居被發(fā)現(xiàn)的概率為:

兩跳鄰居檢測數(shù)學(xué)模型的建立可以盡量減少鄰居檢測周期的總持續(xù)時(shí)間，總持續(xù)時(shí)間等于幀長度乘以幀數(shù)量:

重新整理式3，n可以表達(dá)成關(guān)于T的等式:

因此，該過程的總持續(xù)時(shí)間可以描述成一個關(guān)于指定概率(檢測出所有一跳鄰居的概率)的表達(dá)式:

式中，一跳鄰居檢測概率是系統(tǒng)需求，平均鄰居數(shù)N1由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)決定，q由給定調(diào)制方案下的無線電信道特性確定，式5只取決于如何選擇幀長度T。

因此，為了獲得一個盡量小的f(T)，最常見的操作就是找到一個特定的T使得df(T)/dT=0，求導(dǎo)結(jié)果為:

通過檢驗(yàn)式5的二階微分，不難發(fā)現(xiàn)發(fā)f(T)的最小值點(diǎn)存在且只有一個，但求取數(shù)值解的過程過于繁瑣而且精確度超過實(shí)際應(yīng)用所需。因此，采用MATLAB仿真計(jì)算的方式求取近似曲線。結(jié)果如圖2所示:

通過檢驗(yàn)擬合曲線，可以得到最佳值:

當(dāng)幀長度是一跳鄰居的1.45倍時(shí)，特定概率下的一跳鄰居檢測速度是最快的。如果幀長度T比1.45N1短，就需要更多的幀來達(dá)到相同的一跳鄰居檢測概率。如果幀長度T相比1.45N1長，即使需要的幀更少，但發(fā)送鄰居信號的總持續(xù)時(shí)間仍然大于采用1.45N1時(shí)的長度。

圖2 最佳信號包傳輸時(shí)間幀長度

3 仿真結(jié)果與分析

為了驗(yàn)證本文提出的相關(guān)理論，采用OMNET仿真和節(jié)點(diǎn)實(shí)際硬件測試。其中，仿真的場景根據(jù)節(jié)點(diǎn)數(shù)量的不同分為3個:50個節(jié)點(diǎn)隨機(jī)分布在邊長為500m的正方形區(qū)域中;200個節(jié)點(diǎn)隨機(jī)分布在邊長為1 000m的正方形區(qū)域中;800個節(jié)點(diǎn)隨機(jī)分布在邊長為2 000m的正方形區(qū)域中。所有節(jié)點(diǎn)都擁有100m有效接收范圍，而任意數(shù)據(jù)包碰撞將導(dǎo)致接收失敗。實(shí)驗(yàn)結(jié)果顯示，在第8個時(shí)間片時(shí)檢測到的數(shù)量基本達(dá)到95%以上。單跳鄰居的平均數(shù)量為5.3，根據(jù)式7預(yù)測到的最短持續(xù)時(shí)間的幀長度是7.75個時(shí)間片。由于它并不是一個整數(shù)，所以可以將8個時(shí)間片作為最佳幀長度。

在測試床硬件實(shí)驗(yàn)過程中，如圖3所示，實(shí)驗(yàn)節(jié)點(diǎn)數(shù)為25個，采用接近正6邊形的分布方式，平均單跳鄰居數(shù)量為6，根據(jù)式7預(yù)測到的最短持續(xù)時(shí)間的幀長度是8.7，取整為9。實(shí)驗(yàn)前臺顯示過程和最終結(jié)果如圖4所示。圖4中界面上方為對應(yīng)拓?fù)鋱D，左下方為節(jié)點(diǎn)相互之間的連接關(guān)系，黃色表示單跳鄰居關(guān)系而綠色表示兩條鄰居關(guān)系。圖4右下方，每個節(jié)點(diǎn)的單跳和兩條節(jié)點(diǎn)數(shù)被表示。經(jīng)過7次重傳后，全部的節(jié)點(diǎn)連接都被找到。

圖3 無線傳感網(wǎng)測試環(huán)境

圖4 硬件實(shí)驗(yàn)結(jié)果

4 結(jié)束語

無線傳感網(wǎng)絡(luò)和自組織網(wǎng)絡(luò)不管是在處理能力還是能量上均受到限制，使用消息重傳機(jī)制等方法查找鄰居節(jié)點(diǎn)由于能耗高，耗時(shí)久并不能滿足需求。本文提出的鄰居檢測方案，以接收端為視角，采用隨機(jī)選擇時(shí)間片的方式發(fā)送Hello消息包。本文通過嚴(yán)謹(jǐn)?shù)睦碚撝R分析最佳幀結(jié)構(gòu)，并利用網(wǎng)絡(luò)仿真和測試床檢測驗(yàn)證。在未來，可以將此鄰居檢測方案加入實(shí)際部署的無線傳感網(wǎng)絡(luò)系統(tǒng)，從而進(jìn)一步體現(xiàn)其廣泛適用性。

［1］ Gupta P，Kumar P.The Capacity of Wireless Networks［J］.IEEE Transactions on Information Theory，2000，46(5):388－404.

［2］ Clausen T，Jacquet P，Laouiti A.Optimized Link State Routing Protocol［C］.Lahore:IEEE International Multitopic Conference，2001:233 －246.

［3］ Perkins C，Belding-Royer E，Das S.Ad Hoc On-demand Distance Vector Routing［C］.Vienna:Internet Engineering Task Force，2003:152 －168.

［4］ Benzaid M，Minet P，Agha K.Integrating Fast Mobility in the OLSR Routing Protocol［C］.New York:IEEE Conference in Mobile and Wireless Communications Networks，2002:310 －356.

［5］ Voorhaen M，Blondia C.Analyzing the Impact of Neighbor Sensing on the Performance of the OLSR Protocol［C］.San Francisco:International Symposium on Modeling and Optimization in Mobile，2006:248 －276.

［6］ Bao L，Aceves J.Hybrid Channel Access Scheduling in Ad Hoc Networks［C］.California:IEEE International Conference on Network Protocols，2002:451 － 485.