陳彥如，魏亮雄，郭 兵

(四川大學計算機學院，四川 成都 610065)

目前，物聯(lián)網(wǎng)呈現(xiàn)井噴發(fā)展趨勢.無線傳感網(wǎng)作為物聯(lián)網(wǎng)的一項重要支撐技術(shù)也備受關(guān)注[1].在無線傳感網(wǎng)中，鄰居發(fā)現(xiàn)是路由和組網(wǎng)的前提，所以它是一個非常重要的步驟[2].由于傳感網(wǎng)中傳感器節(jié)點的能量(或者電量)非常有限，這些節(jié)點通常工作在低占空比模式.低占空比是指時間被劃分成時隙，只有少量的時隙節(jié)點處于蘇醒狀態(tài)，而其余時隙節(jié)點處于休眠狀態(tài).在低占空比模式下進行高效的鄰居發(fā)現(xiàn)非常困難，因為節(jié)點同時蘇醒的機會很小.一般而言，給定能量越小，發(fā)現(xiàn)延遲??；給定能量越大，發(fā)現(xiàn)延遲大[3].研究者提出了大量的鄰居發(fā)現(xiàn)算法，旨在給定能量條件下，減小鄰居發(fā)現(xiàn)延遲.研究者提出了兩兩成對的鄰居發(fā)現(xiàn)算法，該類算法只關(guān)注兩兩節(jié)點的發(fā)現(xiàn).該類算法分為概率性算法和確定性算法.在概率性算法中，節(jié)點的工作狀態(tài)不是事先確定的而是由某個概率分布確定的.確定性鄰居算法的工作計劃表是事先確定好的.

最近幾年，又有研究者提出了基于組的鄰居發(fā)現(xiàn)算法.這類算法主要利用鄰居關(guān)系的傳遞性來加速鄰居發(fā)現(xiàn)，工作于基于節(jié)點對的發(fā)現(xiàn)算法之上，所以也可以看作鄰居發(fā)現(xiàn)中間件.基于組的鄰居發(fā)現(xiàn)算法包括 Acc[4]，Group-based[5]、EQS[6]和 Wiflock[7].據(jù)我們所知，目前基于組的鄰居發(fā)現(xiàn)算法都沒有充分考慮移動傳感網(wǎng)中節(jié)點移動速度對蘇醒時隙選擇延遲和能耗的影響.在本文中，基于Group-based鄰居發(fā)現(xiàn)算法，我們提出一種高效的基于組的鄰居發(fā)現(xiàn)算法，在對額外時隙進行選擇時，該算法量化分析節(jié)點移動速度對能耗和發(fā)現(xiàn)延遲的影響，選擇在驗證時刻仍然具有較大概率是鄰居的節(jié)點進行驗證.

1 相關(guān)研究

因為在傳感網(wǎng)中，在鄰居發(fā)現(xiàn)之前進行時鐘同步比較困難，所以目前主要的鄰居發(fā)現(xiàn)算法都是異步的.基于發(fā)現(xiàn)延遲是否有界，即能否保證一定時間內(nèi)兩個利用低占空比工作的節(jié)點必定能夠?qū)崿F(xiàn)相互發(fā)現(xiàn)，現(xiàn)有的異步的兩兩成對的鄰居發(fā)現(xiàn)算法分為概率性鄰居發(fā)現(xiàn)和確定性鄰居發(fā)現(xiàn).

概率性鄰居發(fā)現(xiàn)算法主要包括Birthday[8]，PSBA[9]，Panda[10]等.對于Birthday算法，每個節(jié)點按照一定概率選擇當前時隙應該處于休眠還是蘇醒狀態(tài).PSBA利用概率性和確定性發(fā)現(xiàn)算法的優(yōu)勢，減小了概率性算法發(fā)現(xiàn)延遲的長尾.最近的一個典型概率性鄰居發(fā)現(xiàn)算法是Panda.在Panda中，每個傳感器在起初保持睡眠狀態(tài)，節(jié)點的休眠時間服從指數(shù)分布.睡眠之后，傳感器蘇醒并傾聽一段恒定時間.如果在偵聽狀態(tài)中沒有接收到數(shù)據(jù)包，則節(jié)點向其他鄰近節(jié)點廣播數(shù)據(jù)包.

最初的確定性發(fā)現(xiàn)算法基于Quorum[11].在這類算法中[11-12]，時間被劃分為m2個等長時隙.這些時隙可以看作一個二維數(shù)組，節(jié)點任意選擇該數(shù)組的一行和一列作為蘇醒時隙.Quorum算法保證在m2個時隙內(nèi)兩個節(jié)點能夠相互發(fā)現(xiàn).早期的確定性方法還包括基于素數(shù)的算法，包括Disco[13]，U-connect[14]等.為了進一步提升能效，后來的研究者提出了Searchlight[3].在Searchlight算法中，每個周期有兩個蘇醒時隙：A時隙和P時隙.A時隙固定在每個周期的第一個時隙.由于周期長度相同，兩個節(jié)點A時隙的相對位置是永遠固定的，這樣P時隙被引入用來探測另外一個節(jié)點的A時隙.后來的研究者發(fā)現(xiàn)，采用等長時隙，在兩個節(jié)點蘇醒時隙的重疊之間存在冗余，這對于提升能效造成不利影響.因此，采用不等長蘇醒時隙的確定性鄰居發(fā)現(xiàn)算法研究開始興起.這類算法包括Searchlight-Striped[3]，Non-integer[15]，Lightning[2].

近年來，隨著移動無線傳感網(wǎng)的興起，對鄰居發(fā)現(xiàn)的能效要求越來越嚴苛.于是，又有研究者提出通過鄰居關(guān)系的傳遞性來加速鄰居發(fā)現(xiàn)過程的中間件鄰居發(fā)現(xiàn)算法.因為這類算法底層仍然采用基于節(jié)點對的算法，所以也稱作鄰居發(fā)現(xiàn)中間件.中間件鄰居發(fā)現(xiàn)算法在基于節(jié)點對鄰居發(fā)現(xiàn)的基礎上重新規(guī)劃少量時隙的工作狀態(tài)，即休眠還是蘇醒，來加快鄰居發(fā)現(xiàn)進度.中間件該類鄰居發(fā)現(xiàn)算法包括Acc，Groupbased和EQS等.在ACC算法中，節(jié)點選擇增加一些額外蘇醒時隙，這些額外時隙在底層的基于節(jié)點對的發(fā)現(xiàn)算法中處于休眠狀態(tài)，但其在ACC中間件層變成了蘇醒狀態(tài).這些額外時隙的選擇依據(jù)是根據(jù)時間差異性和空間相似性.兩個節(jié)點的時間差異性取決于這兩個節(jié)點工作表的差異性.兩個節(jié)點的空間相似性取決于這兩個節(jié)點的公有鄰居數(shù)量.ACC通過使用少量的額外蘇醒時隙在一定程度上加速了鄰居發(fā)現(xiàn)進度，但問題是其中時間差異性的獲得需要很多鄰居的信息，在網(wǎng)絡中節(jié)點密度較低的情況下，ACC在選擇額外的蘇醒時隙方面顯得低效.Group-based也加入了少量的額外蘇醒時隙，通過推薦-驗證的方式加速鄰居發(fā)現(xiàn)，但其在選擇額外蘇醒時隙方面效率有進一步提升的空間.EQS利用Quorum圖論濾除不必要的蘇醒時隙，提升了鄰居發(fā)現(xiàn)能效.

在本文中，我們在Group-based的基礎上提出了一種基于組的高效鄰居發(fā)現(xiàn)算法.特別指出，我們提出的算法與其他算法是相互補充的，而不具有排它性.也就是說不同種類的鄰居發(fā)現(xiàn)中間件可以同時使用來提高鄰居發(fā)現(xiàn)的性能.比如EQS和我們提出的算法可以同時使用，分別用于移除低效蘇醒時隙和增加高效蘇醒時隙.此外，據(jù)我們所知，在鄰居發(fā)現(xiàn)中間件算法中，我們提出的算法充分考慮了節(jié)點移動速度對于選擇的蘇醒時隙能效的影響，由此我們提出了節(jié)點移動速度對鄰居關(guān)系影響的定量化分析方法.

2 算法設計

基于組的鄰居發(fā)現(xiàn)算法的核心思路是通過在各個節(jié)點之間共享已經(jīng)發(fā)現(xiàn)的鄰居關(guān)系信息來預測未來時間內(nèi)哪個時隙節(jié)點蘇醒能夠發(fā)現(xiàn)更多鄰居或者對鄰居發(fā)現(xiàn)具有最大的信息貢獻.上節(jié)已經(jīng)提到，已有的基于組的鄰居發(fā)現(xiàn)算法都只是依據(jù)已有的鄰居表和其對應的工作表信息來推測未來的鄰居關(guān)系但忽略了在移動傳感網(wǎng)中移動節(jié)點速度對鄰居關(guān)系的影響.我們在本文中提出的SFND算法核心思路是基于Group-based方法，考慮節(jié)點移動速度對額外增加的蘇醒時隙能效的影響，盡可能地選擇在驗證時刻有很大概率仍然是鄰居且在驗證時刻在蘇醒狀態(tài)的潛在節(jié)點進行驗證.因為我們提出的算法是對已有Group-based方法的改進，所以在接下來的第一小節(jié)我們首先介紹已有的Group-based方法.然后第二小節(jié)給出我們提出算法的詳細設計思路.

2.1 Group-based方法介紹

圖1表示Group-based的工作過程：灰色小圓A，B，C，D分別表示四個傳感器節(jié)點，它們相互在各自的通信范圍之內(nèi).假定A和B在先前通過某個基于節(jié)點對的發(fā)現(xiàn)算法已經(jīng)相互發(fā)現(xiàn)，節(jié)點C和D也通過基于節(jié)點對的算法實現(xiàn)相互發(fā)現(xiàn).接下來，Groupbased中間件算法按照如下的步驟進行工作：

(1)當B發(fā)現(xiàn)了一個新的鄰居C時，B和C分別將自己的所有鄰居信息推薦給對方，節(jié)點B知道了節(jié)點D的工作時間表，節(jié)點C知道了節(jié)點A的工作時間表.我們把推薦者B和C叫做推薦節(jié)點，被推薦者A、D叫做被推薦節(jié)點.因為B接收了C的推薦，所以B叫做C的接收節(jié)點.事實上B和C互為對方的推薦節(jié)點和接收節(jié)點.

(2)由于被推薦者可能不在接收節(jié)點的通信范圍之內(nèi)，因此有必要對被推薦節(jié)點進行驗證以確認是否是接收節(jié)點的鄰居.當節(jié)點B接收到推薦信息后，它將對所有的被推薦節(jié)點進行驗證.也就是說B會在D的下一個蘇醒時隙主動蘇醒，以進行鄰居發(fā)現(xiàn)，也就是相互確認.如果B收到了D的數(shù)據(jù)包，則將其加入自己的鄰居表.同理C也在A的下一個蘇醒時隙主動蘇醒進行驗證，從而發(fā)現(xiàn)了節(jié)點A.

圖1 Group-based算法發(fā)現(xiàn)過程圖Fig 1 Group-based algorithm discovery process diagram

接收節(jié)點需要對被推薦節(jié)點進行驗證，然而當被推薦節(jié)點與接收節(jié)點相距較遠時，被推薦節(jié)點有很大概率不是接收者的鄰居，此時的驗證對能效的貢獻率很低或者為負.尤其在節(jié)點密度比較大的無線傳感網(wǎng)絡中，被推薦節(jié)點個數(shù)很多，如果不對驗證進行有效選擇，將導致低效驗證過多而給接收節(jié)點乃至整個網(wǎng)絡帶來較大的能耗負擔.因此有必要對被推薦節(jié)點進行篩選，選擇具有潛在較大收益的節(jié)點進行驗證.在Group-based算法中，主要依據(jù)接收節(jié)點和被推薦節(jié)點之間已經(jīng)發(fā)現(xiàn)的公有鄰居作為選擇驗證節(jié)點的依據(jù).作者們通過推導得出，兩個節(jié)點的距離Dxy=其中α表示一個常數(shù)，Nx和Ny分別表示節(jié)點x和節(jié)點y已經(jīng)發(fā)現(xiàn)的鄰居個數(shù)，Nc表示這兩個節(jié)點的公共鄰居數(shù).

雖然Group-based算法取得了良好性能，尤其在靜態(tài)無線傳感網(wǎng)絡(靜態(tài)是指其中的節(jié)點位置保持不變)中，其對驗證節(jié)點的選擇效率較高.但在移動無線傳感網(wǎng)中，依據(jù)接收節(jié)點和被推薦節(jié)點發(fā)現(xiàn)時刻的公共鄰居數(shù)來預測驗證時刻的鄰居關(guān)系有時顯得低效，尤其考慮接收節(jié)點和被推薦節(jié)點發(fā)現(xiàn)時刻與驗證時刻相差很大時，很可能在接收節(jié)點和被推薦節(jié)點發(fā)現(xiàn)時刻具有較多公有鄰居的被驗證節(jié)點在驗證時刻已經(jīng)不是接收節(jié)點的鄰居.本文中，我們充分考慮節(jié)點移動速度對驗證選擇的影響，力圖選擇在驗證時刻有很大可能仍然是鄰居的節(jié)點進行驗證，從而提升驗證能效而進一步加快鄰居發(fā)現(xiàn)進度.

2.2 考慮速度因素的快速鄰居發(fā)現(xiàn)中間件算法

我們根據(jù)接收節(jié)點和被推薦節(jié)點相互發(fā)現(xiàn)時刻，接收節(jié)點和被推薦節(jié)點的公有鄰居個數(shù)作為評估此時這兩個節(jié)點距離的依據(jù)，就像Group-based算法一樣.此外，我們還要評估接收節(jié)點和被推薦節(jié)點相互發(fā)現(xiàn)時刻和驗證時刻，即當被推薦節(jié)點的下個蘇醒時隙時刻，這兩個時刻的間隔時間內(nèi)，移動節(jié)點速度對這兩個節(jié)點距離的影響.為簡化分析，假設所有節(jié)點移動速度都相等，值為S.設Δtxy為接收節(jié)點x和被推薦節(jié)點y的驗證時刻減去x和y相互發(fā)現(xiàn)時刻.在這段時間內(nèi)，這兩個節(jié)點距離增加量為速度s和Δtxy的函數(shù)，表示為Δl(s，Δtxy).綜合x和y發(fā)現(xiàn)時刻的距離估計以及Δtxy時間內(nèi)的距離增量估計，我們得到驗證時刻x和y的距離估計lxy=Dxy+Δl(s，Δtxy).

在實際的移動傳感網(wǎng)絡場景中，Δl(s，Δtxy)的表達式取決于節(jié)點的移動模型.往往獲取Δl(s，Δtxy)的準確表示比較困難.不過我們能夠通過測試，找到能使驗證盡可能高效的Δl(s，Δtxy)的大致估計.例如在下節(jié)的仿真評估所使用的模型中，我們將Δl(s，Δtxy)的表達式簡化得到，lxy=Dxy+β1sΔt+β2/，其中β1和β2是與節(jié)點移動模型相關(guān)的常數(shù).

對lxy設置閾值lu，當lxy小于等于 lu時，該驗證時隙被選擇蘇醒，否則認為這是低效或者無效的驗證而讓其休眠.在選擇閾值lu時，可以依據(jù)給定的額外能量預算，以及因為每個節(jié)點剩余能量的不同而對不同的節(jié)點選擇不同的閾值.比如，當節(jié)點剩余能量較少時，可選擇一個較小的閾值.

在移動無線傳感網(wǎng)中，Group-based算法考慮了接收節(jié)點和被推薦節(jié)在相互發(fā)現(xiàn)時它們是鄰居的概率，但在驗證時刻很可能它們已經(jīng)不再是鄰居.SFND算法直接考慮在驗證時刻，這兩個節(jié)點是鄰居的概率，并選擇有較大概率是鄰居(即距離較短的鄰居)的驗證，有效地過濾了低效驗證，從而提升了驗證的能效.

3 仿真評估

我們通過仿真評估提出的SFND算法，并和其他算法進行比較.底層的基于節(jié)點對的算法采用Searchlight，其余要對比的中間件算法包括 ACC和Group-based.為了公平比較，將所有算法總的能量預算即總占空比設定為2%.我們首先對比節(jié)點移動速度對 Searchlight， ACC+Searchlight， Group-based+Searchlight，SFND+Searchlight的平均發(fā)現(xiàn)延遲的影響.然后，對比網(wǎng)絡中節(jié)點密度對這些算法平均發(fā)現(xiàn)延遲的影響.實驗環(huán)境描述如下：網(wǎng)絡場地為邊長為500米的矩形區(qū)域，這個區(qū)域被劃分為2500個等大小的網(wǎng)格.節(jié)點只能部署于網(wǎng)格頂點并沿著網(wǎng)格邊移動.當移動到網(wǎng)格頂點，節(jié)點的移動方向可向上下左右隨機改變.

圖2 速度對平均發(fā)現(xiàn)延遲的影響Fig 2 The effect of velocity on the average discovery delay

圖2顯示了節(jié)點移動速度對平均發(fā)現(xiàn)延遲的影響.我們看到，所有算法包括Searchlight，其平均發(fā)現(xiàn)延遲都隨著速度的增加而減少.這是因為隨著速度增加，節(jié)點成為鄰居的時間減小，那些發(fā)現(xiàn)延遲較大的鄰居發(fā)現(xiàn)沒能成功進行.另外，我們看到，隨著速度的變化，我們的算法SFND的發(fā)現(xiàn)延遲總小于其他算法.比如在節(jié)點速度為4m/s時，相比 Group-based，SFND算法降低發(fā)現(xiàn)延遲高達18.9%.

圖3 節(jié)點密度對平均發(fā)現(xiàn)延遲的影響Fig 3 Influence of node density on average discovery delay

圖3顯示了節(jié)點密度對平均發(fā)現(xiàn)延遲的影響.我們看到Searchlight算法的平均發(fā)現(xiàn)延遲幾乎不受節(jié)點密度的影響，而其他算法的平均發(fā)現(xiàn)延遲隨著節(jié)點密度增大而減少.這是因為節(jié)點密度越大，節(jié)點之間能夠共享的鄰居信息越多，對于中間件算法鄰居發(fā)現(xiàn)進度加速越明顯.而對于基于節(jié)點對的Searchlight算法，因為不考慮間接鄰居信息，所以其平均發(fā)現(xiàn)延遲不受節(jié)點密度的影響.另外，我們看到隨著節(jié)點密度變化，SFND的發(fā)現(xiàn)延遲總是小于其他算法.

4 結(jié)論

在移動無線傳感網(wǎng)中，由于節(jié)點之間的鄰居關(guān)系快速變化，要求低占空比下的鄰居發(fā)現(xiàn)必須更加高效.不同于已有算法，本文中我們提出了一種基于節(jié)點移動速度來選擇有效驗證的高效鄰居發(fā)現(xiàn)中間件算法SFND.我們量化分析了節(jié)點移動速度和時間對兩個節(jié)點期望距離的影響，并將其作為高效驗證選擇的依據(jù).最后我們通過仿真評估驗證了SFND的有效性.缺點是節(jié)點移動速度和時間對兩個節(jié)點期望距離評估仍然不夠精確，以后我們將針對不同的移動模型分別考慮更加精確的速度-時間-距離評估模型，以進一步提升鄰居發(fā)現(xiàn)中間件算法的能效.