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

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

0 引言

車載網(wǎng)絡(luò)是智能城市交通系統(tǒng)的通信基礎(chǔ)對(duì)于采集和傳遞交通路況信息、緩解交通擁堵、提高交通運(yùn)輸效率、降低車輛污染等都有重要作用。然而車載網(wǎng)絡(luò)具有節(jié)點(diǎn)移動(dòng)自主性強(qiáng)、移動(dòng)速度快、分布不均勻、拓?fù)渥兓l繁等特點(diǎn)。這使得現(xiàn)有的移動(dòng)車載網(wǎng)絡(luò)通信技術(shù)還難以滿足智能交通等應(yīng)用的通信需求。究其根本原因在于底層通信的間歇性鏈路與上層通信的持續(xù)性需求之間存在矛盾(使得Internet或Ad Hoc網(wǎng)絡(luò)所采用的傳統(tǒng)通信技術(shù)在車載網(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ù)目的是滿足極端環(huán)境下計(jì)算機(jī)網(wǎng)絡(luò)的數(shù)據(jù)通信需求其主要特點(diǎn)是使用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”(store-carry-forward)[1]的數(shù)據(jù)通信技術(shù)在缺乏底層持續(xù)鏈路的情況下利用被稱為“接觸”Contact的傳輸機(jī)會(huì)以異步的方式來(lái)進(jìn)行逐跳的消息傳遞?？梢钥闯鲆苿?dòng)容遲網(wǎng)絡(luò)技術(shù)能夠?yàn)槌鞘熊囕d網(wǎng)絡(luò)提供更為完善的組網(wǎng)技術(shù)和通信基礎(chǔ)平臺(tái)在提高城市車載網(wǎng)絡(luò)的可達(dá)性、實(shí)時(shí)性和差異容忍性方面具有十分重要的實(shí)用價(jià)值和廣泛的應(yīng)用前景。

基于城市車載環(huán)境的容遲網(wǎng)絡(luò)稱為城市車載容遲網(wǎng)絡(luò)Urban Vehicular Delay-tolerant Network或UVDN。地理通信作為UVDN的一大特色功能主要服務(wù)于對(duì)地理信息敏感的消息。此類消息通常需要被傳送到特定的地理位置其可能是路況信息更新、交通事故提醒、免費(fèi)停車場(chǎng)指引[2]也可能是針對(duì)出租車的客流信息傳達(dá)等。車輛作為UVDN的移動(dòng)節(jié)點(diǎn)同樣采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的模式來(lái)滿足連接稀疏情況下車載網(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)化都是十分必要的。然而城市的車輛數(shù)目龐大車速在地理上的高度不均車輛移動(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]從車載網(wǎng)絡(luò)特征出發(fā)建立模型給出了以特定地理位置作為通信終點(diǎn)的城郊車載容遲網(wǎng)絡(luò)的延時(shí)分析。由于城郊地區(qū)車輛數(shù)目有限道路構(gòu)造簡(jiǎn)單其研究不考慮消息在車輛間的轉(zhuǎn)發(fā)消息只能由車輛攜帶到通信目的地。然而在城市環(huán)境下車輛數(shù)目龐大且車輛間的接觸頻繁為提高通信效率車輛間的消息轉(zhuǎn)發(fā)功能是不可忽略的。目前面向地理通信且考慮車輛間轉(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)的車輛均配備有在一定范圍可以通信的路由設(shè)備此設(shè)備能夠存儲(chǔ)攜帶和轉(zhuǎn)發(fā)消息這使得消息在UVDN中可以以多副本形式傳遞。由于UVDN中的車輛行駛受到復(fù)雜的道路布局限制我們將從簡(jiǎn)化城市地理信息和抽象車輛移動(dòng)模式兩方面入手對(duì)UVDN的通信延時(shí)建模。地理劃分是簡(jiǎn)化城市地理信息的有力手段我們根據(jù)城市道路布局提出了干路中心法Major-road Centered Map Segmentation,MCMS將城市分割為以主干路片段為中心的分區(qū)。城市中的每一個(gè)地理位置屬于且僅可能屬于某一個(gè)分區(qū)。車輛移動(dòng)模式方面在城市分區(qū)的基礎(chǔ)上我們建立了一個(gè)UVDN的延時(shí)分析模型MDM(MCMS-based Delay Model)其中我們假設(shè)車輛在短時(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ā)模式下只有消息原本的攜帶車輛有轉(zhuǎn)發(fā)權(quán)利攜帶消息副本的車輛無(wú)權(quán)利再將消息內(nèi)容轉(zhuǎn)發(fā)給其他車輛。

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

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

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

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

本文的結(jié)構(gòu)安排如下。第一章和第二章將分別詳細(xì)介紹干路中心法MCMS及基于該劃分方法的UVDN延時(shí)分析模型MDM通過(guò)MDM可以得到通信延時(shí)的分布函數(shù)表達(dá)式。在第三章中我們利用北京市出租車軌跡數(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ò)和車載網(wǎng)絡(luò)的研究成果。

1 MCMS干路中心法

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

地理劃分的最簡(jiǎn)單辦法是將整片區(qū)域按經(jīng)緯度均勻劃分。但這種方法沒(méi)有考慮到城市道路布局以及道路對(duì)車輛行駛的限制。在[18]中作者認(rèn)為城市道路可以分為干路和支路。與支路比較干路單位時(shí)間內(nèi)的車流量較大設(shè)計(jì)較寬且布局相對(duì)簡(jiǎn)單明了。因此其提出一種以干路布局作為依據(jù)的城市地理劃分法將干路圍成的最小區(qū)域作為分區(qū)如圖1所示。圖中黑色直線代表城市干路紅色及藍(lán)色線段圍成的區(qū)域?yàn)樗玫姆謪^(qū)。然而此方法得到的分區(qū)在UVDN中暴露出不適應(yīng)性。車流量較大的干路是車輛間通信的主要場(chǎng)所這種方法可能將一條干路上的車輛分隔到兩個(gè)分區(qū)中 這使得車輛定位的復(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將車輛與車輛接觸頻繁的地區(qū)劃為分區(qū)這使得車輛的跟蹤更加準(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ò)車輛在短時(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)由城市車輛集構(gòu)成。車輛可以行駛在城市內(nèi)部的任意道路上并均配有可以攜帶和轉(zhuǎn)發(fā)消息的路由設(shè)備。

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

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

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

2.1.1 符號(hào)

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

2.1.2 假設(shè)

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

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

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

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

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

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

根據(jù)2.1.2中的第二條假設(shè)一輛車的軌跡可視為一個(gè)馬爾科夫過(guò)程此馬爾科夫鏈的節(jié)點(diǎn)為城市中的各分區(qū)。那么如何得到此馬爾科夫鏈的一步轉(zhuǎn)移概率矩陣呢本節(jié)我們將介紹如何采用統(tǒng)計(jì)的方法從車輛的實(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è)車輛所在的分區(qū)共統(tǒng)計(jì)k個(gè)時(shí)刻。記Ai（j）為在第j個(gè)時(shí)刻造訪若一輛車某一跳的起始分區(qū)為Ak1終止分區(qū)為Ak2則其一步內(nèi)在兩分分區(qū)Ai的車輛集。將這n個(gè)分區(qū)在k個(gè)時(shí)刻的所有車輛集寫成一個(gè)矩陣形式處理得到。記｜Ai（m）｜為m時(shí)刻Ai中的造訪車輛數(shù)目而｜為在m時(shí)刻造訪Ai且在m+1時(shí)刻造訪Aj的車輛的數(shù)目。｜也就

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明若車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輛車都未能在（mn1）步內(nèi)到達(dá)Aj

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

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

那么

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

F（t≤mT）

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

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

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

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

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

由于時(shí)間對(duì)城市車輛出行有重大影響對(duì)于一周中的工作日和節(jié)假日或一天中的早晚高峰和其他時(shí)段車輛的出行數(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í)的車輛軌跡數(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)北京市出租車數(shù)據(jù)集在“兩跳”轉(zhuǎn)發(fā)模式下每15s的平均副本發(fā)送數(shù)目N約為0.05因此我們將理論模

2.3.1 首達(dá)概率

在2.2中我們給出了車輛在兩分區(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é)我們選取了不同類型的分區(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í)刻車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)車O在每15s內(nèi)遇到的未帶副本的車輛數(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)刻畫城市車流在短時(shí)間內(nèi)的位置變化規(guī)律并以此為基礎(chǔ)結(jié)合特定轉(zhuǎn)發(fā)模式下的單步副本發(fā)送數(shù)給出以某一分區(qū)為終點(diǎn)的通信延時(shí)的累積分布函數(shù)和期望。MDM定量地描述和分析了兩個(gè)城市地點(diǎn)間消息的傳輸效率。由于城市道路設(shè)計(jì)及車輛歷史軌跡信息被納入到了建模考慮范圍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)間的通信其理論分析依賴于移動(dòng)節(jié)點(diǎn)的相遇強(qiáng)度[16-17]并不包含節(jié)點(diǎn)的地理位置信息。

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

[11]和[7]研究了車載容遲網(wǎng)絡(luò)地理位置間的通信延時(shí)。[7]考慮的是城郊的車載環(huán)境消息源頭地與消息目的地間僅有一條通路。其研究結(jié)合了車輛的移動(dòng)信息通過(guò)排隊(duì)論給出了一定車速范圍內(nèi)通信延時(shí)的分布及期望。[11]則將車輛的移動(dòng)抽象為以地理位置為狀態(tài)的馬爾科夫鏈以此計(jì)算出得通信延時(shí)的期望。然而這些研究都是基于“地-車-地”的兩跳轉(zhuǎn)發(fā)模式這種轉(zhuǎn)發(fā)模式不考慮消息在車輛間的轉(zhuǎn)發(fā)。然而在城市車載容遲網(wǎng)絡(luò)中車輛相遇相對(duì)頻繁車輛間的消息轉(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］龔光魯,錢敏平.應(yīng)用隨機(jī)過(guò)程教程及在算法和智能計(jì)算中的隨機(jī)模型[M].清華大學(xué)出版社,2005.