機(jī)會網(wǎng)絡(luò)中的鄰居發(fā)現(xiàn)性能優(yōu)化方法分析*

代宇茜，姜勝明

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

機(jī)會網(wǎng)絡(luò)中的鄰居發(fā)現(xiàn)性能優(yōu)化方法分析*

代宇茜，姜勝明

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

由于機(jī)會網(wǎng)絡(luò)的節(jié)點移動性、能量有限性和網(wǎng)絡(luò)稀疏性等，數(shù)據(jù)傳輸困難，選擇一種可靠高效的鄰居發(fā)現(xiàn)方法非常重要。現(xiàn)有的算法未能達(dá)到預(yù)期的性能優(yōu)化效果，如主動探測方法是通過節(jié)點廣播探測包來發(fā)現(xiàn)鄰居節(jié)點，會消耗大量能量；被動偵聽方法則是通過不斷地偵聽信道解析數(shù)據(jù)幀以得到鄰居節(jié)點的信息，卻無法準(zhǔn)確偵聽到所有鄰居。文中分析了一種結(jié)合主動探測和被動偵聽的鄰居發(fā)現(xiàn)方案，并與現(xiàn)有方法作比較，通過仿真驗證其對于鄰居發(fā)現(xiàn)性能的優(yōu)化效果。實驗結(jié)果表明，此方法雖未能在丟包率、吞吐量和端到端時延等性能上體現(xiàn)出優(yōu)勢，但鄰居發(fā)現(xiàn)數(shù)目提高約20%，并且提高了鄰居探測過程中的能量有效性，能量最高節(jié)約了60%。

鄰居發(fā)現(xiàn)；機(jī)會網(wǎng)絡(luò)；主動探測；被動偵聽

0 引言

機(jī)會網(wǎng)絡(luò)是一種新興的技術(shù)，概念來源于移動自組網(wǎng)，具有廣泛的應(yīng)用價值。在機(jī)會網(wǎng)絡(luò)中[1]，由于設(shè)備自身能量有限，節(jié)點移動性較高，網(wǎng)絡(luò)鏈路的建立是間歇性的，數(shù)據(jù)的傳輸與轉(zhuǎn)發(fā)存在一定難度。而鄰居發(fā)現(xiàn)是實現(xiàn)其“存儲-攜帶-轉(zhuǎn)發(fā)”的基礎(chǔ)，只有準(zhǔn)確地發(fā)現(xiàn)鄰居，才能得到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)繼而動態(tài)地調(diào)節(jié)發(fā)送功率達(dá)到能量效益最優(yōu)，才能根據(jù)鄰居節(jié)點的信息來發(fā)現(xiàn)路由確定路由算法，才能通過鄰居節(jié)點信息以建立最小生成樹的形式達(dá)到更高效的廣播。

同時，由于機(jī)會網(wǎng)絡(luò)里的數(shù)據(jù)傳輸實質(zhì)是依靠對鄰居節(jié)點的精準(zhǔn)發(fā)現(xiàn)，如若未能夠準(zhǔn)確發(fā)現(xiàn)其鄰居，會使節(jié)點持續(xù)等待轉(zhuǎn)發(fā)機(jī)會，從而極大增加數(shù)據(jù)延時，還會使數(shù)據(jù)傳遞不成功，同時也極度浪費存儲器資源和節(jié)點電量。因此，對鄰居探測方法的研究顯得更為重要。

1 主動探測與被動偵聽

現(xiàn)有的鄰居探測方法[2]多種多樣，根據(jù)鄰居節(jié)點在發(fā)現(xiàn)過程中所處的狀態(tài)分為主動探測與被動偵聽。主動探測是指節(jié)點在其自設(shè)需要的前提下去主動地廣播探測包，從而搜尋鄰居的消息。這種方法一是可以將自身暴露在其他節(jié)點的通信范圍內(nèi)，從而使自己能夠被列入鄰居節(jié)點的列表中，二是可以得到處在自身通信范圍內(nèi)的節(jié)點的應(yīng)答，來得到鄰居節(jié)點的狀況。而被動探測[3]是相對于主動探測而言的。它是指節(jié)點不主動發(fā)送消息尋求周圍鄰居的信息，而是被動地靜默監(jiān)聽網(wǎng)絡(luò)中的鄰居消息，從而得到周圍鄰居的分布情況、運動趨勢、是否可通信等情況。在靈活性和可操作性方面，主動探測有顯著的優(yōu)越性，卻也存在著不可忽略的缺點，其數(shù)據(jù)包開銷較大，占據(jù)了大量的網(wǎng)絡(luò)資源。在能量有限的設(shè)備上無法實現(xiàn)一直進(jìn)行主動探測的方法。而被動偵聽雖然能量消耗較少，節(jié)點間的干擾也少，但沒有主動探測的靈活性等優(yōu)點，同時也因許多無法解析的數(shù)據(jù)包而無法得到準(zhǔn)確的鄰居信息。

文獻(xiàn)[4]提出了一種基于主動探測與被動偵聽相結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法，卻未在其對于鄰居發(fā)現(xiàn)性能優(yōu)化效果方面進(jìn)行驗證，不能夠準(zhǔn)確衡量其與現(xiàn)有最大功率發(fā)現(xiàn)方法之間的差異。本文為研究鄰居發(fā)現(xiàn)算法對于網(wǎng)絡(luò)性能的優(yōu)化，將基于主動探測與被動偵聽相結(jié)合的方法與現(xiàn)有方法進(jìn)行仿真實驗，對比不同發(fā)送功率對鄰居節(jié)點發(fā)現(xiàn)數(shù)目、能量消耗、丟包率、端到端時延和吞吐量的影響，在仿真平臺上設(shè)置不同場景參數(shù)來對比并分析其性能。

2 主動探測與被動偵聽相結(jié)合的鄰居發(fā)現(xiàn)方法

2.1方法設(shè)計背景

在該方法中，為實現(xiàn)通過對功率控制而進(jìn)行鄰居探測的方法，依據(jù)偵聽到的MAC層數(shù)據(jù)幀是否能夠正確解析，將鄰居節(jié)點分為清晰鄰居節(jié)點和模糊鄰居節(jié)點[5]。清晰鄰居節(jié)點是傳統(tǒng)鄰居節(jié)點分類方式中所屬的鄰居節(jié)點，是可以通過對數(shù)據(jù)幀正確解析而得出其物理地址的鄰居節(jié)點，一般由MAC層對數(shù)據(jù)偵聽得到，因此直接選擇節(jié)點最大發(fā)送功率，相較之傳統(tǒng)方法，既不浪費能量又減少了發(fā)現(xiàn)節(jié)點所用時間。而模糊鄰居節(jié)點不能正確解析出物理地址，通過對其信息的偵聽，只能得到自己存在的通信范圍，卻不能知道鄰居的具體信息，因此要從當(dāng)前功率漸次增加，直到達(dá)到最大發(fā)送功率，去發(fā)現(xiàn)鄰居，從而實現(xiàn)節(jié)約能量的期望。

2.2方法具體步驟

(1)任意選一個節(jié)點X，在基于MAC層的被動偵聽鄰居發(fā)現(xiàn)方法以及節(jié)點分類方法的前提下，偵聽周圍鄰居節(jié)點的活動，并解析偵聽到的MAC層的數(shù)據(jù)幀，根據(jù)接收到的數(shù)據(jù)幀能否正確解析出發(fā)送節(jié)點的物理地址，將能解析出物理地址的節(jié)點列在清晰鄰居列表內(nèi)，反之，將不能解析出物理地址的節(jié)點列在模糊鄰居列表中。

(2)在基于物理層功率控制的主動探測鄰居發(fā)現(xiàn)方法的基礎(chǔ)上，節(jié)點X利用上述模糊鄰居節(jié)點信息，若模糊列表為空即沒有模糊節(jié)點存在，則節(jié)點N直接選擇最大發(fā)送功率發(fā)送探測包；若模糊列舉列表不為空即至少存在一個模糊鄰居，則節(jié)點X從當(dāng)前發(fā)送功率開始，逐級遞增，直到解析出清晰的物理地址，或直到達(dá)到最大發(fā)送功率。

(3)節(jié)點X利用上述發(fā)送的探測包中的信息，當(dāng)前發(fā)送功率和最小可接收功率分別記為PXT和PMXR。被探測的節(jié)點Y，被動偵聽到了節(jié)點X發(fā)送的探測包，此時收到的探測包功率為PYR，則探測包傳輸過程中損耗的功率PL為：

PL=PXT-PYR

被探測的節(jié)點Y回復(fù)消息的功率PY為：

PY=PMXR+PL

(4)節(jié)點X收到被探測的節(jié)點Y回復(fù)的消息后，記錄此回復(fù)包中的功率信息，即節(jié)點Y的最小可接收功率PMYR,當(dāng)下次再探測節(jié)點Y時直接使用值為PMYR+PL的發(fā)送功率。

2.3協(xié)議選擇及場景設(shè)計簡介

機(jī)會網(wǎng)絡(luò)協(xié)議種類較多，本文選取AODV(Ad hoc On—Demand Distance Vector Routing)協(xié)議， AODV結(jié)合了在DSR協(xié)議中按需路由機(jī)制以及DSDV協(xié)議中周期路由機(jī)制，因路由表項使用目的序列號而有效避免了路由環(huán)路，通過其節(jié)點的不斷移動和節(jié)點數(shù)量的適當(dāng)變化，模擬機(jī)會網(wǎng)絡(luò)低連通性的鏈路和頻繁變化的拓?fù)浣Y(jié)構(gòu)。節(jié)點自身的探測包攜帶著功率信息，以實現(xiàn)最優(yōu)化發(fā)送功率調(diào)整方法。

3 仿真實驗與結(jié)果分析

3.1仿真實驗相關(guān)參數(shù)

本文中的仿真實驗全部在仿真平臺EXata上進(jìn)行，該平臺與其他網(wǎng)絡(luò)仿真平臺相比，允許用戶更加快速也更加真實地評估網(wǎng)絡(luò)性能，利用軟件虛擬網(wǎng)絡(luò)數(shù)字化呈現(xiàn)整個網(wǎng)絡(luò)、各種虛擬的協(xié)議層、天線以及其中的網(wǎng)絡(luò)設(shè)備。本文將通過對發(fā)送功率的調(diào)節(jié)、節(jié)點密度的設(shè)置和節(jié)點移動速度的改變，來測試基于主動探測與被動偵聽相結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法和現(xiàn)有鄰居發(fā)現(xiàn)方法在不同場景的發(fā)現(xiàn)鄰居數(shù)量、消耗的能量等性能表現(xiàn)。

實驗場景：考察基于主動探測與被動偵聽結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法和現(xiàn)有鄰居發(fā)現(xiàn)方法在不同的發(fā)送功率時，對各網(wǎng)絡(luò)性能的影響。平面仿真場景如圖1所示。

基本場景參數(shù)設(shè)置如表1所示。

圖1 無線機(jī)會網(wǎng)絡(luò)平面仿真場景

參數(shù)數(shù)值場景面積/m25000×5000仿真時間/s3600節(jié)點移動模型RandomWaypoint節(jié)點能量模型Generic路由協(xié)議AODVMAC層協(xié)議802.11傳輸層協(xié)議UDP網(wǎng)絡(luò)層協(xié)議IPv4應(yīng)用數(shù)據(jù)CBR物理層模型802.11b數(shù)據(jù)傳輸帶寬/(Mb/s)11節(jié)點數(shù)/個20節(jié)點發(fā)送功率/dBm20～50節(jié)點移動速度/(m/s)0～30

3.2仿真實驗結(jié)果與分析

為了比較鄰居算法的性能，本文的仿真中主要選用鄰居節(jié)點發(fā)現(xiàn)數(shù)目、能量消耗、丟包率、端到端時延和吞吐量這幾個參數(shù)來衡量算法性能。其中，鄰居節(jié)點發(fā)現(xiàn)數(shù)目是指在鄰居發(fā)現(xiàn)過程中能夠發(fā)現(xiàn)的一跳通信范圍內(nèi)所有的鄰居節(jié)點數(shù)目，本文中發(fā)現(xiàn)的鄰居節(jié)點包括清晰鄰居節(jié)點和模糊鄰居節(jié)點。能量消耗表示在鄰居節(jié)點發(fā)現(xiàn)的過程中由于節(jié)點發(fā)送功率所消耗的能量，節(jié)點的接收階段相較之而言略為微小故先不計。丟包率是指在網(wǎng)絡(luò)傳輸過程中丟失的數(shù)據(jù)包的數(shù)目與實際發(fā)送的數(shù)據(jù)包的數(shù)目之間的比值，這里丟失的數(shù)據(jù)包主要是由找不到路由和節(jié)點間信號干擾導(dǎo)致的。端到端時延Tend由4部分組成：

Tend=(Tt+Tc+Ts+Tq)×M其中包括發(fā)送時延、處理時延、傳播時延和排隊時延，經(jīng)過的跳數(shù)值M在此處取1。吞吐量表示在單位時間內(nèi)通過某個網(wǎng)絡(luò)的數(shù)據(jù)量，可以用來反應(yīng)網(wǎng)絡(luò)中實際的數(shù)據(jù)傳輸能力。

實驗： 對比不同發(fā)送功率對鄰居節(jié)點發(fā)現(xiàn)數(shù)目、能量消耗、丟包率、端到端時延和吞吐量的影響。

如圖2所示，隨著節(jié)點的發(fā)送功率逐漸增加，節(jié)點的探測范圍逐漸擴(kuò)大，節(jié)點的鄰居探測能量也增強(qiáng)。而主動探測與被動偵聽結(jié)合的鄰居發(fā)現(xiàn)算法，是一種基于物理層功率控制的主動探測與媒體接入控制層被動偵聽跨層結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法，通過跨層的方法對發(fā)送功率進(jìn)行控制，用逐級遞增的方式來逐個探測鄰居節(jié)點，類似的跨層探測或傳輸方法在文獻(xiàn)[6]中也出現(xiàn)過。這增加了對模糊鄰居節(jié)點的探測，所以在鄰居節(jié)點發(fā)現(xiàn)的數(shù)目上比被動偵聽發(fā)現(xiàn)方法提高了平均20%左右。

圖2 節(jié)點發(fā)送功率與平均鄰居發(fā)現(xiàn)數(shù)目的關(guān)系

如圖3所示，網(wǎng)絡(luò)能量的消耗會隨著節(jié)點發(fā)送功率的增大而加劇，而在無線機(jī)會網(wǎng)絡(luò)中數(shù)據(jù)傳輸是消耗能量的主要原因。由圖3，節(jié)點發(fā)送功率在35 dBm以下時，能量消耗得較少，是因為發(fā)送功率小數(shù)據(jù)傳輸?shù)靡采伲叶荚谝惶秶鷥?nèi)進(jìn)行，兩種方法相比之下差異不明顯。當(dāng)發(fā)送功率在40 dBm及以上時，網(wǎng)絡(luò)中數(shù)據(jù)進(jìn)行多跳傳輸，能量消耗便增加了。此時主被動結(jié)合方法的能量消耗相較之主動探測方法有明顯的減少，尤其在發(fā)送功率為50 dBm時，能量節(jié)約了大概60%。

圖3 節(jié)點發(fā)送功率與平均能量消耗的關(guān)系

如圖4所示，隨著節(jié)點發(fā)送功率的增加，丟包率總體呈現(xiàn)劍俠趨勢。是因為節(jié)點的傳輸范圍隨之變大，網(wǎng)絡(luò)的連通性隨之增加，網(wǎng)絡(luò)中傳輸時因找不到路由而丟失的數(shù)據(jù)包減少。在節(jié)點功率達(dá)到45 dBm時，由于主動探測法的節(jié)點發(fā)送功率過大，節(jié)點之間出現(xiàn)了信號干擾，導(dǎo)致了丟包率又有所上升；而主被動結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法中節(jié)點間信號干擾不明顯，所以丟包率并沒有明顯變高。

圖4 節(jié)點發(fā)送功率與丟包率的關(guān)系

如圖5所示，在發(fā)送功率逐漸增加的過程中，端到端時延呈不規(guī)則變化，可以看出的是在發(fā)送功率為40 dBm之前，數(shù)據(jù)傳輸在一跳范圍內(nèi)進(jìn)行，數(shù)據(jù)傳輸時延較小，主被動結(jié)合方法能顯現(xiàn)出一絲優(yōu)勢；在40 dBm后進(jìn)行多跳傳輸，時延增大，則主動探測法較優(yōu)。總體來說兩個方法相比較，并沒有表現(xiàn)出明顯的優(yōu)劣之分。

圖5 節(jié)點發(fā)送功率與端到端時延的關(guān)系

如圖6所示，隨著發(fā)送功率的增加，網(wǎng)絡(luò)的平均吞吐量是增加的。當(dāng)發(fā)送功率小于45 dBm時，過小的發(fā)送功率導(dǎo)致數(shù)據(jù)無法傳輸，主被動結(jié)合法的吞吐量不如主動探測法。而當(dāng)發(fā)送功率大于45 dBm時，網(wǎng)絡(luò)中節(jié)點之間信號干擾增大，數(shù)據(jù)包之間沖突增多，致使吞吐量變小，又由于主被動結(jié)合法采用遞增的發(fā)送功率，所以受到干擾不明顯。但兩種方法相比之下，也未能顯現(xiàn)出新方法對此性能的優(yōu)化。

圖6 節(jié)點發(fā)送功率與吞吐量的關(guān)系

4 結(jié)論

通過仿真實驗，模擬出基于主動探測與被動偵聽結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法，通過主動式對功率的控制，遞增地調(diào)節(jié)發(fā)送功率，同時鄰居節(jié)點收到探測包也是用相同的功率回復(fù)的方式保證了數(shù)據(jù)的傳輸，同時很大程度上減少了節(jié)點的發(fā)送功率，比現(xiàn)有鄰居探測方法發(fā)現(xiàn)的鄰居數(shù)目更多，平均能量消耗更少，但卻沒有在丟包率、端到端時延和吞吐量上表現(xiàn)出優(yōu)化效果，還有待改進(jìn)提升。

在本文實驗中搭建無線機(jī)會網(wǎng)絡(luò)場景的基礎(chǔ)上選擇與機(jī)會網(wǎng)絡(luò)協(xié)議相似的AODV協(xié)議，其仿真結(jié)果可以作為參考。同時，將典型的無線機(jī)會網(wǎng)絡(luò)協(xié)議編寫到EXata中可作為一個改進(jìn)的方案。

[1] 熊永平,孫利民,牛建偉,等．機(jī)會網(wǎng)絡(luò)[J].計算機(jī)應(yīng)用,2010,30(3):723-728.

[2] 林爽．無線機(jī)會網(wǎng)絡(luò)中鄰居節(jié)點的擴(kuò)展搜尋[D].廣州：華南理工大學(xué),2015.

[3] 吳世東,姜勝明,楊方,等.一種基于主動探測與被動偵聽相結(jié)合的鄰居節(jié)點發(fā)現(xiàn)方法:中國,CN105979563A[P].2016-09-28.

[4] Yang Dongmin, SHIN J, KIM J, et al. OPEED: optimal energy-efficient neighbor discovery scheme in opportunistic networks[J].Journal of Communications and Networks,2015,17(1): 34-39.

[5] 李艷芳. 無線機(jī)會網(wǎng)絡(luò)中鄰居節(jié)點的被動式探測[D].廣州：華南理工大學(xué),2014.

[6] MOTA V F S, CUNHA F D, MACEDO D F, et al. Protocols, mobility models and tools in opportunistic networks: a survey[J]. Computer Communications,2014,48(SI):5-19.

[7] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine,2006,44(11):134-141.

Analysis of neighbor discovery performance optimization in opportunistic networks

Dai Yuxi, Jiang Shengming

(College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Due to node mobility, sparse network and limited energy, data transmission is tough in opportunistic networks. Therefore, it is necessary to choose neighbor discovery technology which is reliably and efficiently. The present algorithms do not achieve the optimal expectations, the active detection requires nodes to broadcast probe message periodically to discovery neighbor nodes, thus consumes a lot of energy. The passive approach keeps listening to the channel to estimate the information of neighbor nodes, but not all data frames could resolved correctly. This paper investigated a method combined active detection and passive listening, and compared with the existing neighbor discovery method. The optimization effect of neighbor discovery performance was verified by simulation. Compared with the maximum power method, even through this method has no advantage in packet loss rate, throughput capacity and end-to-end delay, the proposed method increases the number of neighbor discovery by about 20%, and reduces the energy consumption in the process of neighbor detection, saving up to 60%.

neighbor discovery; opportunistic networks; active detection; passive listening

國家自然科學(xué)基金(61472237)

TP393

：A

10.19358/j.issn.1674- 7720.2017.17.022

代宇茜，姜勝明.機(jī)會網(wǎng)絡(luò)中的鄰居發(fā)現(xiàn)性能優(yōu)化方法分析[J].微型機(jī)與應(yīng)用，2017,36(17)：75-78.

2017-03-13)

代宇茜(1993-)，女，碩士研究生，主要研究方向：機(jī)會網(wǎng)絡(luò)的鄰居發(fā)現(xiàn)。姜勝明(1964-)，男，博士，教授，主要研究方向：通信網(wǎng)絡(luò)結(jié)構(gòu)、協(xié)議和算法等。