孫偉杰，袁平，殷鋒

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

0 引言

在無線傳感器網(wǎng)絡中，鄰居發(fā)現(xiàn)扮演了重要角色，它是路由和網(wǎng)絡組建的先決條件，為了加快鄰居發(fā)現(xiàn)，許多鄰居發(fā)現(xiàn)算法相繼被提出，現(xiàn)存的鄰居發(fā)現(xiàn)算法主要分為兩類，基于點的成對發(fā)現(xiàn)算法和基于組的鄰居發(fā)現(xiàn)算法，其中成對發(fā)現(xiàn)算法又分為概率性鄰居發(fā)現(xiàn)算法和確定性鄰居發(fā)現(xiàn)算法。

概率性鄰居發(fā)現(xiàn)算法節(jié)點以一定概率在各時隙隨機蘇醒如Birthday[1]等，通常具有較低的平均發(fā)現(xiàn)延遲，但無法保證一個確定的發(fā)現(xiàn)延遲上限。確定性鄰居發(fā)現(xiàn)算法節(jié)點按照預先設定的時刻表進行蘇醒，如Disco[2]，Search?Light[3]，U-connect[4]等能夠保正一個確定的發(fā)現(xiàn)延遲上限，但平均發(fā)現(xiàn)延遲略高于概率性鄰居發(fā)現(xiàn)算法。

近幾年，一些基于組的鄰居發(fā)現(xiàn)被提出，該類算法將一些相鄰的節(jié)點看成一個組，利用組內(nèi)節(jié)點的鄰居信息加快其他節(jié)點的發(fā)現(xiàn)，WiFlock[5]提到了所有的一跳相鄰節(jié)點（即一個組內(nèi)）的蘇醒時隙相錯以使分布平均化，使組外節(jié)點更快發(fā)現(xiàn)組內(nèi)節(jié)點，而Group-based-Discovery[6]提出了在不改變底層發(fā)現(xiàn)協(xié)議的基礎上，通過組間節(jié)點的鄰居推薦加快新了節(jié)點的鄰居發(fā)現(xiàn)。

本文中我們在基于組的鄰居發(fā)現(xiàn)基礎之上提出了一種新的鄰居發(fā)現(xiàn)算法VGC，通過對組內(nèi)的各個節(jié)點進行協(xié)同形成一個大的虛擬節(jié)點，該虛擬節(jié)點工作時隙滿足底層成對發(fā)現(xiàn)算法的分布特征，同時這該虛擬節(jié)點的占空比遠大于組內(nèi)節(jié)點的任何節(jié)點，因而它能更快地發(fā)現(xiàn)鄰居，提高了整個組的能量使用效率。

1 算法設計

在我們的工作中，我們設定了工作場景如下：許多沒有相互發(fā)現(xiàn)的節(jié)點一致地分布在一定區(qū)域內(nèi)。傳感器網(wǎng)絡的輻射范圍是以半徑為r的圓，并且所有的節(jié)點都在一跳的通信范圍內(nèi)。首先根據(jù)成對發(fā)現(xiàn)算法把已經(jīng)相互發(fā)現(xiàn)的節(jié)點看作一個組，如果一個節(jié)點屬于一個組它將不能再屬于其他組。在這個場景中一個單獨的節(jié)點和一個組以及一個組和另一個組都能相互發(fā)現(xiàn)。最終所有節(jié)點都完成了發(fā)現(xiàn)過程。

為了充分利用所有組內(nèi)節(jié)點的活動時隙進行組發(fā)現(xiàn)，我們把所有在時空上分布在網(wǎng)絡的組內(nèi)節(jié)點作為一個虛擬節(jié)點，換句話說，這個虛擬節(jié)點代表了所有組內(nèi)節(jié)點進行鄰居發(fā)現(xiàn)。通常虛擬節(jié)點的活動時隙是不規(guī)則的并且在全局時間內(nèi)有重疊，另外，虛擬節(jié)點依賴于成對發(fā)現(xiàn)算法他們的發(fā)現(xiàn)鄰居，所以這虛擬節(jié)點需要對組內(nèi)節(jié)點的時課表進行協(xié)同調(diào)整以確保虛擬節(jié)點的時隙分布特征和成對發(fā)現(xiàn)算法的相一致，最終所有的組內(nèi)的節(jié)點的活躍時隙被虛擬節(jié)點所協(xié)同，所有的組內(nèi)節(jié)點根據(jù)該協(xié)同的時刻表工作。這樣我們充分利用了占空比大于所有組內(nèi)節(jié)點的虛擬節(jié)點使用成對發(fā)現(xiàn)算法來進行虛擬節(jié)點和他的鄰居之間的快速發(fā)現(xiàn)。

由于每個節(jié)點攜帶的能量是有限的，我們把協(xié)同計算分配給每一個新發(fā)現(xiàn)的節(jié)點以確保每一個節(jié)點的生命周期，當一個節(jié)點新加入一個組時，將會調(diào)整整個組內(nèi)節(jié)點的時序，組內(nèi)大部分其他節(jié)點此時一般是休眠狀態(tài)，對他們的協(xié)同要求需要掛起等待直至被要求協(xié)同的節(jié)點蘇醒，才會將協(xié)同要求傳送給他們，而并不會馬上傳達到。本文從協(xié)同要求延時出發(fā)，采用如下方法：

（1）當新發(fā)現(xiàn)一個鄰居節(jié)點時，更新組內(nèi)的節(jié)點數(shù)目及組的總占空比，并依照節(jié)點占空比計算一個周期內(nèi)每個節(jié)點應該蘇醒的時隙數(shù)目；

（2）依照節(jié)點的下一次的原有蘇醒時隙，按照從早到晚排序，以確定新的時序中各組內(nèi)節(jié)點的蘇醒次序，越早蘇醒的節(jié)點在新的時序中排位越靠前；

（3）將產(chǎn)生的協(xié)同信息通知組內(nèi)其余各個節(jié)點；

（4）組內(nèi)節(jié)點收到協(xié)同信息后調(diào)整自己的工作時刻表。

最終所有節(jié)點完成了協(xié)同過程，形成一個虛擬節(jié)點，該虛擬節(jié)點沒有任何的重疊時隙，并且其時序分布特征和底層成對發(fā)現(xiàn)算法相一致。

2 算法分析

虛擬的節(jié)點的時隙分布特征和底層成對發(fā)現(xiàn)算法相關，在這里我們使用SearchLight進行分析，為了證明虛擬節(jié)點的優(yōu)勢，我們使用DCg代表所有組內(nèi)節(jié)點的占空比總和，在SearchLight我們知道在t時間內(nèi)每個節(jié)點有兩個活躍時隙，因此：

其中n是組內(nèi)節(jié)點的數(shù)量，DCi代表節(jié)點i的占空比，ti代表節(jié)點i的周期，對于虛擬節(jié)點，我們假定只要任一時刻至少有一個組內(nèi)節(jié)點處于蘇醒狀態(tài)，我們就認為該虛擬節(jié)點該時刻處于蘇醒狀態(tài)，我們使用DCfg代表其占空比，因而：

其中 Ln表示 t1，t2，…，tn的最小公倍數(shù)，即 Ln=lcm（t1，t2，t3，…），Nc表示所有組內(nèi)節(jié)點在 Ln內(nèi)時間內(nèi)的重疊時隙個數(shù)。

直觀地，DCg將隨著新加入到組的節(jié)點而動態(tài)的增加，DCfg也相應的隨之增加，然而DCg和DCfg之間難免有一些理論上的偏差，這是因為組內(nèi)節(jié)點之間存在重疊時隙，即Nc的存在，導致虛擬節(jié)點減少了發(fā)現(xiàn)未知鄰居的概率。

圖1

如圖1所示，三個節(jié)點A，B，C他們占空比分別為DCa=2/16,DCb=DCc=2/32，在初始階段這些節(jié)點通過Searchlight進行相互發(fā)現(xiàn)，根據(jù)等式（1）和等式（2）我們知道DCg=8/32和DCfg=5/32，DCg和DCfg之間的理論偏差是3/32，并且該組的時隙分布并不滿足Search Light的時隙分布特征，不能直接將其作為一個虛擬節(jié)點進行鄰居發(fā)現(xiàn)。

在對組內(nèi)節(jié)點的工作周期進行協(xié)同后，其時隙分布特征滿足Search Light的時隙分布特征，并且Nc=0，DCfg能夠達到最大值DCg，像圖2所示的那樣我們能夠看到DCfg從5/32增加到了8/32，并且沒有增加任何的活躍時隙，通過和沒有進行組內(nèi)節(jié)點協(xié)同的相比較，虛擬節(jié)點發(fā)現(xiàn)其鄰居的概率增加了60%。從等式1我們能 夠 看 出DCg＞＞DCi，所 以 易 知DCfg＞＞DCi。 結(jié) 合Search Light，我們能夠充分利用虛擬節(jié)點的占空更大的優(yōu)勢減少平均發(fā)現(xiàn)延遲和提高組的能量使用效率。

圖2

3 算法比較

為了更好地評估VGC的性能，我們在仿真實驗中實現(xiàn)了它和Search Light,Group-based Discovery和Wi?Flock（底層都基于Search Light）。我們每個仿真做了10000次測試，然后去他們的平均值進行分析：

圖3

這第一個仿真是在靜態(tài)場景中，仿真參數(shù)如下：（1）整個網(wǎng)絡區(qū)域范圍是 100×100m；（2）每個節(jié)點的輻射范圍是 140m；（3）節(jié)點數(shù)量是 20；（4）一個時隙的長度是10ms；（5）平均占空比是1/20。圖3表現(xiàn)了Search?Light,Group-based Discovery,WiFlock和VGC的表現(xiàn)。很容易看到：對所有的發(fā)現(xiàn)策略，發(fā)現(xiàn)百分比都隨這時隙數(shù)量的增加而增加。當時隙數(shù)固定的時候，VGC能夠比其他的算法發(fā)現(xiàn)更多的鄰居。尤其是在500個時隙的時候，VGC發(fā)現(xiàn)了98%的鄰居。我們注意到：在剛開始的時候，VGC和Group-based Discovery的發(fā)現(xiàn)率幾乎相同，一段時間后，VGC的發(fā)現(xiàn)率比Group-base Dis?covery增長地更快。這是因為隨著時間的增長，虛擬節(jié)點的大?。▽儆诋斍疤摂M節(jié)點的節(jié)點數(shù)量）增長地更大，所以VGC能夠比其他算法更快地發(fā)現(xiàn)鄰居。

圖4

圖5

在第二個仿真中，我們使用隨機路徑模型[6]作為移動多跳網(wǎng)絡中的移動模型。仿真參數(shù)如下：（1）整個網(wǎng)絡區(qū)域為500×500m；（2）每個節(jié)點的輻射半徑是40m；（3）節(jié)點數(shù)量是 400；（4）一個時隙的長度是 10ms；（5）平均占空比是1/20。圖4描繪了平均發(fā)現(xiàn)時延和節(jié)點移動速度的關系，速度從1m/s到40m/s，增量為5m/s，從圖4中我們能夠看出VGC的曲線在每種速度下都明顯好于其他算法。圖5表明了占空比變化對三種算法的平均發(fā)現(xiàn)延時的影響。很容易看出，當消耗相同能量時，VGC比其他兩種算法更快的完成發(fā)現(xiàn)過程。原因和第一個仿真相同。結(jié)合圖4和圖5我們能夠得出結(jié)論VGC能夠顯著地提高平均發(fā)現(xiàn)延遲和能量使用效率。

4 結(jié)語

本文我們?yōu)榈驼伎毡鹊臒o線傳感器網(wǎng)絡提出了一個新的鄰居發(fā)現(xiàn)算法，叫做虛擬組協(xié)同鄰居發(fā)現(xiàn)算法。VGC的主要思想是一個組基于預測性的協(xié)同策略整合他的所有組內(nèi)節(jié)點的工作時刻表，以至于把所有組內(nèi)節(jié)點作為一個虛擬節(jié)點考慮來發(fā)現(xiàn)他的鄰居。我們在靜態(tài)和動態(tài)場景中都做了仿真。通過和WiFlock以及Group-based Discovery相比較，VGC能夠更進一步地減少平均發(fā)現(xiàn)實驗和提高能量效率。

參考文獻：

[1]M.J.McGlynn and S.A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[J].MobiHoc'01:Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking&Computing,pages 137-145,2001.

[2]P.Duttaand D.Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[J].Proceedings of the 6th International Conference on Embedded Networked Sensor Systems（SenSys'08）,71-84,2008.

[3]Bakht,M.,Kravets,R.:‘SearchLight:Asynchronous Neighbor Discovery Using Systematic Probing.ACM SIGMOBILE Mobile Computing and Communications Review,2010：31-33.

[4]Kandhalu,A.,Lakshmanan,K.,Rajkumar,R.R.:‘U-Connect:a Lowlatency Energy-Efficient Asynchronous Neighbor Discovery Protocol[J].Proceedings of the9th International Conferenceon Information Processing in Sensor Networks（IPSN'10）,2010：350-361.

[5]Purohit,A.,Priyantha,B.,Liu,J.:‘Wiflock:Collaborative Group Discovery and Maintenance in Mobile Sensor Networks.Information Processing in Sensor Networks（IPSN）,2011 10th International Conference on,2011：37-48.

[6]Chen,L.,Gu,Y.,Guo,S.,He,T.,Shu,Y.,Zhang,F.,and Chen,J.:‘Groupbased 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.IEEE,2012：542-550