無線傳感器網絡低延遲鄰居發現算法研究

劉元梓

（四川大學計算機學院，成都 610065)

無線傳感器網絡低延遲鄰居發現算法研究

劉元梓

（四川大學計算機學院，成都 610065)

鄰居發現問題是無線傳感器網絡（WSNs）通信協議的重要組成部分之一。由于不需要同步通訊，異步的鄰居發現算法近年得到較多的關注。針對異步網絡環境，設計一種新穎的鄰居發現算法，并驗證在不同節點密度、節點占空比、節點通信不規則度以及節點移動方式等情況下，該算法的發現延遲和能耗。結果表明，該算法在降低發現延遲方面取得良好效果，提升網絡的性能，對實時性要求較高的無線傳感器網絡有很高的實用價值。

鄰居發現；動態占空比；發現延遲

0 引言

鄰居發現同時間同步、節點定位等一樣，是無線傳感器網絡的基礎支撐技術。鄰居發現對于節點識別周邊環境的鄰居節點以及構建路由并協同工作，具有重要意義。無線傳感器網絡經過多年的研究發展，鄰居發現已不再是一項新的技術，具有一定量的可參考文獻資料。一直處于喚醒狀態的節點發現的研究主要集中在定向天線，而基于占空比的節點發現算法則是多種多樣的。當傳感器節點處于移動的環境中，這種環境對發現時間有很高要求，即要以盡可能快地速度發現節點。

比較著名的傳感器節點發現算法有Stochasticbased Protocols[1-2]，Quorum-based Protocols[3]，Disco[4]，UConnect[5]，多信道[6]以及基于沖突的節點發現等。這些算法主要集中在怎樣通過某一類型的調度算法來保證一對節點可以同時喚醒，經過驗證這些算法是有效的，可以保證節點在有限的時間界限內發現其鄰居節點。Stochastic-based Protocols中，節點以隨機循環的方式監聽、傳輸或者休眠，在耗能和發現延遲上進行權衡折中。Quorum-based Protocols闡明在有界限的時間上保證成對節點的喚醒時間重疊的局限性。Disco介紹了一個基于中國剩余定理（Chinese Reminder Theorem）的鄰居發現算法，算法中節點選擇一對素數作為周期，素數的選擇要滿足其占空比要求。U-Connect提出了針對對稱或者非對稱的占空比設置的統一鄰居發現算法。值得注意的是U-Connect對于對稱異步的發現方案是1.5倍近似算法，而Quorum和Disco則是2倍近似算法。

在傳統的成對發現算法中，每個節點周期性地處于喚醒狀態和休眠狀態，而且傳感器網絡中鄰居節點必須是處于彼此的通信范圍之內的，只有這樣節點之間才可以正常通信，進而實現數據的傳輸。當兩個節點分別根據自己的工作安排進行調度并同時處于喚醒狀態時，兩個節點此發現對方，并將對方加入到自己的鄰居表中，至此完成了一個鄰居節點的發現。組發現算法，同成對發現算法一樣，節點是在喚醒狀態和休眠狀態之間周期性地切換。傳感器網絡節點處于蘇醒狀態時，根據自己的工作安排調度進行廣播；當傳感器網絡中的兩個節點同時處于喚醒狀態并在彼此的通信范圍內時，一個節點發現了另外一個節點，這兩個節點便形成一個組。當第三個節點與第一個節點同時喚醒時，第三個節點發現第一個節點并將其加入到自己的鄰居表中，同時第一個節點將其發現的鄰居節點信息廣播給第三個節點；當第三個節點和第二個節點的喚醒時間同步時，由于第三個節點通過第一個節點已經獲知第二個節點的信息，此時只需判斷這個節點是否是其鄰居節點，如果是的話，將其加入到自己的鄰居表中，形成一個更大的組。以此類推，這個由鄰居節點組成的組不斷地擴大，從而完成鄰居節點的發現。

本文的主要貢獻如下所示：

（1）根據影響無線傳感器網絡能量消耗和延遲的因素，分析現有的鄰居發現算法的優缺點，研究性能更優、延遲更低的鄰居發現算法；

（2）分析已有鄰居發現算法中節點的調度機制，采取更先進的發現調度策略。鄰居發現策略采用群組發現的思想，所有節點采用周期性的睡眠調度機制，發現節點將已發現的鄰居節點納入其所在的群組，通過已有鄰居節點的鄰居信息來獲取潛在的鄰居節點的信息，采用Demand-wakeup機制主動蘇醒以更快的速度發現更多的鄰居節點；

（3）研究群組發現過程中節點間信息的推薦機制，鄰居節點如何有效地向發現節點推薦潛在的鄰居信息來保證發現效率的同時降低能耗以及發現節點如何高效選擇鄰居節點的信息避免過多接收無用的信息而造成不必要的能耗；

（4）利用傳感器網絡中節點移動模型預測節點通信范圍內潛在的鄰居節點，根據潛在的鄰居節點的數量動態調整節點的占空比，以此更快更多地發現鄰居節點；

本文剩余部分的內容主要是算法的設計與實現。

1 Disco算法分析

路由器、交換機等硬件設備，那么無線傳感器網絡中的節點如何通信呢？毫無疑問，所有的工作都是由傳感器節點自身來完成。

許多應用設備，包括那些布置在廣闊野外區域的具有多樣性配置的設備，例如在野外部署的低廉傳感器，主要用于環境監測、野生動物監測、戰場環境監視以及采集野外環境信息等。如何精確保證這些傳感器節點的全局時間同步是個具有挑戰性的問題，為了解決這個問題，通常采用基于分布式協調占空比模式來決定各自的工作調度，即由節點自己的工作調度決定何時工作、何時發送數據、何時接收數據以及何時進入低功耗的休眠狀態。

為了安排節點的工作調度，我們將傳感器設備（如節點S）的工作時間劃分為連續的固定長度的時隙（Time Slots），依據預先安裝的協議，節點S激活無線電設備并將其狀態在某一段時隙內切換至發現模式，然后節點S向網絡中的并且處于其通信范圍內的其他節點廣播消息，以此來通知它的存在性，同時節點S也偵聽其他節點的信息。如果在某一時隙，節點S和其他的節點同時處于工作狀態，即工作調度出現重疊部分，如果節點在彼此的通信范圍內，它們就能夠互相發現并成為彼此的鄰居節點。

定義1：我們通常將上述在時間方面的調度機制成為時隙參考機制（Time Slots Reference Mechanism）。

時隙參考機制的示意圖如圖1所示。

圖1 時隙參考機制示意圖

無線傳感器網絡中所有節點在網絡中地位是同等的，任何一個節點既是發送節點也是接收節點，將自己采集和接收的數據信息傳送給離接收者更近的節點以及向網絡中的其他節點廣播從而將其存在性通知給其他節點；同時，接收來自于其他節點發送的數據信息。無線傳感器網絡沒有固定的用于發送和接收信息的基礎設施，不具有手持設備（如手機等）固定的用于轉接信號的信號接收塔和發送塔，也不具有Internet的專用

在圖1中，我們將節點的工作周期劃分為蘇醒狀態（Active State）和休眠狀態（Dormant State），圖中，我們用黑色區域時隙代表蘇醒狀態，白色區域時隙代表休眠狀態，如果有兩個或多個節點同時處于蘇醒狀態（或者說工作調度出現重疊），而且彼此之間可以互相通信，它們之間就可以完成鄰居發現，成為彼此的鄰居節點。

Dutta和Culler在文獻[4]中提出異步鄰居發現算法Disco，該算法基于中國剩余定理相關理論，算法中兩個節點選擇一對素數，使得這兩個素數的倒數分別與節點期望的占空比相等，采取素數的好處是可以保證兩個節點在工作過程中會出現相同的喚醒時隙，使得節點間可以相互通信并完成鄰居發現。在Disco算法中，所有的節點采取周期性偵聽-睡眠機制，周期性地在蘇醒狀態（Active State）和休眠狀態（Dormant State）或者睡眠狀態（Sleep State）間切換。鄰居發現的過程如下：網絡中一個節點處于另一個節點的通信范圍內，并且在某一時刻這兩個節點同時處于蘇醒狀態，如果一個節點的無線電廣播信息時，由于另一個節點處于蘇醒狀態可以接收到廣播信息，此時，兩個節點交換數據信息，完成鄰居發現，成為彼此的鄰居節點。Disco算法的原理如圖2所示。將其加入自己的鄰居信息表Neighbor Table（a），同時，節點c發現其鄰居節點a并將自己的鄰居信息表Neighbor Table（c）。至此，節點a完成了對節點b和節點c的鄰居發現過程，節點a將節點b和c的信息添加到鄰居表中。當t=64時，節點a、b和c才同時處于蘇醒狀態。

2 設計原理

圖2 傳感器網絡鄰居發現算法-Disco算法原理圖

如圖2所示，以傳感器網絡中的a，b，c三個節點為例，其中節點a為發現節點DN，節點a，b和c都按照各自的工作安排進行調度。在t=1時，節點b和節點c同時處于喚醒狀態（Active State），節點b和c發現彼此，并將其添加到彼此的鄰居表Neighbor Table（b）和Neighbor Table（c）中；在t=4時，節點b和節點a同時處于喚醒狀態，它們發現彼此，并將對方加入到自己的鄰居表Neighbor Table（b）和Neighbor Table（a）中。此時節點a和節點b互為鄰居節點，節點b和節點c互為鄰居節點，但是節點a和節點c并沒有發彼此，因而無法判斷是否是鄰居節點。當時間t=29時，節點a和節點c同時處于蘇醒狀態，接節點a現其鄰居節點c并

低延遲鄰居發現算法Group的原理：

（1）對于傳感器網絡中一個單獨的節點，節點根據自己的工作調度安排，周期性地處于喚醒狀態和睡眠狀態。此時，節點將自己的工作安排調度進行廣播；

（2）當傳感器網絡中的兩個節點同時處于喚醒狀態時，一個節點發現了另外一個節點時，這兩個節點便形成一個虛擬組。當第三個節點與第一個節點同時喚醒時，第三個節點發現第一個節點并將其加入到自己的鄰居表中；

（3）第一個節點在第三個節點喚醒時隙主動蘇醒，將其發現的鄰居節點信息（第二個節點）廣播給第三個節點；

（4）第三個節點在第二個節點喚醒時隙時主動喚醒，由于第三個節點通過第一個節點已經獲知第二個節點的信息，此時只需判斷這個節點是否是其鄰居節點，如果是的話，將其加入到自己的鄰居表中，形成一個更大的虛擬組。以此類推，這個由鄰居節點組成的組不斷地擴大，從而完成鄰居節點的發現。

3 度量標準

同步鄰居發現算法在部署節點時要求所有的節點擁有相同的初始化時間，但是這樣的要求在實際的應用環境中很難實現，或者基本上不可能，所以這里我們主要針對異步鄰居發現算法提出鄰居發現算法的度量標準，這個標準對于同步鄰居發現算法還是具有一定的參考意義的。

能量的高效性以及較低的發現延遲是評價鄰居發現算法的兩個主要參數，通過這個參數的分析比較基本上可以確定某個鄰居發現算法是否具有實用性。在實際情況中，既要提高能量的有效性，又要擁有較低的發現延遲，這是不可能的，魚和熊掌不可兼得。在本文進行研究之前，已經有部分人將研究方向投向鄰居發現，分析發現這些研究成果都有一個共同點：以犧牲節點的能量來換取較低的發現延遲或者以較高的發現延遲來節省節點的能量，所以鄰居發現的一個主要目標就是在節點的能耗和發現延遲兩個方面尋求一個最佳的平衡點，一味地追求高能效、低延遲是與現實情況相悖的。

為了更好地評價一個鄰居發現算法的好壞，是否具有一定的實際意義，我們將采用能耗-延遲（Power-Latency，PL）的乘積M來作為鄰居發現算法的評價標準。

對于周期為T的鄰居發現調度滿足如下關系：

則一個調度周期內的平均能耗P表示為：

在這個周期為T的鄰居發現調度中，假設所有成對節點（節點賦予所有可能的相對相位偏移量）中最差的發現延遲為L，則我們將能耗-延遲的乘積M定義為：

采用時隙調度機制有以下兩個優點：第一，時隙調度機制是可以實際實現的；第二，只要節點的時鐘漂移總和小于單個時隙的長度，時隙參考機制就可以克服時鐘漂移問題。

在延遲需求為L的鄰居發現中，時隙長度要比L單位時間內最差情況下的相對時間漂移大。同時，一個時間槽持續時間的設定與很多實現因素相關，比如，無線電在切換接收狀態和發送狀態的周轉周期、將振蕩器從低功耗狀態加速需要的時間以及清空信道需要的時間等。由于實際鄰居發現算法的槽性質，發現調度是離散性質的，所以這里我們用表示離散狀態下的發現調度，滿足延遲需求L的周期為T的節點m在時隙t時的發現調度可表示為，同時一個周期內的平均能耗P為：

則能耗-延遲乘積M為：

4 結語

本文在研究已有鄰居發現算法的基礎上，對各算法之間的區別與聯系作深入分析，并開始著手鄰居發現問題方面的研究，主要在以下幾個方面進行深入研究：

（1）分析并挖掘延遲更低的自適應鄰居發現調度算法。在無線傳感器網絡中，兩個節點實現鄰居發現的一個基本條件就是節點必須處在彼此的通信范圍內，只有這樣節點之間才能夠正常通信，并完成數據傳輸。目前，在學術界的經常討論和研究的熱點算法基本上都是經典的成對發現（如Disco、U-Connect），即傳感器網絡中的兩個節點分別根據自己的工作安排調度蘇醒，如果兩個節點的蘇醒時隙重疊（即同時蘇醒），而且在彼此的通信范圍內，則這兩個節點就可以互相發現互為鄰居，同時添加到各自的鄰居表中。仔細分析不難發現，這一類的發現策略沒有充分利用節點的時間相關性這一特性。綜合考慮節點間的時間相關性，采用主動蘇醒的Demand-Wakeup機制，根據已有鄰居節點獲取潛在鄰居節點的信息，通過主動蘇醒來發現潛在的鄰居節點，并在此基礎上研究鄰居節點間信息的推薦機制，提出基于公共鄰居率的鄰居推薦機制，通過該推薦機制，使得CNR-Group算法在延遲和能耗方面都有所降低，提升了網絡的性能，延長了網絡的生命周期。

（2）利用實際的節點移動模型來預測潛在的鄰居節點，并通過潛在的鄰居節點數動態調整節點的占空比，以此提高鄰居節點的發現效率，降低發現延遲。根據所交換的節點調度信息主動蘇醒可以實現鄰居節點的發現。

（3）根據節點的移動模型可以估計節點的位置，節點可以預估其通信范圍內潛在的鄰居節點個數，如果鄰居節點的個數超過所設定的閾值，節點動態調節占空比并延長蘇醒時間，來實現更多節點的鄰居發現。

[1]Mc Glynn M J，Borbash S A.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks.Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing[C].ACM，2001.

[2]Borbash S A，Ephremides A，Mc Glynn M J.An Asynchronous Neighbor Discovery Algorithm for Wireless Sensor Networks[J].Ad Hoc Networks，2007，5（7）:998-1016.

[3]Lai S，Ravindran B，Cho H.Heterogenous Quorum-Based Wake-up Scheduling in Wireless Sensor Networks[J].Computers，IEEE Transactions on，2010，59（11）:1562-1575.

[4]Dutta P，Culler D.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications.Proceedings of the 6th ACM conference on Embedded Network Sensor Systems[C].ACM，2008.

[5]Kandhalu A，Lakshmanan K，Rajkumar R R.U-connect:a Low-Latency Energy-Efficient Asynchronous Neighbor Discovery Protocol. Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks[C].ACM，2010.

[6]Karowski N，Viana A C，Wolisz A.Optimized Asynchronous Multi-Channel Neighbor Discovery.INFOCOM，2011 Proceedings IEEE [C].IEEE，2011.

[7]Niven I，Zuckerman H S，Montgomery H L.An Introduction to the Theory of Numbers[M].John Wiley&Sons，2008.

[8]Chen L，Gu Y，Guo S，et al.Group-Based Discovery in Low-Duty-Cycle Mobile Sensor Networks.Sensor，Mesh and Ad Hoc Communications and Networks SECON），2012 9th Annual IEEE Communications Society Conference on[C].IEEE，2012.

Research on a Low Latency Neighbor Discovery Algorithm for Wireless Sensor Network

LIU Yuan-zi

（College of Computer Science，Sichuan University，Chengdu 610065）

Neighbors discovery problem is wireless sensor networks(WSNs)one of the important part of communication protocol.As it needs not synchronization communication,asynchronous neighbor discovery algorithm got more attention in recent years.For asynchronous network environment,designs a novel neighbor discovery algorithm,and validates its discovery latency and energy consumption in different case such as node density,node duty cycle,node communications irregular degree and node move mode.The results show that the algorithm has achieved good results in reducing discovery delay,and improves the network performance,and has a high practical value in higher re-al-time requirement wireless sensor network.

Neighbor Discovery;Dynamic Duty Cycle;Discovery Latency

1007-1423（2016）08-0016-05

10.3969/j.issn.1007-1423.2016.08.003

劉元梓（1984-），男，重慶云陽人，碩士研究生，研究方向為網絡信息安全

2016-03-01

2016-03-10