龐利平，殷峰

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

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

龐利平1，殷峰2

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

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

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

0 引言

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

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

下圖是Searchlight時(shí)序分配圖。

圖1 Searchlight時(shí)隙分布（t=8）

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

1 SOND算法

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

圖2 SOND時(shí)隙分布圖（t=8）

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

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

SOND算法發(fā)現(xiàn)原理：設(shè)x，y為傳感器網(wǎng)絡(luò)中的兩個(gè)鄰居節(jié)點(diǎn)，P（x，y）是x的A時(shí)隙到的A時(shí)隙的相對(duì)位移。當(dāng)P（x，y）小于τ時(shí)，必定有x節(jié)點(diǎn)的A時(shí)隙與y節(jié)點(diǎn)的A時(shí)隙在第一個(gè)周期內(nèi)重疊。當(dāng)P（x，y）大于等于τ并且小于t/2*τ時(shí)，必定有x的C時(shí)隙和y的A時(shí)隙在n個(gè)周期（即一個(gè)超級(jí)周期）內(nèi)的某一個(gè)時(shí)隙重疊。當(dāng)P（x，y）大于等于t/2*τ，必有y的A時(shí)隙與的C時(shí)隙在t/2周期內(nèi)的某一個(gè)時(shí)隙重疊。

2 算法比較

本文將SOND算法與Searchlight、Birthday、Disco算法在不同比較條件下進(jìn)行了仿真實(shí)驗(yàn)比較。

圖3是在靜態(tài)場(chǎng)景下的幾種算法的發(fā)現(xiàn)延遲分析比較，我們可以很直觀得出本文提出的算法SOND比其他3種算法更好地減少了鄰居節(jié)點(diǎn)間的發(fā)現(xiàn)時(shí)延，能較快地實(shí)現(xiàn)節(jié)點(diǎn)之間的鄰居發(fā)現(xiàn)。

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

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

圖4 占空比對(duì)幾種算法的ADLs影響

3 結(jié)語(yǔ)

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

2016-12-06

2017-02-10

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