胡 鶴 劉 丹 朱 濤，2 李澤西，2

（1.北京航空航天大學(xué)，中國(guó) 北京100191；2.網(wǎng)絡(luò)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，中國(guó) 北京100191）

0 引言

車(chē)載網(wǎng)絡(luò)是智能城市交通系統(tǒng)的通信基礎(chǔ)對(duì)于采集和傳遞交通路況信息、緩解交通擁堵、提高交通運(yùn)輸效率、降低車(chē)輛污染等都有重要作用。然而車(chē)載網(wǎng)絡(luò)具有節(jié)點(diǎn)移動(dòng)自主性強(qiáng)、移動(dòng)速度快、分布不均勻、拓?fù)渥兓l繁等特點(diǎn)。這使得現(xiàn)有的移動(dòng)車(chē)載網(wǎng)絡(luò)通信技術(shù)還難以滿(mǎn)足智能交通等應(yīng)用的通信需求。究其根本原因在于底層通信的間歇性鏈路與上層通信的持續(xù)性需求之間存在矛盾(使得Internet或Ad Hoc網(wǎng)絡(luò)所采用的傳統(tǒng)通信技術(shù)在車(chē)載網(wǎng)絡(luò)組網(wǎng)實(shí)踐中面臨著巨大的挑戰(zhàn)。

許多研究者正試圖利用移動(dòng)容遲網(wǎng)絡(luò)Delay Tolerant NetworkDTN技術(shù)來(lái)解決這一矛盾。移動(dòng)容遲網(wǎng)絡(luò)是隨著無(wú)線通信與計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展而出現(xiàn)的一種新興技術(shù)目的是滿(mǎn)足極端環(huán)境下計(jì)算機(jī)網(wǎng)絡(luò)的數(shù)據(jù)通信需求其主要特點(diǎn)是使用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”(store-carry-forward)[1]的數(shù)據(jù)通信技術(shù)在缺乏底層持續(xù)鏈路的情況下利用被稱(chēng)為“接觸”Contact的傳輸機(jī)會(huì)以異步的方式來(lái)進(jìn)行逐跳的消息傳遞?？梢钥闯鲆苿?dòng)容遲網(wǎng)絡(luò)技術(shù)能夠?yàn)槌鞘熊?chē)載網(wǎng)絡(luò)提供更為完善的組網(wǎng)技術(shù)和通信基礎(chǔ)平臺(tái)在提高城市車(chē)載網(wǎng)絡(luò)的可達(dá)性、實(shí)時(shí)性和差異容忍性方面具有十分重要的實(shí)用價(jià)值和廣泛的應(yīng)用前景。

基于城市車(chē)載環(huán)境的容遲網(wǎng)絡(luò)稱(chēng)為城市車(chē)載容遲網(wǎng)絡(luò)Urban Vehicular Delay-tolerant Network或UVDN。地理通信作為UVDN的一大特色功能主要服務(wù)于對(duì)地理信息敏感的消息。此類(lèi)消息通常需要被傳送到特定的地理位置其可能是路況信息更新、交通事故提醒、免費(fèi)停車(chē)場(chǎng)指引[2]也可能是針對(duì)出租車(chē)的客流信息傳達(dá)等。車(chē)輛作為UVDN的移動(dòng)節(jié)點(diǎn)同樣采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的模式來(lái)滿(mǎn)足連接稀疏情況下車(chē)載網(wǎng)絡(luò)的數(shù)據(jù)通信需求。雖然UVDN以通信效率為代價(jià)獲得通信的可行性但在實(shí)際應(yīng)用中消息是普遍具有時(shí)效性的也就是說(shuō)一個(gè)消息可能只在其產(chǎn)生后的某一段時(shí)間內(nèi)是有價(jià)值的。因此UVDN的通信延時(shí)分析對(duì)路由的設(shè)計(jì)及網(wǎng)絡(luò)協(xié)議的優(yōu)化都是十分必要的。然而城市的車(chē)輛數(shù)目龐大車(chē)速在地理上的高度不均車(chē)輛移動(dòng)嚴(yán)格受到道路約束等等因素使得UVDN的延時(shí)分析方法在設(shè)計(jì)上存在挑戰(zhàn)。

由于UVDN是容遲網(wǎng)絡(luò)的特殊應(yīng)用范例我們希望能從一般容遲網(wǎng)絡(luò)的延時(shí)研究中獲得啟發(fā)。遺憾的是雖然針對(duì)一般容遲網(wǎng)絡(luò)的延時(shí)研究已經(jīng)取得了優(yōu)秀的成果[3-5]但因?yàn)橐话闳葸t網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)自由度大且缺乏節(jié)點(diǎn)定位信息這些成果難以被推廣到UVDN的延時(shí)分析。部分研究學(xué)者[6-7]從車(chē)載網(wǎng)絡(luò)特征出發(fā)建立模型給出了以特定地理位置作為通信終點(diǎn)的城郊車(chē)載容遲網(wǎng)絡(luò)的延時(shí)分析。由于城郊地區(qū)車(chē)輛數(shù)目有限道路構(gòu)造簡(jiǎn)單其研究不考慮消息在車(chē)輛間的轉(zhuǎn)發(fā)消息只能由車(chē)輛攜帶到通信目的地。然而在城市環(huán)境下車(chē)輛數(shù)目龐大且車(chē)輛間的接觸頻繁為提高通信效率車(chē)輛間的消息轉(zhuǎn)發(fā)功能是不可忽略的。目前面向地理通信且考慮車(chē)輛間轉(zhuǎn)發(fā)的UVDN的研究多注重于單副本條件下的路由協(xié)議設(shè)計(jì)[2，8-9]對(duì)于多副本條件下的延時(shí)等網(wǎng)絡(luò)性能的理論分析還很缺乏。

本文考慮的是UVDN在多副本傳送條件下以特定地理位置為終點(diǎn)的通信延時(shí)問(wèn)題。網(wǎng)絡(luò)內(nèi)的車(chē)輛均配備有在一定范圍可以通信的路由設(shè)備此設(shè)備能夠存儲(chǔ)攜帶和轉(zhuǎn)發(fā)消息這使得消息在UVDN中可以以多副本形式傳遞。由于UVDN中的車(chē)輛行駛受到復(fù)雜的道路布局限制我們將從簡(jiǎn)化城市地理信息和抽象車(chē)輛移動(dòng)模式兩方面入手對(duì)UVDN的通信延時(shí)建模。地理劃分是簡(jiǎn)化城市地理信息的有力手段我們根據(jù)城市道路布局提出了干路中心法Major-road Centered Map Segmentation,MCMS將城市分割為以主干路片段為中心的分區(qū)。城市中的每一個(gè)地理位置屬于且僅可能屬于某一個(gè)分區(qū)。車(chē)輛移動(dòng)模式方面在城市分區(qū)的基礎(chǔ)上我們建立了一個(gè)UVDN的延時(shí)分析模型MDM(MCMS-based Delay Model)其中我們假設(shè)車(chē)輛在短時(shí)間內(nèi)的位置移動(dòng)是一個(gè)馬爾科夫過(guò)程。根據(jù)此馬爾科夫鏈及網(wǎng)絡(luò)副本發(fā)送率單位時(shí)間內(nèi)網(wǎng)絡(luò)中產(chǎn)生的新的消息副本數(shù)可以得到UVDN通信延時(shí)的累積分布函數(shù)。

本文中我們將以“兩跳”轉(zhuǎn)發(fā)模式為例詳細(xì)介紹UVDN的延時(shí)分析模型MDM。在這種轉(zhuǎn)發(fā)模式下只有消息原本的攜帶車(chē)輛有轉(zhuǎn)發(fā)權(quán)利攜帶消息副本的車(chē)輛無(wú)權(quán)利再將消息內(nèi)容轉(zhuǎn)發(fā)給其他車(chē)輛。

本文的主要貢獻(xiàn)有：

1）針對(duì)城市以地理位置為終點(diǎn)的通信問(wèn)題本文提出了新的區(qū)域劃分方法——干路中心法即MCMS。此劃分方法抓住了城UVDN的特點(diǎn):城市干路上的車(chē)輛流通量大移動(dòng)節(jié)點(diǎn)接觸頻繁。因此以干路片段為中心劃分城市區(qū)域貼近了現(xiàn)實(shí)的城市車(chē)載環(huán)境且降低了移動(dòng)節(jié)點(diǎn)在分區(qū)中定位的復(fù)雜性。而由此方法所得的分區(qū)正是接下來(lái)延時(shí)分析模型的基礎(chǔ)結(jié)構(gòu)。

2）本文將城市車(chē)輛的移動(dòng)抽象為以分區(qū)作為狀態(tài)節(jié)點(diǎn)的馬爾科夫過(guò)程并以此為基礎(chǔ)建立理論分析模型MDM給出UVDN地理通信的延時(shí)分布函數(shù)。此模型抓住了城市車(chē)輛集的宏觀運(yùn)動(dòng)規(guī)律不依賴(lài)車(chē)輛的個(gè)體出行偏好這使得車(chē)輛集構(gòu)造復(fù)雜且數(shù)目龐大的UVDN的通信延時(shí)計(jì)算大大簡(jiǎn)化。

3）本文建立了多副本傳送條件下的城市地理通信延時(shí)模型MDM這里車(chē)輛間的交流是被考慮在內(nèi)的這一考慮在城市車(chē)載環(huán)境下是十分有必要的。而通過(guò)MDM得到的理論延時(shí)分布表現(xiàn)出了與仿真結(jié)果較好的吻合度這表明MDM建模假設(shè)的合理性及建模方法的正確性。

本文的結(jié)構(gòu)安排如下。第一章和第二章將分別詳細(xì)介紹干路中心法MCMS及基于該劃分方法的UVDN延時(shí)分析模型MDM通過(guò)MDM可以得到通信延時(shí)的分布函數(shù)表達(dá)式。在第三章中我們利用北京市出租車(chē)軌跡數(shù)據(jù)集檢驗(yàn)MDM給出的延時(shí)分析結(jié)果并將MDM的理論延時(shí)分布與實(shí)際數(shù)據(jù)仿真結(jié)果進(jìn)行比較。第四章中我們將根據(jù)仿真結(jié)果對(duì)MDM進(jìn)行總結(jié)。最后在第五章我們將給出目前國(guó)內(nèi)外學(xué)者針對(duì)移動(dòng)容遲網(wǎng)絡(luò)和車(chē)載網(wǎng)絡(luò)的研究成果。

1 MCMS干路中心法

以地理位置為通信終點(diǎn)的UVDN延時(shí)分析需要依賴(lài)網(wǎng)絡(luò)節(jié)點(diǎn)的地理信息。這類(lèi)復(fù)雜的信息不僅包括目的地與消息原本攜帶車(chē)輛的地理位置還包括其他車(chē)輛的位置移動(dòng)規(guī)律。由于移動(dòng)路由設(shè)備有一定的通信覆蓋范圍將城市劃分成地理連續(xù)的分區(qū)不僅有利于網(wǎng)絡(luò)節(jié)點(diǎn)地理信息的獲取更便于建立通信延時(shí)的分析模型。

地理劃分的最簡(jiǎn)單辦法是將整片區(qū)域按經(jīng)緯度均勻劃分。但這種方法沒(méi)有考慮到城市道路布局以及道路對(duì)車(chē)輛行駛的限制。在[18]中作者認(rèn)為城市道路可以分為干路和支路。與支路比較干路單位時(shí)間內(nèi)的車(chē)流量較大設(shè)計(jì)較寬且布局相對(duì)簡(jiǎn)單明了。因此其提出一種以干路布局作為依據(jù)的城市地理劃分法將干路圍成的最小區(qū)域作為分區(qū)如圖1所示。圖中黑色直線代表城市干路紅色及藍(lán)色線段圍成的區(qū)域?yàn)樗玫姆謪^(qū)。然而此方法得到的分區(qū)在UVDN中暴露出不適應(yīng)性。車(chē)流量較大的干路是車(chē)輛間通信的主要場(chǎng)所這種方法可能將一條干路上的車(chē)輛分隔到兩個(gè)分區(qū)中 這使得車(chē)輛定位的復(fù)雜度增大了而精確度卻降低了。因此我們提出了新的基于干路布局的城市地理劃分法——干路中心法Major-road Centered Map Segmentation,MCMS。

圖1 以干路為邊界的分區(qū)方法示意圖

MCMS的執(zhí)行步驟如下。選取干路的交點(diǎn)及干路圍出的區(qū)域的中心點(diǎn)作為坐標(biāo)點(diǎn)連接四個(gè)相鄰的坐標(biāo)點(diǎn)便得到一個(gè)分區(qū)如圖2所示。MCMS將車(chē)輛與車(chē)輛接觸頻繁的地區(qū)劃為分區(qū)這使得車(chē)輛的跟蹤更加準(zhǔn)確。除此之外MCMS以坐標(biāo)點(diǎn)連接得到分區(qū)適用于多樣的城市干路布局。通過(guò)這種具有科學(xué)合理性及普適性的劃分方法得到的城市分區(qū)正是延時(shí)分析模型MDM的基礎(chǔ)結(jié)構(gòu)。

圖2 MCMS示意圖

2 UVDN延時(shí)分析模型MDM

本章將以“兩跳”轉(zhuǎn)發(fā)模式為例介紹基于MCMS的UVDN延時(shí)分析模型MDMMCMS-based Delay Model。此模型通過(guò)車(chē)輛在短時(shí)間內(nèi)的位移模式得到以地理位置為通信終點(diǎn)的UVDN的延時(shí)分布函數(shù)。

首先按照上一章介紹的MCMS將整個(gè)城市區(qū)域劃分后得到n-1個(gè)分區(qū)依次將其編號(hào)為A1，A2，…，An-1城市之外的區(qū)域定義為黑洞區(qū)編號(hào)為An。除黑洞區(qū)之外的每個(gè)分區(qū)均是以干路片段為中心的多邊形區(qū)域。UVDN中的移動(dòng)節(jié)點(diǎn)由城市車(chē)輛集構(gòu)成。車(chē)輛可以行駛在城市內(nèi)部的任意道路上并均配有可以攜帶和轉(zhuǎn)發(fā)消息的路由設(shè)備。

在0時(shí)刻分區(qū)Ai內(nèi)一輛車(chē)O要將消息I通過(guò)UVDN傳送到分區(qū)Aji≠j且均不是黑洞區(qū)。Ai稱(chēng)為消息源分區(qū)Aj稱(chēng)為目標(biāo)分區(qū)。車(chē)輛O稱(chēng)為源頭節(jié)點(diǎn)。消息I由O攜帶移動(dòng)且其副本僅可以由O轉(zhuǎn)發(fā)給與其相遇的車(chē)輛。從O得到消息I副本的車(chē)輛稱(chēng)為轉(zhuǎn)呈節(jié)點(diǎn)。消息I可以隨著源頭節(jié)點(diǎn)及轉(zhuǎn)呈節(jié)點(diǎn)的移動(dòng)到達(dá)城市的某些分區(qū)形成消息傳遞的軌跡網(wǎng)。當(dāng)有車(chē)輛從接收消息I開(kāi)始首次達(dá)到分區(qū)Aj時(shí)通信宣告結(jié)束。0時(shí)刻與通信結(jié)束時(shí)刻間的時(shí)長(zhǎng)稱(chēng)為通信延時(shí)。我們的工作是在MCMS的城市分區(qū)基礎(chǔ)上建立UVDN的延時(shí)分析模型MDM通過(guò)MDM給出兩分區(qū)間通信延時(shí)的分布函數(shù)。首先我們給出模型中需要的符號(hào)及必要的假設(shè)。

2.1 符號(hào)和假設(shè)

MDM主要通過(guò)城市車(chē)輛在短時(shí)間內(nèi)的位置移動(dòng)規(guī)律來(lái)得到通信延時(shí)的分布函數(shù)。下面我們給出一些符號(hào)和假設(shè)來(lái)簡(jiǎn)化實(shí)際的城市車(chē)輛移動(dòng)模式。

2.1.1 符號(hào)

通過(guò)車(chē)輛的實(shí)際移動(dòng)軌跡數(shù)據(jù)可以得到一組等時(shí)間間隔的地圖快照。設(shè)｛X0，X1，X2，…，Xn，…｝為地圖快照中記錄下的某一車(chē)輛的軌跡其中Xk（k∈N+）為k時(shí)刻該車(chē)所在的分區(qū)編號(hào)。T為車(chē)輛軌跡中相鄰時(shí)刻的時(shí)間間隔其也是兩個(gè)相鄰快照間的時(shí)長(zhǎng)。車(chē)輛的行駛軌跡在地理上是連續(xù)的為體現(xiàn)這一客觀事實(shí)間隔時(shí)間T的取值不宜過(guò)大應(yīng)盡量使車(chē)輛在相鄰時(shí)刻的快照中處于地理上相鄰或相同的分區(qū)。記N為車(chē)O在T內(nèi)轉(zhuǎn)發(fā)出的消息副本數(shù)即單步副本發(fā)送數(shù)此參數(shù)與實(shí)際的車(chē)載環(huán)境密切相關(guān)。

2.1.2 假設(shè)

我們提出以下三條假設(shè)來(lái)描述車(chē)輛在分區(qū)間的位置移動(dòng)模式。車(chē)輛的移動(dòng)是彼此間相互獨(dú)立的一輛車(chē)的移動(dòng)并不受其他車(chē)輛移動(dòng)的干擾。

一輛車(chē)在下一時(shí)刻所處的分區(qū)只與當(dāng)前時(shí)刻所在的分區(qū)有關(guān)。因此｛X0，X1，X2，…，Xn，…｝為一個(gè)馬爾科夫過(guò)程。即

在城市環(huán)境下車(chē)輛數(shù)目龐大結(jié)隊(duì)出行比例較小。因此車(chē)輛的移動(dòng)可以看作是相互獨(dú)立的第一條假設(shè)是對(duì)實(shí)際車(chē)載環(huán)境的合理簡(jiǎn)化。

城市車(chē)輛總體的出行分布受城市人口出行需求的支配具有一定宏觀的規(guī)律。在車(chē)輛數(shù)目較大的情況下一個(gè)分區(qū)的車(chē)輛集在短時(shí)間內(nèi)的位置移動(dòng)分布與車(chē)輛個(gè)體的歷史軌跡并無(wú)很強(qiáng)的關(guān)聯(lián)性而與該分區(qū)的車(chē)輛流動(dòng)規(guī)律有關(guān)。并且在UVDN中車(chē)O對(duì)于轉(zhuǎn)呈節(jié)點(diǎn)的選擇無(wú)個(gè)體偏好性。因此將UVDN中的車(chē)輛移動(dòng)簡(jiǎn)化為馬爾科夫過(guò)程是具有宏觀意義的。

對(duì)于第三條假設(shè)當(dāng)T較小時(shí)車(chē)輛在每一跳的起始和終止分區(qū)逗留的時(shí)間可看作是相同的。

2.2 一步轉(zhuǎn)移概率矩陣

根據(jù)2.1.2中的第二條假設(shè)一輛車(chē)的軌跡可視為一個(gè)馬爾科夫過(guò)程此馬爾科夫鏈的節(jié)點(diǎn)為城市中的各分區(qū)。那么如何得到此馬爾科夫鏈的一步轉(zhuǎn)移概率矩陣呢本節(jié)我們將介紹如何采用統(tǒng)計(jì)的方法從車(chē)輛的實(shí)際軌跡數(shù)據(jù)集中得出一步轉(zhuǎn)移概率矩陣。

現(xiàn)有通過(guò)MCMS得到的n個(gè)分區(qū)分別標(biāo)記為A1，A2，…，An其中An為黑洞區(qū)。每隔T拍下一個(gè)地圖快照該快照上記錄了此時(shí)刻網(wǎng)絡(luò)中各個(gè)車(chē)輛所在的分區(qū)共統(tǒng)計(jì)k個(gè)時(shí)刻。記Ai（j）為在第j個(gè)時(shí)刻造訪若一輛車(chē)某一跳的起始分區(qū)為Ak1終止分區(qū)為Ak2則其一步內(nèi)在兩分分區(qū)Ai的車(chē)輛集。將這n個(gè)分區(qū)在k個(gè)時(shí)刻的所有車(chē)輛集寫(xiě)成一個(gè)矩陣形式處理得到。記｜Ai（m）｜為m時(shí)刻Ai中的造訪車(chē)輛數(shù)目而｜為在m時(shí)刻造訪Ai且在m+1時(shí)刻造訪Aj的車(chē)輛的數(shù)目。｜也就

從Ai到Aj的一步轉(zhuǎn)移概率pij可以通過(guò)對(duì)（1）中的相應(yīng)數(shù)據(jù)進(jìn)行是經(jīng)一步由Ai轉(zhuǎn)移到Aj的車(chē)輛數(shù)這里1≤m≤k-1，m∈N+。在一共k個(gè)時(shí)刻通過(guò)以下算式計(jì)算一步轉(zhuǎn)移概率pij

公式（2）表明pij是一步由Ai到Aj的總轉(zhuǎn)移車(chē)次數(shù)占Ai的總到訪車(chē)次數(shù)的比例。這里需注意只要一輛車(chē)在一個(gè)快照中的地理位置屬于Ai就稱(chēng)該車(chē)造訪Ai一次。而該車(chē)位于Ai的快照個(gè)數(shù)即為該車(chē)造訪Ai的次數(shù)。公式（2）中總轉(zhuǎn)移車(chē)次數(shù)與總到訪車(chē)次數(shù)的比值是車(chē)輛在k個(gè)時(shí)刻由Ai到Aj的平均一步轉(zhuǎn)移概率。這個(gè)平均一步轉(zhuǎn)移概率滿(mǎn)足馬爾科夫鏈的一步轉(zhuǎn)移概率矩陣性質(zhì)。另外需注意此一步轉(zhuǎn)移概率是有向的即pij與pji是可以不相等的。

2.3 消息在分區(qū)間傳遞的效率

一步轉(zhuǎn)移概率矩陣是馬爾科夫鏈的核心要素。接下來(lái)將介紹MDM如何利用馬爾科夫鏈理論得到通信延時(shí)的分布函數(shù)。

其中pij為車(chē)輛從Ai到Aj的一步轉(zhuǎn)移概率。設(shè)f（n）

ij為車(chē)輛從Ai經(jīng)過(guò)n步首次到達(dá)Aj的概率即其中Xk為第k步所在的分區(qū)。由隨機(jī)過(guò)程中對(duì)Markov鏈的相關(guān)分析[19]可得f（n）ij的遞推公式如下

根據(jù)（3）和（4）可以得到車(chē)輛從Ai到Aj任意步數(shù)的首達(dá)概率序列:進(jìn)一步設(shè)車(chē)輛在m步之內(nèi)能夠從Ai到Aj達(dá)的概率為l（m）ij則

2.3.2 車(chē)輛在非目標(biāo)區(qū)域之間的轉(zhuǎn)動(dòng)

當(dāng)一輛車(chē)接收到消息I的副本成為轉(zhuǎn)呈節(jié)點(diǎn)后其有可能攜帶消息在非目標(biāo)分區(qū)中運(yùn)轉(zhuǎn)若干時(shí)間之后再駛?cè)肽繕?biāo)分區(qū)Aj。車(chē)輛在非目標(biāo)區(qū)域中的轉(zhuǎn)動(dòng)規(guī)律亦可通過(guò)矩陣P給出。

設(shè)Hj為P中除掉Aj所對(duì)應(yīng)的行和列后所得到的余子陣其為n-1階方陣。hik為Hj的元素其表示車(chē)輛從Ai到Ak的一步轉(zhuǎn)移概率這里i，k均不等于j。將Hj做m次連乘便得到車(chē)輛在除Aj之外的其他區(qū)域中運(yùn)動(dòng)的m步概率轉(zhuǎn)移矩陣H（m）j。

其中hi（km）為車(chē)輛從Ai經(jīng)m步到Ak且未經(jīng)過(guò)Aj概率。

2.3.3 延時(shí)t的分布函數(shù)

若相鄰快照間隔時(shí)間為T(mén)車(chē)O的單步副本發(fā)送數(shù)為N。以下定理給出了將I從Ai傳送到Aj的通信延時(shí)t的分布函數(shù)及期望。

定理1 消息從Ai中的車(chē)O經(jīng)UVDN傳送到Aj的通信延時(shí)t的分布函數(shù)為

證明若車(chē)O在第n1步（1≤n1＜m）造訪分區(qū)Ak根據(jù)第三條假設(shè)其在Ak中逗留了T并感染Ak中的N個(gè)轉(zhuǎn)呈節(jié)點(diǎn)。則PO不經(jīng)Aj在第n1步到達(dá)Ak第n1步感染的N輛車(chē)都未能在（mn1）步內(nèi)到達(dá)Aj

PO不經(jīng)Aj在第n1步到達(dá)Ak第n1步感染的N輛車(chē)都未能在（mn1）步內(nèi)到達(dá)Aj｜O在前n1-1步未到過(guò)Aj

令qi（jn1，m）=PO在前n1步內(nèi)未到達(dá)Aj且其第n1步感染的車(chē)輛均未能在（m-n1）步內(nèi)到達(dá)分區(qū)Aj｜O在前n1-1步未到過(guò)Aj

那么

由以上分析我們可給出通信延時(shí)t的分布函數(shù)

F（t≤mT）

=P消息I在mT之前可由Ai的車(chē)O傳遞到Aj

=1-P源頭節(jié)點(diǎn)和轉(zhuǎn)呈節(jié)點(diǎn)都未能在mT之前到達(dá)Aj

=1-P車(chē)O在mT之前未到達(dá)Aj并且沒(méi)有轉(zhuǎn)呈節(jié)點(diǎn)在mT之前到達(dá)Aj

P車(chē)O在mT之前未到達(dá)Aj并且沒(méi)有轉(zhuǎn)呈節(jié)點(diǎn)在mT之前到達(dá)Aj

證明由分布函數(shù)與密度函數(shù)的關(guān)系可得出分區(qū)Ai到分區(qū)Aj的通信延時(shí)t的密度函數(shù)f（t）

再根據(jù)期望的求解方法易得通信延時(shí)t的期望即為公式（8）。

證畢

從定理1的推導(dǎo)可見(jiàn)當(dāng)m取定時(shí)通信延時(shí)t的分布函數(shù)是關(guān)于N的增函數(shù)。這與現(xiàn)實(shí)情況是符合的發(fā)送出的副本越多規(guī)定時(shí)間內(nèi)到達(dá)目標(biāo)分區(qū)的概率就越大。

3 MDM的模型驗(yàn)證與評(píng)估

本章的仿真數(shù)據(jù)集為北京市出租車(chē)軌跡數(shù)據(jù)集。該數(shù)據(jù)集中的約10000輛出租車(chē)均配備有GPS接收器及GPRS無(wú)線通信設(shè)備。我們選擇的地理通信的仿真區(qū)域是位于北京市地理中心東北部的一長(zhǎng)方形區(qū)域。其東西長(zhǎng)3.9km南北長(zhǎng)4.5km總面積約為17.5km2。以下我們稱(chēng)該區(qū)域?yàn)閰^(qū)域S。

我們將在區(qū)域S上實(shí)施MCMS再利用MDM及北京市出租車(chē)在2010年6月15日的軌跡數(shù)據(jù)給出S中分區(qū)對(duì)間的通信延時(shí)累積分布函數(shù)。之后我們將MDM得到的理論結(jié)果與實(shí)際的仿真結(jié)果進(jìn)行了比較兩者達(dá)到了較高的吻合度。

由于時(shí)間對(duì)城市車(chē)輛出行有重大影響對(duì)于一周中的工作日和節(jié)假日或一天中的早晚高峰和其他時(shí)段車(chē)輛的出行數(shù)目和熱點(diǎn)地區(qū)等都會(huì)呈現(xiàn)出明顯的差別。本文將軌跡數(shù)據(jù)集按時(shí)間劃分利用出行規(guī)律較為穩(wěn)定的時(shí)段進(jìn)行延時(shí)的分析及仿真。我們選擇的仿真時(shí)間為一工作日2010年6月15日早高峰時(shí)段的4個(gè)小時(shí)早6:30至10:30共計(jì)為14400s。

3.1 地理分區(qū)

利用MCMS得到的城市地理分區(qū)是MDM的基礎(chǔ)結(jié)構(gòu)。如圖3所示我們以干路片段為中心對(duì)區(qū)域S進(jìn)行劃分得到32個(gè)分區(qū)各分區(qū)均包含錯(cuò)綜復(fù)雜的支路。將除S外的北京市區(qū)域定義為黑洞區(qū)。在分區(qū)的基礎(chǔ)上將6月15日早高峰時(shí)段4個(gè)小時(shí)的車(chē)輛軌跡數(shù)據(jù)以15s為間隔獲取地圖快照并利用2.2節(jié)中介紹的統(tǒng)計(jì)方法計(jì)算分區(qū)間的一步轉(zhuǎn)移概率矩陣P。設(shè)置消息生命時(shí)長(zhǎng)TTLTimetoLive為1500s。根據(jù)我們之前的工作[16]可知1500s內(nèi)北京市出租車(chē)數(shù)據(jù)集在“兩跳”轉(zhuǎn)發(fā)模式下每15s的平均副本發(fā)送數(shù)目N約為0.05因此我們將理論模

2.3.1 首達(dá)概率

在2.2中我們給出了車(chē)輛在兩分區(qū)間的一步轉(zhuǎn)移概率的求解公式。根據(jù)公式（2）可以得到任意兩分區(qū)間的一步轉(zhuǎn)移概率。記P為該馬爾科夫鏈的一步轉(zhuǎn)移概率矩陣。型中的單步副本發(fā)送數(shù)N定為0.05。

利用P和N得到任意分區(qū)對(duì)的理論延時(shí)分布函數(shù)。

圖3 區(qū)域S的分區(qū)結(jié)果示意圖

接下來(lái)我們將在此32個(gè)分區(qū)中選擇分區(qū)對(duì)地理通信延時(shí)的MDM結(jié)果及仿真結(jié)果進(jìn)行比較。

3.3 仿真校驗(yàn)

本節(jié)我們選取了不同類(lèi)型的分區(qū)對(duì)來(lái)對(duì)通信延時(shí)理論分布函數(shù)進(jìn)行校驗(yàn)。以11區(qū)為消息源分區(qū)再分別選擇2區(qū)邊鄰區(qū)、3區(qū)頂點(diǎn)臨區(qū)和1區(qū)非臨區(qū)作為目標(biāo)分區(qū)見(jiàn)圖4。得到的理論結(jié)果和實(shí)際仿真結(jié)果如下。

圖4 仿真實(shí)驗(yàn)的分區(qū)示意圖

圖5表明了UVDN中11區(qū)到2區(qū)0時(shí)刻車(chē)O位于11區(qū)通信終點(diǎn)為2區(qū)的通信延時(shí)的理論分布曲線與實(shí)際仿真結(jié)果的對(duì)比。11區(qū)與2區(qū)是一邊相臨的分區(qū)。圖中綠色曲線代表通過(guò)MDM得出的延時(shí)理論分布曲線紅色曲線代表通過(guò)實(shí)際數(shù)據(jù)仿真得到的延時(shí)分布曲線。從圖中我們可以看出理論分布結(jié)果在變化趨勢(shì)和準(zhǔn)確度上與仿真結(jié)果都吻合的比較好。例如在1500s之內(nèi)消息可以成功傳達(dá)到2區(qū)的理論概率值為0.32實(shí)際的概率值為0.34只相差0.02。且從整體觀察兩條曲線的最大值差約850s處也只有約0.07。11區(qū)到2區(qū)的實(shí)際延時(shí)分布略高于理論分布。分析其原因可能是11區(qū)到2區(qū)的距離較近其單步平均副本發(fā)送數(shù)N大于全網(wǎng)平均值0.05。

圖5 11-2 MDM的延時(shí)分布與仿真結(jié)果對(duì)比圖

圖6表明了UVDN中11區(qū)到其頂點(diǎn)臨區(qū)3區(qū)的通信延時(shí)的理論分布曲線與實(shí)際仿真結(jié)果的對(duì)比。綠色及紅色曲線分別表示理論和實(shí)際的延時(shí)分布。從圖中不難看出延時(shí)理論分布曲線與實(shí)際分布曲線不僅在變化趨勢(shì)上高度一致且具有多處交點(diǎn)在準(zhǔn)確性上的吻合度也很高。例如在1500s之內(nèi)消息可以成功傳達(dá)到3區(qū)的理論與實(shí)際概率值均為0.315。而從整體觀察兩條曲線的最大值差約300s處也不超過(guò)0.025。

圖7表明了UVDN中11區(qū)到其非臨區(qū)1區(qū)的通信延時(shí)的理論分布曲線與實(shí)際仿真結(jié)果的對(duì)比。從圖中可見(jiàn)延時(shí)理論分布曲線與實(shí)際分布曲線在1200s之前吻合度比較高但在1200s之后吻合度有所降低。而兩條曲線的最大值差也出現(xiàn)在1450s附近約為0.05。以非臨區(qū)為終點(diǎn)的延時(shí)理論分略高于實(shí)際分布這是由于分區(qū)距離增大會(huì)導(dǎo)致的延時(shí)普遍增大而單步副本發(fā)送數(shù)N會(huì)隨著延時(shí)的增大而變小延時(shí)越長(zhǎng)車(chē)O在每15s內(nèi)遇到的未帶副本的車(chē)輛數(shù)目越小。也就是說(shuō)11區(qū)到1區(qū)的單步副本發(fā)送數(shù)N小于0.05。這也可以解釋在1200s之后理論分布與實(shí)際分布的差值有明顯的增大。

圖6 11-3 MDM的延時(shí)分布與仿真結(jié)果對(duì)比圖

通過(guò)與三對(duì)分區(qū)仿真結(jié)果的對(duì)比可以看出通過(guò)MDM得到的延時(shí)分布函數(shù)具有較好的準(zhǔn)確性這說(shuō)明MDM能夠?qū)VDN的延時(shí)進(jìn)行準(zhǔn)確的分析和預(yù)測(cè)。

圖7 MDM的延時(shí)分布與仿真結(jié)果對(duì)比圖

4 總結(jié)與展望

本文建立了在多副本傳送條件下以地理位置為通信終點(diǎn)的UVDN的延時(shí)分析模型MDM。其通過(guò)新的分區(qū)方法MCMS將城市地理信息簡(jiǎn)化為地理連續(xù)的分區(qū)這使得城市中的任意地點(diǎn)均可作為UVDN的通信終點(diǎn)。在所得分區(qū)上利用馬爾科夫鏈來(lái)刻畫(huà)城市車(chē)流在短時(shí)間內(nèi)的位置變化規(guī)律并以此為基礎(chǔ)結(jié)合特定轉(zhuǎn)發(fā)模式下的單步副本發(fā)送數(shù)給出以某一分區(qū)為終點(diǎn)的通信延時(shí)的累積分布函數(shù)和期望。MDM定量地描述和分析了兩個(gè)城市地點(diǎn)間消息的傳輸效率。由于城市道路設(shè)計(jì)及車(chē)輛歷史軌跡信息被納入到了建模考慮范圍MDM在城市環(huán)境下具有較好的適應(yīng)性和可操作性。最后仿真驗(yàn)證結(jié)果表明了MDM的正確性。

從仿真驗(yàn)證數(shù)據(jù)可以看出分區(qū)間的距離對(duì)單步副本發(fā)送數(shù)N有一定影響而N正是理論延時(shí)分布的重要參數(shù)。下一步工作將利用節(jié)點(diǎn)相遇頻度分析單步副本發(fā)送數(shù)N得到UVDN在特定轉(zhuǎn)發(fā)模式下單步副本發(fā)送數(shù)對(duì)于延時(shí)的函數(shù)使MDM在精度上得到進(jìn)一步的提高。

5 國(guó)內(nèi)外研究現(xiàn)狀

路由協(xié)議決定了消息在容遲網(wǎng)絡(luò)中的傳遞方式是容遲網(wǎng)絡(luò)的重點(diǎn)研究對(duì)象[6]。對(duì)容遲網(wǎng)絡(luò)在基礎(chǔ)轉(zhuǎn)發(fā)模式下的通信延時(shí)進(jìn)行理論分析對(duì)于路由協(xié)議的改良和優(yōu)化具有十分重要的意義。

目前“兩跳模式”和“傳染病模式”是容遲網(wǎng)絡(luò)最為通用的兩種基礎(chǔ)轉(zhuǎn)發(fā)模式。國(guó)內(nèi)外研究者已提出多種數(shù)學(xué)模型對(duì)基于這兩種轉(zhuǎn)發(fā)模式的通信延時(shí)進(jìn)行理論分析且部分分析結(jié)果已經(jīng)被運(yùn)用到了路由協(xié)議的優(yōu)化方面。[10]和[15]以獲得消息的節(jié)點(diǎn)數(shù)為狀態(tài)建立排隊(duì)論模型并將此模型與移動(dòng)節(jié)點(diǎn)間的相遇強(qiáng)度信息結(jié)合得出了“兩跳模式”和“傳染病模式”下延時(shí)期望的數(shù)學(xué)表達(dá)式。[5]進(jìn)一步地計(jì)算出了此兩種轉(zhuǎn)發(fā)模式下容遲網(wǎng)絡(luò)延時(shí)的分布函數(shù)并以此為基礎(chǔ)分析了移動(dòng)節(jié)點(diǎn)的轉(zhuǎn)發(fā)自由度對(duì)通信延時(shí)的影響。[14]通過(guò)連續(xù)時(shí)間的馬爾科夫鏈模型建立了可以求解延時(shí)分布的微分方程組。這一成果被[12]推廣到總能耗有限制的容遲網(wǎng)絡(luò)情況并得到了基于“兩跳模式”的路由協(xié)議的優(yōu)化策略。這些優(yōu)秀的研究結(jié)果都側(cè)重于移動(dòng)節(jié)點(diǎn)間的通信其理論分析依賴(lài)于移動(dòng)節(jié)點(diǎn)的相遇強(qiáng)度[16-17]并不包含節(jié)點(diǎn)的地理位置信息。

車(chē)載網(wǎng)絡(luò)方面。[13]采用模擬的方法對(duì)比了理論移動(dòng)模型RWP與實(shí)際城市車(chē)輛軌跡在“傳染病模式”下延時(shí)和其他網(wǎng)絡(luò)性能指標(biāo)。從對(duì)比中發(fā)現(xiàn)車(chē)輛的移動(dòng)自由度限制使得城市車(chē)載網(wǎng)絡(luò)在“傳染病模式”下的通信延時(shí)明顯高于RWP且這種轉(zhuǎn)發(fā)模式帶來(lái)的消息副本數(shù)激增會(huì)大大增加網(wǎng)絡(luò)運(yùn)行負(fù)擔(dān)。因此其結(jié)合城市車(chē)輛的地理位置信息針對(duì)緩存有限的情況提出了改進(jìn)的路由協(xié)議。然而其研究的仍是以移動(dòng)節(jié)點(diǎn)作為通信目標(biāo)容遲網(wǎng)絡(luò)且對(duì)延時(shí)的估計(jì)是通過(guò)模擬實(shí)驗(yàn)得出的缺乏理論分析。

[11]和[7]研究了車(chē)載容遲網(wǎng)絡(luò)地理位置間的通信延時(shí)。[7]考慮的是城郊的車(chē)載環(huán)境消息源頭地與消息目的地間僅有一條通路。其研究結(jié)合了車(chē)輛的移動(dòng)信息通過(guò)排隊(duì)論給出了一定車(chē)速范圍內(nèi)通信延時(shí)的分布及期望。[11]則將車(chē)輛的移動(dòng)抽象為以地理位置為狀態(tài)的馬爾科夫鏈以此計(jì)算出得通信延時(shí)的期望。然而這些研究都是基于“地-車(chē)-地”的兩跳轉(zhuǎn)發(fā)模式這種轉(zhuǎn)發(fā)模式不考慮消息在車(chē)輛間的轉(zhuǎn)發(fā)。然而在城市車(chē)載容遲網(wǎng)絡(luò)中車(chē)輛相遇相對(duì)頻繁車(chē)輛間的消息轉(zhuǎn)發(fā)功能是對(duì)間歇性連接的合理利用是不可忽略的轉(zhuǎn)發(fā)模式。

［1］K.Fall.A Delay-Tolerant Network Architecture for Challenged Internets[C].Karlsruhe,Germany:ACM,2003:27-34.

［2］I.Leontiadis and C.Mascolo.GeOpps:Geographical Opportunistic Routing for Vehicular Networks[C].IEEE,2007:1-6.

［3］A.Panagakis,A.Vaios and I.Stavrakakis.Study of two-hop message spreading in DTNs[C].Limassol:IEEE,2007:1-8.

［4］Q.Ye,L.Cheng,M.C.Chuah,B.Davison.Performance comparison of different multicast routing strategies in disruption tolerant networks[J].Computer Communications,Elsevier,2009,32(16):1731-1741.

［5］G.Resta and P.Santi.The Effects of Node Cooperation Level on Routing Performance in Delay Tolerant Networks[C].Rome,Italy:IEEE,2009:1-9.

［6］S.Jain,K.Fall,and R.Patra.Routing in a delay tolerant network[C].Portland,OR,USA:ACM,2004:145-158.

［7］M.J.Khabbaz,W.F.Fawaz and C.M.Assi.Modeling and Delay Analysis of Intermittently Connected Roadside Communication Networks [J].Vehicular Technology,IEEE Transactions,2012,61(6):2698-2706.

［8］E.Kuiper and S.Nadjm-Tehrani.Geographical Routing With Location Service in Intermittently Connected MANETs[J].Vehicular Technology,IEEE Transactions,2011,60(2):592-604.

［9］C.Pei-Chun,W.Jui-Ting,T.Lung-Chih,L.C.Kevin,Mario Gerla,Jerome Haerri.GeoDTN+Nav:a hybrid geographic and DTN routing with navigation assistance in urban vehicular networks[C].Dublin,Ireland:ISVCS,2008.

［10］E.Altman,A.P.Azad,X.Bas,T.Ar and F.De Pellegrini.Combined Optimal Control of Activation and Transmission in Delay-Tolerant Networks[J].Networking,IEEE/ACM Transactions,2013,21(2):482-494.

［11］D.Niyato,W.Ping and J.C.M.Teo.Performance Analysis of the Vehicular Delay Tolerant Network[C].IEEE,2009:1-5.

［12］O.R.Helgason,F.Legendre,V.Lenders,M.May and G.Karlsson.Performance of opportunistic content distribution under different levels of cooperation[C].Lucca,Italy:IEEE,2010:903-910.

［13］H.Hong-Yu,L.Pei-En,L.Minglu,L.Da,L.Xu and S.Wei.Performance Evaluation of SUVnet With Real-Time Traffic Data[J].Vehicular Technology,IEEE Transactions,2007,56(6):3381-3396.

［14］T.Small and Z.J.Haas.The Shared Wireless Infostation Model:A New Ad Hoc Networking Paradigm (or Where There Is a Whale,There Is a Way)[C].Annapolis,MD,USA:ACM,2003:233-244.

［15］R.Groenevelt,G.Koole and P.Nain.Message delay in Manet[C].Banff,AB,Canada:ACM,2005:412-413.

［16］H.Yuting,W.Haiquan,X.Chunhe,L.Weiguo and Y.Ying.On the distribution of inter contact time for DTNs[C].IEEE,2012:152-155.

［17］X.Chunhe,L.Dong,W.Haiquan,L.Min,L.Weifeng.Characterization and Modeling in Large-scale Urban DTNs[C].IEEE,2012:352-359.

［18］Z.Yu,L.Yanchi,Y.Jing,X.Xing.Urban Computing with Taxicabs[C].ACM,2011:89-98.

［19］龔光魯,錢(qián)敏平.應(yīng)用隨機(jī)過(guò)程教程及在算法和智能計(jì)算中的隨機(jī)模型[M].清華大學(xué)出版社,2005.