王曉菲 蔡 英② 李 卓②

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

2.2 流量模型

2.3 調(diào)度模型

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

2.4 單副本兩跳中繼算法

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

3 相遇間隔時(shí)間

3.1 任意節(jié)點(diǎn)相遇間隔時(shí)間

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

3.2 選定節(jié)點(diǎn)相遇間隔時(shí)間

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

3.3 隨機(jī)移動(dòng)模型的等價(jià)性

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

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

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

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

4 排隊(duì)服務(wù)模型

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

4.1 延遲基本定義及劃分

圖1 端到端延遲階段劃分

4.2 S端排隊(duì)模型

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

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

4.3 R端排隊(duì)模型

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

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

定理4端包副本到達(dá)時(shí)間間隔A的期望與方差上界為

證明 詳細(xì)過(guò)程請(qǐng)參照定理2證明。

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

證明 詳細(xì)過(guò)程請(qǐng)參照定理3證明。 定理6服務(wù)時(shí)間X的期望與方差上界為

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

5 端到端延遲閉解方案

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

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

定理7-成功傳輸概率為

證畢

定理8-成功傳輸概率為

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

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

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

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

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

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

6.2 理論結(jié)果準(zhǔn)確性驗(yàn)證

表1端到端延遲各階段理論值與實(shí)驗(yàn)值對(duì)照

理論值實(shí)驗(yàn)值理論值實(shí)驗(yàn)值 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

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

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

7 結(jié)束語(yǔ)

封閉形式網(wǎng)絡(luò)延遲推導(dǎo)是移動(dòng)自組網(wǎng)性能分析的關(guān)鍵問(wèn)題之一，而在不同隨機(jī)移動(dòng)模型下圍繞端到端延遲的研究目前尚不充分。本文將多種常見(jiàn)隨機(jī)移動(dòng)模型合理化轉(zhuǎn)為i.i.d.移動(dòng)模型，針對(duì)無(wú)序傳輸環(huán)境選用單副本兩跳中繼算法，重點(diǎn)討論存在干擾、競(jìng)爭(zhēng)的數(shù)據(jù)包排隊(duì)服務(wù)過(guò)程，從而計(jì)算出移動(dòng)自組網(wǎng)端到端延遲的封閉形式緊密上界，最終編程模擬驗(yàn)證了理論結(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] 童超, 牛建偉, 龍翔, 等. 移動(dòng)模型研究綜述[J]. 計(jì)算機(jī)科學(xué), 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] 盛友招. 排隊(duì)論及其在現(xiàn)代通信中的應(yīng)用[M]. 北京: 人民郵電出版社, 2007: 68-71.

王曉菲： 女，1990年生，碩士生，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)、信息安全.

蔡 英： 女，1966年生，博士，教授，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)、信息安全.

李 卓： 男，1983年生，博士，講師，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)、移動(dòng)計(jì)算.

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ā)展計(jì)劃面上項(xiàng)目(KM201311232014, KM201411232013)資助課題

蔡英 ycai@bistu.edu.cn