王曉菲 蔡 英② 李 卓②

?

隨機移動模型下移動自組網(wǎng)無序傳輸端到端延遲閉解分析

王曉菲①蔡 英*①②李 卓①②

①(北京信息科技大學計算機學院 北京 100101)②(北京信息科技大學網(wǎng)絡(luò)文化與數(shù)字傳播研究北京市重點實驗室 北京 100101)

針對移動自組網(wǎng)端到端延遲在封閉形式分析方面的局限性，該文提出一種有效的針對無序傳輸，單副本兩跳中繼算法的網(wǎng)絡(luò)延遲建模方案，并給出其嚴格的理論延遲上界。首先針對多種隨機移動模型，證明了移動節(jié)點的相遇間隔時間可歸納為統(tǒng)一表達式。然后，綜合分析了媒介競爭、流量競爭、排隊延遲等問題，合理劃分并精確求解出了各延遲關(guān)鍵時間段，從而構(gòu)造了數(shù)據(jù)包排隊服務(wù)模型。最后推導出移動自組網(wǎng)端到端延遲的封閉形式理論上界。仿真結(jié)果表明，該理論延遲與實驗數(shù)據(jù)緊密吻合。

移動自組網(wǎng)；端到端延遲；隨機移動模型；無序傳輸；排隊服務(wù)模型

1 引言

顯然，上述漸近式分析方案只能從宏觀上描述延遲時間的變化趨勢，而確切的延遲描述方法更能引發(fā)網(wǎng)絡(luò)設(shè)計者的強烈興趣，通?？山柚忾]式求解方法加以解決，現(xiàn)有研究主要局限于采用i.i.d.移動模型的有序傳輸方式，例如：文獻[11]中分別討論i.i.d.移動模型下兩跳及多跳中繼算法，同時給出端到端延遲的封閉形式精確解表達式。文獻[14]為方便靈活操控延遲，設(shè)計副本兩跳中繼算法以支持冗余包傳輸，指出基于i.i.d.模型的端到端延遲的封閉形式上限是源端與目的端平均服務(wù)時間的函數(shù)。此外，2012年提出的一種基于組傳輸?shù)膬商欣^方案[15]解決了無序接收方式下封閉式平均傳輸延遲的分析問題。然而，該方案忽略了發(fā)送端數(shù)據(jù)包的排隊等待時間。

若將移動模型劃分為隨機移動模型與受限移動模型兩類[17]，文獻[18]已經(jīng)證明其中的隨機移動模型與i.i.d.移動模型在某些條件下存在等價性，這為精確衡量節(jié)點相遇行為提供了理論依據(jù)。基于此，針對無序傳輸方式，本文試圖在兩跳，單副本且存在干擾或競爭的中繼條件下，提出一種可廣泛適用于多種隨機移動模型的端到端延遲封閉形式分析方案，以克服上述弊端，并經(jīng)仿真實驗證實有效。

2 系統(tǒng)模型與中繼算法

2.1 網(wǎng)絡(luò)模型

將單位平方網(wǎng)絡(luò)范圍劃分為×個小區(qū)，初始時刻隨機分布有個移動節(jié)點。選用一種基于時隙且快速移動[14]的網(wǎng)絡(luò)場景，忽略移動模型復雜的邊界效應(yīng)，并規(guī)定每個節(jié)點在任一時隙持續(xù)期間僅歸屬于唯一的一個小區(qū)，每個時隙能夠成功傳輸?shù)淖畲蟊忍財?shù)固定為一個數(shù)據(jù)包。每個時隙至多允許節(jié)點在相遇條件下一同完成一次發(fā)送和一次接收，以及為某一數(shù)據(jù)分組提供的一次副本轉(zhuǎn)發(fā)。

為簡便起見，下文分別用標記,和依次代表源節(jié)點、目的節(jié)點和中繼節(jié)點。

2.2 流量模型

2.3 調(diào)度模型

局部傳輸場景要求任意時隙位于某一小區(qū)中的節(jié)點只能向位于相同小區(qū)中的鄰居節(jié)點傳送數(shù)據(jù)包，即網(wǎng)絡(luò)通信范圍近似取值為(21/2)/。同時可引入傳輸組概念[14]有效避免無線傳輸資源競爭與干擾。任意兩個水平距離且垂直距離均為整數(shù)倍的小區(qū)屬于相同傳輸組。為確保位于相同傳輸組內(nèi)的節(jié)點可以同時傳輸而不會發(fā)生相互干擾，的取值十分關(guān)鍵[14]，需滿足式(1)：

2.4 單副本兩跳中繼算法

單副本兩跳中繼算法規(guī)定包副本數(shù)上限為1，且源節(jié)點發(fā)出的每個數(shù)據(jù)包在到達目的節(jié)點之前最多經(jīng)歷兩跳傳輸。中繼節(jié)點或目的節(jié)點在收到一個完整的數(shù)據(jù)包后，立即對其進行處理，并從接收緩存隊列中刪除該包。兩跳中繼網(wǎng)絡(luò)每時每刻只存在3類傳輸形式，即-傳輸，-傳輸和-傳輸。當傳輸條件同時成立時，由于直接傳輸方式的開銷相對較低，故一般具有最高的優(yōu)先級。

3 相遇間隔時間

3.1 任意節(jié)點相遇間隔時間

源節(jié)點與任意節(jié)點相遇是數(shù)據(jù)包在端完成發(fā)送過程的前提。本節(jié)推導任意節(jié)點每次相遇所需等待的間隔時間，進而度量發(fā)送服務(wù)效率。因i.i.d.模型下節(jié)點位置在任意時隙呈現(xiàn)均勻分布，可知任意兩節(jié)點自初態(tài)起在第步相遇的概率為1/2，故某節(jié)點與其余任意節(jié)點(至少一個)在第步相遇的概率為

3.2 選定節(jié)點相遇間隔時間

兩跳中繼算法指出數(shù)據(jù)包副本自源節(jié)點發(fā)送至某一中繼節(jié)點后，需經(jīng)完成向某一固定目的節(jié)點的轉(zhuǎn)發(fā)操作。本節(jié)為此推導與每次相遇所需等待的平均間隔時間，用以描述端轉(zhuǎn)發(fā)服務(wù)效率。依據(jù)i.i.d.模型定義，任意節(jié)點在任意時隙位于任意小區(qū)的概率均為1/2，可知若將兩選定節(jié)點,首次相遇的時隙視作時刻0，則其后二者在第步相遇的概率為

3.3 隨機移動模型的等價性

按照節(jié)點的移動特性，可以將移動模型劃分為隨機移動模型與受限移動模型兩大類[17]。前者主要包括隨機漫步移動模型[13]、隨機路徑點移動模型[13]等。Cai 等人[18]的研究工作充分討論了隨機移動模型與i.i.d.模型滿足某些約束條件時存在的等價關(guān)系，因而本文采用i.i.d.模型對節(jié)點相遇時間進行整體討論。

引理1 在嚴格基于時隙且快速移動的網(wǎng)絡(luò)模型下，若各節(jié)點初始位置均勻分布，各時隙移動方式一致且獨立，則采用隨機移動模型的節(jié)點在任意時隙位于某一小區(qū)的概率為1/2，節(jié)點位置呈現(xiàn)均勻分布。

引理2 在嚴格基于時隙且快速移動的網(wǎng)絡(luò)模型下，若各節(jié)點初始位置集中于一個小區(qū)，各時隙移動方式一致且獨立，則采用隨機移動模型的節(jié)點在任意時隙位于某一小區(qū)的概率隨著移動次數(shù)的增加快速趨向1/2，節(jié)點位置近似于均勻分布。

由引理1可知，節(jié)點在任意時隙下所處位置的概率等同于i.i.d.模型，節(jié)點初始時刻的均勻分布狀態(tài)未隨時間而發(fā)生任何改變，任意兩節(jié)點在相同小區(qū)相遇的概率仍為1/2，故式(2)與式(3)顯然成立；由引理2可知兩選定節(jié)點在某一小區(qū)發(fā)生相遇，二者此后的相遇概率雖在短期內(nèi)受到上次相遇位置的影響，但二者再次相遇時各節(jié)點所處位置已無限接近于均勻分布，此時相遇概率可近似取值為1/2，即式(4)與式(5)成立。綜上，本文針對i.i.d.模型圍繞任意節(jié)點兩類相遇間隔時間的推導方法及結(jié)論，同樣適用于多種常見的隨機移動模型。

4 排隊服務(wù)模型

本節(jié)在隨機移動模型節(jié)點相遇時間間隔的研究基礎(chǔ)上，分別為源節(jié)點和中繼節(jié)點構(gòu)造兩類排隊模型，并借助概率描述各類傳輸事件及通信鏈路的發(fā)生條件，可作為后續(xù)延遲推導的基礎(chǔ)。

4.1 延遲基本定義及劃分

圖1 端到端延遲階段劃分

4.2 S端排隊模型

定理2服務(wù)時間X的期望與方差上界為

證明 由定理1結(jié)論可知，節(jié)點與節(jié)點在相遇后以概率1發(fā)生傳輸，故而

4.3 R端排隊模型

定理3 兩節(jié)點在相遇條件下發(fā)生-傳輸?shù)母怕蕿?/p>

化簡上式可得式(9) 證畢。

定理4端包副本到達時間間隔A的期望與方差上界為

證明 詳細過程請參照定理2證明。

定理5 兩節(jié)點在相遇條件下發(fā)生-傳輸?shù)母怕蕿?/p>

證明 詳細過程請參照定理3證明。 定理6服務(wù)時間X的期望與方差上界為

隨著文化程度的提高，醫(yī)務(wù)人員院感知識認知正確率逐漸增高，這個結(jié)果與邱湖海等［15］在2015年的研究報道是一致的。不過不同文化程度的醫(yī)務(wù)人員對醫(yī)院污物處理認知程度上并沒有顯著差異，平均認知正確率僅有66.36%，說明即便文化程度較高的醫(yī)務(wù)工作者對于醫(yī)院污物處理的認知也是不足的，提示在以后的醫(yī)院感染培訓中要著重加強醫(yī)院污物處理方面的培訓內(nèi)容。

5 端到端延遲閉解方案

本節(jié)利用第4節(jié)中所得端排隊模型與端排隊模型的相關(guān)結(jié)論，推導出端到端延遲上界的封閉表達式。首先，為精確度量包的端到端延遲，并最大限度合理約束理論上界，考慮不同通信鏈路的影響因素，特別是直接傳輸方式下對端服務(wù)額外耗時的合理解決方案。

對于––傳輸，如圖1(b)所示，包延遲上界為W+(X)+(W)+(X)。

定理7-成功傳輸概率為

證畢

定理8-成功傳輸概率為

因此，包最終經(jīng)––過程或-過程得以傳輸?shù)母怕史謩e為

仿照相似的推導思路，可將本文閉解方案推廣至多跳中繼環(huán)境。具體證明過程從略。

6 仿真結(jié)果與分析

仿真器依據(jù)系統(tǒng)模型的相關(guān)要求，在C++環(huán)境中設(shè)計并實現(xiàn)封閉形式端到端延遲上界的理論值計算以及單副本兩跳中繼的無序接收傳輸調(diào)度過程。仿真程序包含隨機數(shù)生成模塊，輸入流控制模塊，傳輸機會競爭模塊，傳輸組管理模塊，總傳輸調(diào)度模塊以及i.i.d.移動模型[11]，隨機漫步移動模型[9]等。通過對比實驗數(shù)據(jù)與理論延遲上界，分析驗證i.i.d.移動模型及多種常見隨機移動模型下移動自組網(wǎng)端到端延遲性能。

6.1 網(wǎng)絡(luò)參數(shù)設(shè)置

模擬程序以當前系統(tǒng)時間作為隨機種子，以i.i.d.移動模型，隨機漫步移動模型和隨機路徑點移動模型為例。仿真實驗運行總數(shù)達到107時隙，網(wǎng)絡(luò)主要參數(shù)依次設(shè)定為=8,=64,取值區(qū)間為(0,1)，并約定保護因子=1，則式(1)可相應(yīng)地化簡為=min{4,}=4。

6.2 理論結(jié)果準確性驗證

表1端到端延遲各階段理論值與實驗值對照

理論值實驗值理論值實驗值 i.i.d.WalkWayPointi.i.d.WalkWayPoint 0.300.50 E()1.591.59 1.59 1.59 1.59 1.59 1.59 1.59 E()64.0064.12 64.39 64.19 64.00 64.10 64.13 63.88 E(XS)60.5559.68 60.33 59.53 60.55 60.07 60.47 59.45 E(XR)..3838.403849.183818.283811.323838.403834.433836.343830.99 0.700.90 E() 1.59 1.59 1.59 1.59 1.59 1.59 1.59 1.59 E()64.00 63.97 64.07 64.22 64.00 64.02 63.97 63.76 E(XS)60.55 60.43 60.75 59.93 60.55 60.38 60.36 60.33 E(XR)3838.403842.503838.163846.843838.403846.033835.663843.54

此外，不同移動模型下端到端延遲的理論上界與實驗數(shù)據(jù)對比如圖2。在忽略程序隨機性誤差的前提下，表1證實了各延遲階段的理論分析結(jié)論，實驗結(jié)果與之緊密吻合。圖2驗證了端到端延遲理論上界在不同移動模型下的有效性。該圖線表明實驗數(shù)據(jù)與理論上界緊密匹配，且隨著輸入負載逐漸向1逼近，延遲的平均增長速率持續(xù)提升。

圖2 網(wǎng)絡(luò)端到端延遲理論上界與模擬仿真結(jié)果對比

7 結(jié)束語

封閉形式網(wǎng)絡(luò)延遲推導是移動自組網(wǎng)性能分析的關(guān)鍵問題之一，而在不同隨機移動模型下圍繞端到端延遲的研究目前尚不充分。本文將多種常見隨機移動模型合理化轉(zhuǎn)為i.i.d.移動模型，針對無序傳輸環(huán)境選用單副本兩跳中繼算法，重點討論存在干擾、競爭的數(shù)據(jù)包排隊服務(wù)過程，從而計算出移動自組網(wǎng)端到端延遲的封閉形式緊密上界，最終編程模擬驗證了理論結(jié)果。

[1] Fujishiro N, Nakano H, and Miyauchi A. A routing algorithm for mobile Ad hoc networks based on multi-agent cost learning[J]., 2013, 7(1): 67-72.

[2] Liu Y Y. Stable routing algorithm for mobile Ad hoc network[J]., 2011, 6(8): 1171-1178.

[3] Liang D. Opportunistic media access control and routing for delay-tolerant mobile Ad hoc networks[J]., 2012, 18(8): 949-965.

[4] Ikeda M, Kulla E, Barolli L,.. Performance evaluation of wireless mobile ad-hoc network via NS-3 simulator[C]. Proceedings of 14th International Conference on Network-Based Information Systems (NBiS 2011), Tirana, 2011: 135-141.

[5] Vaidya B, Denko M K, and Rodrigues J J P C. Security mechanism for voice over multipath mobile Ad hoc networks[J]., 2011, 11(2): 196-210.

[6] Otero A S and Atiquzzaman M. Ad aptive localized active route maintenance mechanism to improve performance of VoIP over ad hoc networks[J].s, 2011, 6(1): 68-78.

[7] Greco C, Cagnazzo M, and Pesquet-Popescu B. Low-latency video streaming with congestion control in mobile Ad-hoc networks[J]., 2012, 14(4): 1337-1350.

[8] Zhou L, Zhang Y, Rodrigues J,.. Quality-delay tradeoff for video streaming over mobile Ad hoc networks[C]. Proceedings of 2012 IEEE International Conference on Communications (ICC 2012), Ottawa, 2012: 223-227.

[10] Sharma G, Mazumdar R, and Shroff N B. Delay and capacity trade-offs in mobile Ad hoc networks: a global perspective[J]./, 2007, 15(5): 981-992.

[11] Neely M J and Modiano E. Capacity and delay tradeoffs for Ad-hoc mobile networks[J]., 2005, 51(6): 1917-1937.

[12] Sharma G and Mazumdar R. Delay and capacity trade-off in wireless Ad hoc networks with random mobility[OL]. http://ece.uwaterloo.ca/mazum/M2004.pdf, 2013, 11.

[13] Zhou S and Ying L. On delay constrained multicast capacity of large-scale mobile Ad-hoc networks[C]. Proceedings of 29th IEEE International Conference on Computer Communications (INFOCOM 2010), San Diego, 2010: 131-135.

[14] Liu J J, Jiang X H, Nishiyama H,.. Delay and capacity in Ad hoc mobile networks with f-cast relay algorithms[J]., 2011, 10(8): 2738-2751.

[15] Liu J J, Jiang X H, Nishiyama H,.. Generalized two-hop relay for flexible delay control in MANETs[J]., 2012, 20(6): 1950-1963.

[16] Cai Y, Wang X F, Li Z,. Delay and capacity in MANETs under random walk mobility model[OL]http://link.springer.com/article/10.1007% 2Fs11276-013- 0617-6#. 2013.

[17] 童超, 牛建偉, 龍翔, 等. 移動模型研究綜述[J]. 計算機科學, 2009, 36(10): 5-9.

Tong Chao, Niu Jian-wei, Long Xiang,.. Survey on mobility model[J]., 2009, 36(10): 5-9.

[18] Cai Y, Wang X F, and Zhang Y Q. The analysis of mobility models in MANETs with two-hop relay algorithm[C]. Proceedings of 4th International Conference on Intelligent Networking and Collaborative Systems (INCoS 2012), Bucharest, 2012: 229-236.

[19] Li P, Fang Y, and Li J. Throughput, delay, and mobility in wireless Ad-hoc networks[C]. Proceedings of 29th IEEE International Conference on Computer Communications (INFOCOM 2010), San Diego, 2010: 1-9.

[20] 盛友招. 排隊論及其在現(xiàn)代通信中的應(yīng)用[M]. 北京: 人民郵電出版社, 2007: 68-71.

王曉菲： 女，1990年生，碩士生，研究方向為無線網(wǎng)絡(luò)、信息安全.

蔡 英： 女，1966年生，博士，教授，研究方向為無線網(wǎng)絡(luò)、信息安全.

李 卓： 男，1983年生，博士，講師，研究方向為無線網(wǎng)絡(luò)、移動計算.

Closed-form Solution of End-to-end Delay with Out-of-order Delivery in MANETs under Random Mobility Models

Wang Xiao-fei①Cai Ying①②Li Zhuo①②

①(&,100101,)②(,&,100101,)

Due to the limitation of the closed-form analysis of end-to-end delay in mobile ad hoc networks, this paper develops an effective modeling scheme for delay in the networks where the delivery is out-of-order and the two-hop relay algorithm with single copy is involved, and presents a rigorous theoretical upper bound. First, for various random mobility models, it is proved that the inter-meeting time between mobile nodes can be expressed in a unified expression. Furthermore, taking the medium competition, the traffic competition and the queuing delay into consideration, the critical time period of delay is defined accurately, and then the queuing service is modeled. Finally, an exact upper bound of the end-to-end delay is derived in closed-form. Simulation results validate that the theoretical delay matches the experimental data closely.

Mobile Ad hoc NETworks (MANETs); End-to-end delay; Random mobility model; Out-of-order delivery; Queuing service model

TP393

A

1009-5896(2014)01-0034-07

10.3724/SP.J.1146.2013.00155

2013-01-29收到，2013-10-22改回

北京市教委科技發(fā)展計劃面上項目(KM201311232014, KM201411232013)資助課題

蔡英 ycai@bistu.edu.cn