龐利平，殷峰

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

一種基于時隙優(yōu)化的鄰居發(fā)現(xiàn)算法研究

龐利平1，殷峰2

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

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

無線傳感器網(wǎng)絡（WSNs）；鄰居發(fā)現(xiàn)算法；時隙優(yōu)化

0 引言

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

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

下圖是Searchlight時序分配圖。

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

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

1 SOND算法

本文提出了SOND算法，相比于Searchlight，SOND算法對A時隙進行了改變，A時隙向后溢出δ長度，其中δ是節(jié)點發(fā)送信息的最小時間單位，在一個δ時間長度內，節(jié)點只能發(fā)送一個Beacon信息，δ大小跟傳感器節(jié)點硬件環(huán)境相關。同時對探測時隙P時隙進行了優(yōu)化，并將其改為C（Compound）時隙（如圖2中所示），它由IP（Inoperative Part）和BP（Beacon Part）兩部分構成。IP部分時節(jié)點處于idle狀態(tài)（在idle狀態(tài)，RF模塊不能發(fā)送和接收數(shù)據(jù)，但電路沒有完全關閉，此時的節(jié)點可以快速地轉換到active狀態(tài)）。BP時隙的長度只足夠發(fā)一個數(shù)據(jù)包（Beaconing Packet），其大小用δ表示。由于BP的長度δ只能保證單向發(fā)現(xiàn)，但單向發(fā)現(xiàn)后，雙向發(fā)現(xiàn)容易獲得。為了確保在最壞發(fā)現(xiàn)延遲內至少有一次重疊時間大于等于δ的重疊,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個周期內一個節(jié)點的A時隙與另外一個節(jié)點A時隙的重疊，或者一個節(jié)點的A時隙與另外一個節(jié)點C時隙的重疊來實現(xiàn)鄰居發(fā)現(xiàn)。因此可以增加一行中C時隙個數(shù)，從而減小矩陣行數(shù)n。但在一行內增加了C時隙就增加了節(jié)點的占空比，這樣會導致能耗的增加。那么n取值多少時能量是最優(yōu)的呢？已知節(jié)點在IP狀態(tài)時消耗的能量遠小于節(jié)點在BP狀態(tài)下的能量消耗，為了便于計算，假定一個時隙的長度τ=1，IP狀態(tài)下的能量消耗是BP狀態(tài)下能量消耗的β倍，β值大小和硬件環(huán)境相關。根據(jù)圖2中的統(tǒng)計數(shù)據(jù)，若超級周期中蘇醒時隙工作的總時長用tw表示，可以得到如下公式。

對上述公式進行變換求導計算，根據(jù)現(xiàn)有鄰居發(fā)現(xiàn)算法的硬件環(huán)境，取得α=0.1，β=0.1，可求得到n的最優(yōu)值與節(jié)點占空比之間的關系。

SOND算法發(fā)現(xiàn)原理：設x，y為傳感器網(wǎng)絡中的兩個鄰居節(jié)點，P（x，y）是x的A時隙到的A時隙的相對位移。當P（x，y）小于τ時，必定有x節(jié)點的A時隙與y節(jié)點的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是在靜態(tài)場景下的幾種算法的發(fā)現(xiàn)延遲分析比較，我們可以很直觀得出本文提出的算法SOND比其他3種算法更好地減少了鄰居節(jié)點間的發(fā)現(xiàn)時延，能較快地實現(xiàn)節(jié)點之間的鄰居發(fā)現(xiàn)。

圖3 發(fā)現(xiàn)延遲累積分布圖（CDF）

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

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

3 結語

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

[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-），女，四川廣安人，碩士研究生，研究方向無線傳感與網(wǎng)絡技術

2016-12-06

2017-02-10

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