一種基于時隙優化的鄰居發現算法研究

龐利平，殷峰

（1.四川大學計算機學院，成都 610065；2.西南民族大學校園網絡管理中心，成都 610064）

一種基于時隙優化的鄰居發現算法研究

龐利平1，殷峰2

（1.四川大學計算機學院，成都 610065；2.西南民族大學校園網絡管理中心，成都 610064）

作為無線傳感器網絡組網及路由的先決條件，鄰居發現問題受到越來越人們的關注。為了提高無線傳感器網絡中節點的發現概率，減少發現延時，提出一種基于時隙優化的鄰居發現算法（SOND）。SOND算法基于Searchlight[1]原理，對Searchlight中時隙進行優化，從而提高鄰居節點之間的發現效率和減少鄰居的發現延遲。仿真實驗表明SOND算法具有良好的發現性能。

無線傳感器網絡（WSNs）；鄰居發現算法；時隙優化

0 引言

為了解決低占空比無線傳感器網絡中的鄰居發現問題，相關領域的研究人員對鄰居發現算法做了大量的研究。目前鄰居發現算法可分為兩大類：確定性鄰居發現算法和概率性生日協議[2]鄰居發現算法。確定性鄰居發現算法又可分為基于中國剩余定理的算法，最著名的是Disco[3]算法。確定性鄰居發現算法可以提供最差情況下的發現時延，保證傳感器節點在該時延內一定可以發現其鄰居。相比于確定性鄰居發現算法，概率性鄰居發現算法具有較好的平均發現時延，但是其拖尾較長。本文主要在確定性鄰居算法典型算法Searchlight基礎之上做出研究。

Searchlight算法核心思想：時間被分成多個連續的等長時隙（長度大小為τ），t個時隙構成一個周期。每個周期有兩個蘇醒時隙，其余時隙都為休眠時隙。兩個蘇醒時隙分別是A（Anchor）時隙和探測P（Probe）時隙。A時隙固定在每個周期的第0個時隙。每個周期P時隙的位置由以下公式決定（其中Pi表示第i個周期所處在本周期的第幾個時隙，每個周期所有時隙從0到t-1編號，Pi=1）：

下圖是Searchlight時序分配圖。

圖1 Searchlight時隙分布（t=8）

Searchlight發現原理：把t/2個周期看作一個t/2*t的矩陣（如圖1所示），各行的P時隙投影到最后一行后，最后一行從1到t/2的所有時隙都是P時隙投影，從而保證一個節點的A時隙與另外一個節點A時隙的重疊，或者一個節點的A時隙與另外一個節點P時隙的重疊，實現鄰居發現。但如何保證P的個數與矩陣行數之間的關系來達到能量最優以及P時隙蘇醒時隙的大小是Searchlight尚未研究的。針對這些問題，本文在Searchlight的基礎上對蘇醒時隙進行了優化改進,以及探討了周期數與占空比之間的最優關系。

1 SOND算法

本文提出了SOND算法，相比于Searchlight，SOND算法對A時隙進行了改變，A時隙向后溢出δ長度，其中δ是節點發送信息的最小時間單位，在一個δ時間長度內，節點只能發送一個Beacon信息，δ大小跟傳感器節點硬件環境相關。同時對探測時隙P時隙進行了優化，并將其改為C（Compound）時隙（如圖2中所示），它由IP（Inoperative Part）和BP（Beacon Part）兩部分構成。IP部分時節點處于idle狀態（在idle狀態，RF模塊不能發送和接收數據，但電路沒有完全關閉，此時的節點可以快速地轉換到active狀態）。BP時隙的長度只足夠發一個數據包（Beaconing Packet），其大小用δ表示。由于BP的長度δ只能保證單向發現，但單向發現后，雙向發現容易獲得。為了確保在最壞發現延遲內至少有一次重疊時間大于等于δ的重疊,C時隙向后“溢出”δ。SOND時隙分布圖（t=8）如圖2所示。

圖2 SOND時隙分布圖（t=8）

相比于Searchlight算法，SOND的第二個改進是允許在一個周期內增加多個C時隙。我們用n（圖2中n= t/2）個周期構建一個大小為t*n時隙的矩陣，由于這個矩陣所定義的蘇醒模式每隔t*n時隙就會重復，所以t*n時隙被叫作超級周期（T）。為確保每行的C時隙投影到最后一行后，最后一行從1到t/2的所有時隙都是C時隙即可保證在n個周期內一個節點的A時隙與另外一個節點A時隙的重疊，或者一個節點的A時隙與另外一個節點C時隙的重疊來實現鄰居發現。因此可以增加一行中C時隙個數，從而減小矩陣行數n。但在一行內增加了C時隙就增加了節點的占空比，這樣會導致能耗的增加。那么n取值多少時能量是最優的呢？已知節點在IP狀態時消耗的能量遠小于節點在BP狀態下的能量消耗，為了便于計算，假定一個時隙的長度τ=1，IP狀態下的能量消耗是BP狀態下能量消耗的β倍，β值大小和硬件環境相關。根據圖2中的統計數據，若超級周期中蘇醒時隙工作的總時長用tw表示，可以得到如下公式。

對上述公式進行變換求導計算，根據現有鄰居發現算法的硬件環境，取得α=0.1，β=0.1，可求得到n的最優值與節點占空比之間的關系。

SOND算法發現原理：設x，y為傳感器網絡中的兩個鄰居節點，P（x，y）是x的A時隙到的A時隙的相對位移。當P（x，y）小于τ時，必定有x節點的A時隙與y節點的A時隙在第一個周期內重疊。當P（x，y）大于等于τ并且小于t/2*τ時，必定有x的C時隙和y的A時隙在n個周期（即一個超級周期）內的某一個時隙重疊。當P（x，y）大于等于t/2*τ，必有y的A時隙與的C時隙在t/2周期內的某一個時隙重疊。

2 算法比較

本文將SOND算法與Searchlight、Birthday、Disco算法在不同比較條件下進行了仿真實驗比較。

圖3是在靜態場景下的幾種算法的發現延遲分析比較，我們可以很直觀得出本文提出的算法SOND比其他3種算法更好地減少了鄰居節點間的發現時延，能較快地實現節點之間的鄰居發現。

圖3 發現延遲累積分布圖（CDF）

圖4是在動態場景下占空比DC（Duty Cycle）從1%變化到5%時幾種算法的ADLs（Average Discovery Latency）平均發現延時的比較，我們可以看出幾種算法的平均發現延時都隨占空比的增大而降低，但在同一DC下，我們發現SOND算法的平均發現延時比其他3種算法的ADLs低。

圖4 占空比對幾種算法的ADLs影響

3 結語

隨著硬件技術的提高，基于無線傳感器網絡的應用已經廣泛影響到包括工業、醫療、農業、軍事及戶外探索在內的多個領域。而近些年社交網絡、社區游戲的興起，更是吸引了許多業內人士對該領域的探索。無線傳感器網絡中的鄰居發現算法是無線傳感器網絡的重要研究方向和熱點，本文在經典的鄰居發現算法Searchlight之上，基于Searchlight算法中存在的不足，提出了一種基于時隙優化來提高無線傳感器網絡中的鄰居發現效率和減少鄰居節點間的發現延時，并通過仿真實驗表明，本文在Searchlight基礎之上提高了鄰居節點間的發現效率并且減少了節點之間的發現延時。同時，相比其他幾種林發發現算法具有更好的性能。

[1]M.Bakht，R.Kravets.SearchLight:Asynchronous Neighbor Discovery Using Systematic Probing.ACM SIGMOBILE Mobile Computing and Communications Review，vol.14，no.4，pp.31-33，2011.

[2]M.J.McGlynn，S.A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks.in Proceedings of MobiHoc'01.ACM，pp.137-145.2001.

[3]P.Dutta，and D.Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications.In Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems，pp.71-84.Nov.2008.

A Neighbor Discovery Algorithm Based on Time Slot Optimization

PANG Li-ping1，YIN Feng2
（1.College of Computer Science，Sichuan University，Chengdu 610065；2.Campus Network Management Center，Southwest University of Nationalities，Chengdu 610064）

As a prerequisite for networking and routing in wireless sensor networks,neighbor discovery is concerned by more and more people.In order to improve the discovery probability of nodes in wireless sensor networks and reduce the delay of discovery,proposes a neighbor discovery algorithm based on time slot optimization(SOND).SOND algorithm based on the principle of Searchlight,the Searchlight in the slot is optimized,so as to improve the efficiency of the discovery between neighbor nodes and reduce the delay of the neighbor discovery. Simulation results show that the SOND algorithm has good performance.

Wireless Sensor Networks(WSNs);Neighbor Discovery Algorithm;Slot Optimization

1007-1423（2017）05-0011-03

10.3969/j.issn.1007-1423.2017.05.003

龐利平（1992-），女，四川廣安人，碩士研究生，研究方向無線傳感與網絡技術

2016-12-06

2017-02-10

殷鋒（1972-），男，貴州榕江人，副主任，教授，研究方向為數據挖掘、中間件、分布式計算、軟件測試