基于發(fā)現(xiàn)矩陣的鄰居發(fā)現(xiàn)算法：Swift

李旭，袁平，殷鋒

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

鄰居發(fā)現(xiàn)一直是低占空比無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)核心問(wèn)題，為了解決這個(gè)問(wèn)題很多有名的算法被提了出來(lái)，例如 Searchlight、Striped-Searchlight和 Search?light-trim。在這些知名算法中，時(shí)間總是被分成連續(xù)的時(shí)隙，時(shí)隙的長(zhǎng)度固定為t。節(jié)點(diǎn)在某些時(shí)隙保持蘇醒，處在蘇醒時(shí)隙的節(jié)點(diǎn)能給鄰居節(jié)點(diǎn)發(fā)送信息也能接受鄰居節(jié)點(diǎn)發(fā)送的信息，為了節(jié)省能量節(jié)點(diǎn)其他時(shí)隙都保持睡眠。為了簡(jiǎn)化研究學(xué)者們通常假設(shè)只要2個(gè)節(jié)點(diǎn)的活動(dòng)時(shí)隙重合足夠發(fā)送和接收一個(gè)數(shù)據(jù)幀，2個(gè)相鄰節(jié)點(diǎn)之間就能相互發(fā)現(xiàn)。

以上這些算法的主要區(qū)別是，其發(fā)現(xiàn)矩陣有不同，導(dǎo)致能量效率也不同。在這些發(fā)現(xiàn)算法中蘇醒時(shí)隙被分為 2類（Anchor slots和 Probe slots）。Anchor slot和Probe slot有相同的能耗，但是他們?cè)诎l(fā)現(xiàn)矩陣中的位置不相同。DM的第一列（0th）都是Anchor slots，Probe slots的位置各不相同，因此他們的DM的大小也不相同。

Searchlight和Searchlight-trim的發(fā)現(xiàn)矩陣都是的矩陣，但是Striped-Searchlight的發(fā)現(xiàn)矩陣是的矩陣。Striped-Searchlight通過(guò)讓所有的An?chor slot和Probe slot向后溢出σ，能夠?qū)robe slots的數(shù)量和發(fā)現(xiàn)矩陣的行數(shù)減少為Searchlight的一半。Searchlight-trim將Anchor slot和Probe slot的長(zhǎng)度變?yōu)榱嗽瓉?lái)的Striped-Searchlight和Searchlight-trim都有效地提高能效，但是都沒(méi)有盡可能的讓Probe slot的蘇醒長(zhǎng)度變得更短，也沒(méi)有嘗試在同一行中部署多個(gè)Probe slots，來(lái)提高鄰居發(fā)現(xiàn)的能量利用率。

為了實(shí)現(xiàn)確定性的雙向鄰居發(fā)現(xiàn)，本文提出了DM。在 DM中我們用 Special slot代替 Probe slot。Special slot由處在idle狀態(tài)的IP部分和處在蘇醒狀態(tài)的AP共同構(gòu)成。通過(guò)縮短Special slot中蘇醒時(shí)長(zhǎng)，可以節(jié)約能量。除此之外DM的大小可以按照應(yīng)用的需求動(dòng)態(tài)的配置。基于DM我們提出了Swift算法，Swift能夠有效地提高能量地利用率。

1 算法實(shí)現(xiàn)

在DM中，時(shí)間被劃分成連續(xù)的等長(zhǎng)時(shí)隙，長(zhǎng)度用t表示。T個(gè)連續(xù)的時(shí)隙構(gòu)成一個(gè)周期。n個(gè)相鄰的周期構(gòu)成一個(gè)超級(jí)周期。在DM和超級(jí)周期有相同大小，但是DM中的活動(dòng)時(shí)隙分為2中Anchor slots和Special slots。Special slot由處在idle狀態(tài)的IP部分和處在蘇醒狀態(tài)的AP部分共同構(gòu)成。節(jié)點(diǎn)在idle狀態(tài)下消耗的能量大概是蘇醒狀態(tài)下的，處在idle狀態(tài)下的節(jié)點(diǎn)能很快的從idle恢復(fù)到蘇醒狀態(tài)，因此可以將AP的長(zhǎng)度縮減到只夠發(fā)送和接受一幀數(shù)據(jù)。這樣做能夠有效地提高能量的利用率，因?yàn)镾pecial slot消耗的能量是Probe slot的，此外我們還能按需來(lái)改變DM中Special slot的個(gè)數(shù)和位置。

圖1 發(fā)現(xiàn)矩陣

2 發(fā)現(xiàn)定理

對(duì)于兩個(gè)相鄰節(jié)點(diǎn)x和y，x和y的DM大小分別是：nx*tx,ny*ty，只要tx等于ty，在 max{nx*tx,ny*ty}個(gè)時(shí)隙之內(nèi)兩個(gè)相鄰的節(jié)點(diǎn)一定能相互發(fā)現(xiàn)。

圖2 φ(x,y)定義

證明：

假設(shè)n=max{nx,ny}(nx≥1,ny≥1)，tx=ty=T，φ(x,y)表示節(jié)點(diǎn)x的Anchor slot（Ax）和節(jié)點(diǎn)y的Anchor slot（AY）之間的相位差。當(dāng)φ(x,y)≤t時(shí)，Ax和AY將會(huì)重合，并且重合的長(zhǎng)度大于等于σ，因?yàn)閠+σ-φ(x,y)≥σ。當(dāng)，y節(jié)點(diǎn)的 A時(shí)隙必然落在DMx的一列或者相鄰的兩列之間。因此在n*T個(gè)slot內(nèi)AY和APY一定會(huì)重合，重合部分的長(zhǎng)度為σ。因?yàn)樵趚節(jié)點(diǎn)的發(fā)現(xiàn)矩陣中，任意兩個(gè)APY之間的距離必然等于t-σ.因此有(t-σ)-(t-σ)=2σ，這意味著AY和APX必然重合。當(dāng)時(shí)和上面原因類似，這種情況下有APY和Ax必然重合。因此只要tx=ty，x和 y在max{nx*tx,ny*ty}個(gè)slot內(nèi)一定能相互發(fā)現(xiàn)。

圖3 圖解發(fā)現(xiàn)定理

如圖3所示，當(dāng)tx=ty=8時(shí)，nx=3和ny=2，無(wú)論φ(x,y)的值如何變化，節(jié)點(diǎn)x，y在24個(gè)slot內(nèi)一定能相互發(fā)現(xiàn)。

3 性能分析

在這個(gè)部分主要討論Swift的性能，Swift的最壞發(fā)現(xiàn)延遲是n*Tslots，因?yàn)閮蓚€(gè)相鄰的節(jié)點(diǎn)在一個(gè)超級(jí)周期內(nèi)一定能相互發(fā)現(xiàn)。在一個(gè)DM中有n個(gè)An?chor slots，APs和IPs各有個(gè)。IPs的長(zhǎng)度有2種情況t或者t-σ，當(dāng)IP跟在Anchor slot或者Special slot之后（圖1）。在這里我們只討論最壞的情況，在這種情況下只有一個(gè)長(zhǎng)度為t-σ的IPs，其他的IPs長(zhǎng)度都為 t。在 DM 中 Anchor slot，APs，IPs的總長(zhǎng)度分別是：Swift的占空比是：(t視為基本單位)。

為了計(jì)算一個(gè)給定的占空比d的最壞發(fā)現(xiàn)延遲，用?(n,t)來(lái)表示Swift的最壞發(fā)現(xiàn)延遲，則有：

當(dāng)a=2(1+σ)，b=0.1+σ，c=-(0.3σ+0.1)，通過(guò)計(jì)算可以得到?(n,t)的最小值是：當(dāng)n和t有可能不是整數(shù)，此時(shí)應(yīng)該向下取整。

圖4 Swift算法理論性能分析

圖4顯示當(dāng)占空比從1%變到5%，不同算法的理論最壞發(fā)送延遲，從圖中可以看出當(dāng)占空比為1%時(shí)，和Searchlight相比Swift降低了48%的最壞發(fā)現(xiàn)延遲。

4 仿真

在這部分我們將通過(guò)和現(xiàn)在最好的鄰居發(fā)現(xiàn)算法Striped-Searchlight和Searchlight-Trim做對(duì)比來(lái)評(píng)估Swift的性能。仿真的場(chǎng)景如下：一個(gè)500×500（m）的矩形，被平均分成10000個(gè)小塊，200個(gè)傳感器節(jié)點(diǎn)被隨機(jī)的部署在該區(qū)域。當(dāng)節(jié)點(diǎn)到達(dá)每個(gè)小區(qū)域的頂點(diǎn)時(shí)，能夠改變方向（向左，向右，向下，向上）。我們研究靜態(tài)條件下最壞發(fā)現(xiàn)延遲的累積分布函數(shù)（CDF）。此外還在動(dòng)態(tài)場(chǎng)景（節(jié)點(diǎn)移動(dòng)）下評(píng)估了DC和speed對(duì)平均發(fā)現(xiàn)延遲（ADL）的影響。在仿真環(huán)境下節(jié)點(diǎn)的通信半徑為50m~100m,t=10ms。

在占空比為2%的靜態(tài)環(huán)境下，和Search-Trim相比Swift能減少48.08%的最壞發(fā)現(xiàn)延遲，兩者之間的相關(guān)關(guān)系如圖5。圖6表明當(dāng)占空比從1%變化到5%，不同算法的平均發(fā)現(xiàn)延遲。3個(gè)算法的平均發(fā)現(xiàn)延遲隨著占空比的增加都在增加。當(dāng)占空比為2%時(shí)，Swift比Search-Trim減少了39.6%的平均發(fā)現(xiàn)延遲。圖7顯示了當(dāng)節(jié)點(diǎn)移動(dòng)速度從2m/s變化到10m/s時(shí)，速度變化對(duì)平均發(fā)現(xiàn)延遲的影響。對(duì)所有的節(jié)點(diǎn)來(lái)說(shuō)隨著速度的增加，平均發(fā)現(xiàn)延遲增加了。這是因?yàn)殡S著速度的增加節(jié)點(diǎn)之間保持鄰居關(guān)系的時(shí)間變短了。

所有的對(duì)比都顯示了在相同條件下Swift的性能比現(xiàn)有的算法好。

圖5 最壞發(fā)現(xiàn)延遲和占空比之間的關(guān)系

5 結(jié)語(yǔ)

在這篇文章中，基于DM提出了一個(gè)確定性的雙向鄰居發(fā)現(xiàn)算法Swift。理論分析當(dāng)Swift和Search?light占空比相同的時(shí)候，Swift相比Searchlight降低了48%的最壞發(fā)現(xiàn)延遲。理論分析和實(shí)驗(yàn)仿真都證明了Swift的優(yōu)越性。

圖6 占空比和平均發(fā)現(xiàn)延遲之間的關(guān)系

圖7 速度對(duì)平均發(fā)現(xiàn)延遲的影響

參考文獻(xiàn)：

[1]Bakht,Mehedi,M.Trower,R.Kravets.Searchlight:Helping Mobile Devices Find Their Neighbors[J].ACM Sigops Operating Systems Review，2011，45.3：71-76.

[2]Michael J.McGlynn and Steven A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[R].In MobiHoc 01:Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing,New York,NY,USA,ACM，2001：137-145.

[3]Zhou,H.Y.,Luo,D.Y.,Gao,Y.,Zuo,D.C.Modeling of Node Energy Consumption for Wireless Sensor Networks[J].Wireless Sensor Network,2011：3（1）：18-23.

[4]Bakht,M.,Trower,M.,&Kravets,R.H.Searchlight:Won't You be My Neighbor[R].Proceedings of the 18th Annual International Conference on Mobile Computing And Networking，2012：185-196.

[6]Chen,S.,Russell,A.,Jin,R.,Qin,Y.,Wang,B.,&Vasudevan,S.Asynchronous Neighbor Discovery on Duty-cycled Mobile Devices:Integer and Non-Integer Schedules[J].MobiHoc,2015：47-56.

[7]Arvind Kandhalu,Karthik Lakshmanan,Ragunathan Rajkumar.U-connect:a Low-latency Energy-efficient Asynchronous Neighbor Discovery Protocol[R].In IPSN 10:International Conference on Information Processing in Sensor Networks，2010：350-361.

[8]Prabal Dutta and David Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[R].In SenSys 08:Proceedings of the 6th ACM conference on Embedded network sensor systems,New York,NY,USA,ACM，2008：71-84.

[9]ZHANG Lan,DING Xuan,WAN Zhi-guo,GU Ming,LI Xiang-yang.Wiface:a Secure Geosocial Networking System Usingwifi-based Multihop Manet[J].In MCS 10:Proceedings of the 1stACMWorkshop on Mobile Cloud Computing&Services,ACM，2010：1-8.

[10]Wei,L.,Zhou,B.,Ma,X.,Chen,D.,Zhang,J.,Peng,J.,...&Chen,L.Lightning:A High-efficient Neighbor Discovery Protocol for Low Duty Cycle Wsns[J].IEEE Communications Letters,2016，20（5）：966-969.