黃丹莉，邱雪松，張黎明

(1.北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京100876； 2.中國國際工程咨詢公司高技術(shù)業(yè)務(wù)部,北京100048)

自適應(yīng)的機(jī)會(huì)網(wǎng)絡(luò)消息副本調(diào)整策略

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

(1.北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京100876； 2.中國國際工程咨詢公司高技術(shù)業(yè)務(wù)部,北京100048)

提出了一種具有自適應(yīng)的消息副本調(diào)整策略。該方法對(duì)消息副本的數(shù)量屬性分層劃分，通過控制屬性來控制副本數(shù)量，是一種可定量定性調(diào)整的策略。根據(jù)劃分的屬性提取副本數(shù)優(yōu)先度，綜合考慮消息的其他屬性，完成基于效用優(yōu)先級(jí)消息隊(duì)列的調(diào)整。實(shí)驗(yàn)結(jié)果表明，該方法能夠自適應(yīng)調(diào)整消息副本的冗余程度，達(dá)到較高的投遞率，對(duì)不同網(wǎng)絡(luò)負(fù)載有較高的適應(yīng)性。

機(jī)會(huì)網(wǎng)絡(luò)；路由協(xié)議；自適應(yīng)；隊(duì)列調(diào)整

0 引言

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

本文基于spray and wait路由協(xié)議提出一種可適應(yīng)的機(jī)會(huì)網(wǎng)絡(luò)消息副本調(diào)整策略。通過劃分消息副本數(shù)量屬性達(dá)到定量定性控制的目的。量化消息副本的屬性價(jià)值進(jìn)行隊(duì)列調(diào)整，能夠達(dá)到存儲(chǔ)空間占用較少、投遞率較高的效果。

1 消息副本數(shù)的自適應(yīng)控制

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

消息副本數(shù)屬性域：將一個(gè)消息副本的數(shù)量維度劃分為數(shù)值區(qū)域，表示3種不同的狀態(tài)，見表1。

表1 消息副本數(shù)屬性區(qū)域表

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

(1)

當(dāng)網(wǎng)絡(luò)負(fù)載較輕時(shí)，調(diào)整策略是對(duì)于asleep屬性值不為0的消息，喚醒一個(gè)asleep副本，轉(zhuǎn)變?yōu)閟leepy狀態(tài)。發(fā)生擁塞時(shí)，采取縮減策略(也稱為催眠過程)。對(duì)于節(jié)點(diǎn)vi存儲(chǔ)空間里的每一條消息都會(huì)進(jìn)行副本數(shù)屬性值的修改，用于限制減少之后在網(wǎng)絡(luò)中繼續(xù)噴射的消息副本數(shù)量。即asleep屬性值減一，sleepy屬性值加一，awake屬性值不變；跳過asleep屬性值為0的消息，不做修改，調(diào)整下一條消息，見下列方程組：

(2)

2 基于消息副本效用的隊(duì)列調(diào)整

從消息副本投遞效用和存儲(chǔ)空間利用率的角度出發(fā)，綜合考慮了消息副本狀態(tài)和數(shù)量分布所反映的消息重要性、剩余生存時(shí)間ttl對(duì)投遞的效用回報(bào)。在傳輸消息時(shí)優(yōu)先傳送效用更高的消息副本，在刪除消息時(shí)首先刪除投遞效用最低的。

首先定義了消息副本數(shù)量屬性反應(yīng)的效用優(yōu)先度：

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

(3)

然后，結(jié)合消息效用和經(jīng)歷跳數(shù)、延時(shí)所反應(yīng)的消息效用回報(bào)，定義歸一化權(quán)重分配矩陣：

α=[α1α2α3]，

(4)

式中：α1表示分配給lp屬性的權(quán)重；α2表示ttl屬性所占的權(quán)重；α3表示跳數(shù)hop屬性的權(quán)重。

(5)

在效用重要度比值矩陣A中，a12表示副本數(shù)優(yōu)先度lp與ttl屬性權(quán)重的重要性比值，a23表示ttl屬性權(quán)重與跳數(shù)hop屬性的重要度比值。

為了得到一致性可以計(jì)算最大特征根λ和對(duì)應(yīng)的特征向量ω。ω的轉(zhuǎn)置矩陣即為歸一化權(quán)重分配矩陣α。在不同場(chǎng)景下這3個(gè)屬性相互的重要程度可以適當(dāng)傾斜，但仍然需要一致性檢測(cè)。

最后得到消息副本的效用優(yōu)先級(jí)計(jì)算公式如下所示：

(6)

1+msg.hop是考慮到剛剛創(chuàng)建的消息跳數(shù)為0，為了防止分母為0采取數(shù)值加一措施。另外，TTL_maxvi是預(yù)分配的消息最大生存時(shí)間，任意消息的剩余生存時(shí)間與其關(guān)系滿足msg.TTL∈[0，TTL_maxvi]；lp_maxvi是在節(jié)點(diǎn)vi上最大的消息副本數(shù)優(yōu)先度，其中任意消息副本的副本數(shù)優(yōu)先度滿足lp∈[0，lp_maxvi]；hop_maxvi是節(jié)點(diǎn)vi上最大的消息副本跳數(shù)。在計(jì)算消息效用優(yōu)先級(jí)時(shí)采用最大最小規(guī)格化方法將這3個(gè)維度的效用加權(quán)求和。求出的值越大意味著傳遞該消息對(duì)網(wǎng)絡(luò)性能提高更有貢獻(xiàn)，其優(yōu)先級(jí)就越高，反之，效用更低，優(yōu)先級(jí)越低。

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的有效性和可適應(yīng)性，下面展示使用theONEsimulator仿真器進(jìn)行的實(shí)驗(yàn)(核心參數(shù)見表2)。對(duì)消息的投遞率、傳輸開銷變化、仿真結(jié)束網(wǎng)絡(luò)節(jié)點(diǎn)平均存儲(chǔ)空間占用情況進(jìn)行比較和分析。

表2 仿真參數(shù)設(shè)置

圖1 消息產(chǎn)生時(shí)間間隔對(duì)網(wǎng)絡(luò)各性能指標(biāo)的影響

圖1呈現(xiàn)了關(guān)于AQOS算法網(wǎng)絡(luò)投遞率、傳輸開銷以及傳輸延時(shí)與消息產(chǎn)生時(shí)間間隔之間的關(guān)系。間隔減小，單位時(shí)間內(nèi)產(chǎn)生的消息增加，網(wǎng)絡(luò)傳輸壓力增大，網(wǎng)絡(luò)投遞率降低，但是AQOS始終保持較為穩(wěn)定的投遞率輸出。而達(dá)到這樣的效果是調(diào)整了消息副本數(shù)量，適應(yīng)這樣的變化。

圖2 消息大小對(duì)網(wǎng)絡(luò)各性能指標(biāo)的影響

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

圖3 投遞率與節(jié)點(diǎn)緩存大小的關(guān)系

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

從圖4可以看出在仿真結(jié)束時(shí)，AQOS的緩存占用率僅高于低效率的DirectDelivery協(xié)議，在投遞率性能優(yōu)越的同時(shí)剩余空間充裕，更容易抵抗短時(shí)間擁塞帶來的不良影響?？梢夾QOS較好地權(quán)衡了消息隊(duì)列中各消息可以帶來的投遞效用，進(jìn)行了調(diào)度優(yōu)化，故而獲得較高的投遞率。

圖4 網(wǎng)絡(luò)負(fù)載與節(jié)點(diǎn)緩存大小的關(guān)系

4 結(jié)語

本文提出了一種具有自適應(yīng)的消息副本調(diào)整策略，該方法能夠自適應(yīng)調(diào)整消息副本的冗余程度。通過大量的仿真實(shí)驗(yàn)和對(duì)比實(shí)驗(yàn)，在消息產(chǎn)生最頻繁、節(jié)點(diǎn)存儲(chǔ)空間最小的情況下仍然可以取得較高的投遞率和較大的剩余存儲(chǔ)空間，綜合性能優(yōu)于其他經(jīng)典路由協(xié)議?？梢宰C明該策略對(duì)變化網(wǎng)絡(luò)負(fù)載有較高的適應(yīng)性，達(dá)到較高的投遞率。

[1] 馬華東,袁培燕,趙東.移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由問題研究進(jìn)展[J].軟件學(xué)報(bào),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

國家科技支撐計(jì)劃(2015BAH03F02) 國家自然科學(xué)基金面上項(xiàng)目(61272515)

黃丹莉(1992-)，女(漢)，湖北，碩士 主要研究機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議。

TP393

A

1009-8984(2016)04-0096-04