自適應的機會網絡消息副本調整策略

黃丹莉，邱雪松，張黎明

(1.北京郵電大學網絡技術研究院，北京100876； 2.中國國際工程咨詢公司高技術業務部,北京100048)

自適應的機會網絡消息副本調整策略

黃丹莉1，邱雪松1，張黎明2

(1.北京郵電大學網絡技術研究院，北京100876； 2.中國國際工程咨詢公司高技術業務部,北京100048)

提出了一種具有自適應的消息副本調整策略。該方法對消息副本的數量屬性分層劃分，通過控制屬性來控制副本數量，是一種可定量定性調整的策略。根據劃分的屬性提取副本數優先度，綜合考慮消息的其他屬性，完成基于效用優先級消息隊列的調整。實驗結果表明，該方法能夠自適應調整消息副本的冗余程度，達到較高的投遞率，對不同網絡負載有較高的適應性。

機會網絡；路由協議；自適應；隊列調整

0 引言

與傳統網絡不同，機會網絡中沒有端到端的持久的連接路徑，借助節點相遇機會，完成不同連通域的源節點和目的節點的通信。它對于城市感知研究和未來普適計算的實現有很大的促進作用。因而近年來引起了科研工作者們的關注[1]。在野生動物追蹤[2]、星際互聯網絡[3]、車聯網等方面都具有很高的應用價值。較為典型的機會網絡路由協議有基于單消息的直接傳輸路由協議(direct delivery)[4]，源節點攜帶消息移動，直到遇到目的節點；epidemic路由協議[5]，消息被復制給所有不具有該消息副本的節點，并繼續復制傳播下去；prophet路由協議[6]，節點間維護相互之間的接觸概率信息，消息僅被復制給更高概率接觸到目標節點的其他節點，并繼續復制傳播下去；spray and wait路由協議[7]，消息創建時限定消息副本的個數，在spray階段傳播復制消息，當節點攜帶的消息副本不能再復制時進入wait階段，等待遇到目的節點完成投遞。上述方法中在消息副本數量的分配上缺乏網絡適應性，沒有考慮存儲空間對網絡性能的影響。

本文基于spray and wait路由協議提出一種可適應的機會網絡消息副本調整策略。通過劃分消息副本數量屬性達到定量定性控制的目的。量化消息副本的屬性價值進行隊列調整，能夠達到存儲空間占用較少、投遞率較高的效果。

1 消息副本數的自適應控制

首先定義了消息副本限額范圍(l0,lmax)：為了確保網絡容量能夠被充分利用且投遞率能夠達到一定的概率，分配一個靜態范圍屬性。

消息副本數屬性域：將一個消息副本的數量維度劃分為數值區域，表示3種不同的狀態，見表1。

表1 消息副本數屬性區域表

其中lawake，是最高狀態等級的消息副本數，lsleepy和lasleep分別表示另外兩種副本數狀態，狀態等級以此降低，這3個屬性被綜合用來控制消息副本在路由過程中的復制傳遞，lmax是副本數的上限。awake屬性的副本承擔著主要的路由轉發任務，該屬性值之和在整個網絡中不會發生變化(優先級保護)；sleepy屬性用于輔助加速擴散、增加傳遞成功率，為之后的傳遞任務減輕壓力且預留延遲誤差，它與asleep相互轉化；asleep屬性值的存在用于記錄和定量恢復至預定的副本數上限。需要注意的是，和噴射等待協議相似地，無論一條消息副本的3個數值區域是多少，只要該消息沒有被丟棄，那么在存儲空間只占用一條消息大小的空間。這三者的數量關系滿足如下方程組：

(1)

當網絡負載較輕時，調整策略是對于asleep屬性值不為0的消息，喚醒一個asleep副本，轉變為sleepy狀態。發生擁塞時，采取縮減策略(也稱為催眠過程)。對于節點vi存儲空間里的每一條消息都會進行副本數屬性值的修改，用于限制減少之后在網絡中繼續噴射的消息副本數量。即asleep屬性值減一，sleepy屬性值加一，awake屬性值不變；跳過asleep屬性值為0的消息，不做修改，調整下一條消息，見下列方程組：

(2)

2 基于消息副本效用的隊列調整

從消息副本投遞效用和存儲空間利用率的角度出發，綜合考慮了消息副本狀態和數量分布所反映的消息重要性、剩余生存時間ttl對投遞的效用回報。在傳輸消息時優先傳送效用更高的消息副本，在刪除消息時首先刪除投遞效用最低的。

首先定義了消息副本數量屬性反應的效用優先度：

lp=β1·lawake+β2·lsleepy+β3·lasleepy。

(3)

然后，結合消息效用和經歷跳數、延時所反應的消息效用回報，定義歸一化權重分配矩陣：

α=[α1α2α3]，

(4)

式中：α1表示分配給lp屬性的權重；α2表示ttl屬性所占的權重；α3表示跳數hop屬性的權重。

(5)

在效用重要度比值矩陣A中，a12表示副本數優先度lp與ttl屬性權重的重要性比值，a23表示ttl屬性權重與跳數hop屬性的重要度比值。

為了得到一致性可以計算最大特征根λ和對應的特征向量ω。ω的轉置矩陣即為歸一化權重分配矩陣α。在不同場景下這3個屬性相互的重要程度可以適當傾斜，但仍然需要一致性檢測。

最后得到消息副本的效用優先級計算公式如下所示：

(6)

1+msg.hop是考慮到剛剛創建的消息跳數為0，為了防止分母為0采取數值加一措施。另外，TTL_maxvi是預分配的消息最大生存時間，任意消息的剩余生存時間與其關系滿足msg.TTL∈[0，TTL_maxvi]；lp_maxvi是在節點vi上最大的消息副本數優先度，其中任意消息副本的副本數優先度滿足lp∈[0，lp_maxvi]；hop_maxvi是節點vi上最大的消息副本跳數。在計算消息效用優先級時采用最大最小規格化方法將這3個維度的效用加權求和。求出的值越大意味著傳遞該消息對網絡性能提高更有貢獻，其優先級就越高，反之，效用更低，優先級越低。

3 實驗結果

為了驗證算法的有效性和可適應性，下面展示使用theONEsimulator仿真器進行的實驗(核心參數見表2)。對消息的投遞率、傳輸開銷變化、仿真結束網絡節點平均存儲空間占用情況進行比較和分析。

表2 仿真參數設置

圖1 消息產生時間間隔對網絡各性能指標的影響

圖1呈現了關于AQOS算法網絡投遞率、傳輸開銷以及傳輸延時與消息產生時間間隔之間的關系。間隔減小，單位時間內產生的消息增加，網絡傳輸壓力增大，網絡投遞率降低，但是AQOS始終保持較為穩定的投遞率輸出。而達到這樣的效果是調整了消息副本數量，適應這樣的變化。

圖2 消息大小對網絡各性能指標的影響

圖2呈現了關于AQOS算法網絡投遞率、傳輸開銷以及傳輸延時與消息大小之間的關系。隨著消息大小的增大，單位消息需要占據的節點緩存空間增加，網絡負載壓力增大，網絡投遞率降低。但是AQOS始終保持較高的投遞率輸出，即使在消息大小為700k也仍然保持在83%以上；當消息大小不大于500k時，可以獲得至少89%的投遞率，且較為穩定。可以看出負載壓力較大時，消息副本數量自適應縮減，高效地利用有限的節點存儲資源。

圖3 投遞率與節點緩存大小的關系

消息成功率如圖3所示。從圖示結果可以看出，AQOS協議完成的消息投遞率保持在86%以上，優于其他協議。另外，對比分析噴射等待(sprayandwait)協議副本數配額為6和20的性能可以發現，AQOS提出的算法投遞率性能更優。同時，隨節點緩存空間增大而增大，但是幅度緩和，可見AQOS相較于其他協議不容易受到節點緩存空間變化的影響。最顯著的優勢在于節點緩存空間為5M時，仍然能夠完成較高的投遞率。

從圖4可以看出在仿真結束時，AQOS的緩存占用率僅高于低效率的DirectDelivery協議，在投遞率性能優越的同時剩余空間充裕，更容易抵抗短時間擁塞帶來的不良影響。可見AQOS較好地權衡了消息隊列中各消息可以帶來的投遞效用，進行了調度優化，故而獲得較高的投遞率。

圖4 網絡負載與節點緩存大小的關系

4 結語

本文提出了一種具有自適應的消息副本調整策略，該方法能夠自適應調整消息副本的冗余程度。通過大量的仿真實驗和對比實驗，在消息產生最頻繁、節點存儲空間最小的情況下仍然可以取得較高的投遞率和較大的剩余存儲空間，綜合性能優于其他經典路由協議。可以證明該策略對變化網絡負載有較高的適應性，達到較高的投遞率。

[1] 馬華東,袁培燕,趙東.移動機會網絡路由問題研究進展[J].軟件學報,2015,26(3):600-616.

[2]JuangP.Energy-efficientcomputingforwildlifetracking：designtrade-offsandearlyexperienceswithZebraNet[J].ACMSIGPLAM，2002，37：96-107.

[3]DianaR,LochinE,FranckL,etal.DTNroutingforquasi-deterministicnetworkswithapplicationtoLEOconstellations[J].InternationalJournalofSatelliteCommunications&Networking,2015，10：1-18.

[4]SpyropoulosT，PsounisKCS,Raghavendra.Efficientroutinginintermittentlyconnectedmobilenetworks:thesingle-copycase[J].IEEE/ACMTrans.Networking，2008，16：63-76.

[5]VahdatA,BeckerD.Epidemicroutingforpartially-connectedAdHocnetworks[R].TechnicalReportCS-200006,Durham:DukeUniversity,2000:1-14.

[6]LindgrenA,DoriaA,DaviesE,etal.Probabilisticroutingprotocolforintermittentlyconnectednetworks[J].ACMSIGMOBILEmobilecomputingandcommunicationsreview,2003,7(3):19-20.

[7]SpyropoulosT,PsounisK,RaghavendraCS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//Proceedinsofthe2005ACMSIGCOMNworkshoponDelay-tolerantnetworking(WDTN′05).NewYork,USA:ACM,2005:252-259.

[8]LoSC,LuCL.Adynamiccongestioncontrolbasedroutingfordelay-tolerantbetworks[C]//FuzzySystemsandKnowledgeDiscovery(FSKD),2012 9thInternationalConferenceon.Chongqing,China:IEEE,2012:2047-2051.

[9]TangS,LiW.QoSprovisioningandqueuemanagementinmobileadhocnetworks[C]//WirelessCommunicationsandNETWORKINGConference.LasVegas,Nevada,USA:IEEE,2006:400-405.

[10]ker?nenA,OttJ,K?rkk?inenT.TheonesimulatorforDTNprotocolevaluation[C]//Proceedingofthe2ndInternationalConferenceonSimulationToolsandTechniques(Simutools’09).Rome,Italy:ICST(InstituteforComputerSciences,Social-InformaticsandTelecommunicationsEngineering),2009:55.

The Optimization Strategy for Adaptable Opportunistic Network Message Replica

HUANG Dan-li，et al.

(InstituteofNetworkTechnology，BeijingUniversityofPostsandTelecommunications，Beijing100876，China)

This paper presents an adaptive message replica adjustment strategy.This method is a kind of quantitative and qualitative adjustment strategy to control the number of replicas by controlling attributes，and then according to the attribute partition，the priority of the replica is extracted.Moreover，the other attributes of the message are considered to form the message queue optimization based on the priority of utility.The experimental results show that the proposed method can adaptively adjust the redundancy degree of message replicas to achieve higher delivery rate，and have higher adaptability to different network loads.

opportunistic network；routing protocol；adaptable strategy；queue optimization

10.3969/j.issn.1009-8984.2016.04.025

2016-11-15

國家科技支撐計劃(2015BAH03F02) 國家自然科學基金面上項目(61272515)

黃丹莉(1992-)，女(漢)，湖北，碩士 主要研究機會網絡路由協議。

TP393

A

1009-8984(2016)04-0096-04