VGC:虛擬組協同鄰居發現算法

孫偉杰，袁平，殷鋒

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

0 引言

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

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

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

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

1 算法設計

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

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

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

（1）當新發現一個鄰居節點時，更新組內的節點數目及組的總占空比，并依照節點占空比計算一個周期內每個節點應該蘇醒的時隙數目；

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

（3）將產生的協同信息通知組內其余各個節點；

（4）組內節點收到協同信息后調整自己的工作時刻表。

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

2 算法分析

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

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

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

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

圖1

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

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

圖2

3 算法比較

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

圖3

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

圖4

圖5

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

4 結語

本文我們為低占空比的無線傳感器網絡提出了一個新的鄰居發現算法，叫做虛擬組協同鄰居發現算法。VGC的主要思想是一個組基于預測性的協同策略整合他的所有組內節點的工作時刻表，以至于把所有組內節點作為一個虛擬節點考慮來發現他的鄰居。我們在靜態和動態場景中都做了仿真。通過和WiFlock以及Group-based Discovery相比較，VGC能夠更進一步地減少平均發現實驗和提高能量效率。

參考文獻：

[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