MDM:一种城市车载容迟网络的延时分析模型
开篇：润墨网以专业的文秘视角，为您筛选了一篇MDM:一种城市车载容迟网络的延时分析模型范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘 要】城市车载容迟网络（Urban Vehicular Delay-tolerant Network（UVDN（作为容迟网络的重要应用已逐渐成为移动通信领域的研究热点。然而（由于城市地理信息复杂（车辆行驶轨迹多变（从理论上对UVDN的通信延时进行分析具有较大的难度。本文首先提出了基于干路分布的城市区域划分方法-MCMS（Major-road Centered Map Segmentation（（将城市划分为毗邻的分区以简化城市地理信息。在此基础上（针对车辆移动模式（本文提出了UVDN的延时分析模型-mdm（MCMS-based Delay Model for UVDN（。该模型以城市分区为状态（利用马尔科夫链来刻画UVDN的车辆移动模式及相遇规律（并利用这些特性从理论上推导出UVDN端到端通信延时的累积分布函数。最后（在大规模真实数据集上的仿真实验表明（本文提出的MDM模型能够对UVDN的通信延时进行准确的分析和预测。
【关键词】容迟网络；城市车载网络；延时分析；马尔科夫链
【Abstract】As a significant application of Delay Tolerant Network， Urban Vehicular Delay-tolerant Network （UVDN） is paid much attention in mobile communication. However， due to the complexity of geographic information and vehicular trajectory， delay analysis of UVDN is challenged theoretically. In order to simplify the geographic information， this paper firstly suggests an approach of map segmentation called MCMS （Major-road Centered Map Segmentation） to partition a city into adjacent regions. Then， based on these regions， a delay analysis model MDM （MCMS-based Delay Model） is proposed for UVDN. MDM employs a Markov chain to depict inherent characteristics of vehicular network in terms of mobility patterns and encounters， which are exploited to derive the CDF of end-to-end delays. Finally， through extensive simulations under real vehicular trajectories， MDM exhibits good performance in UVDN delay analysis and prediction.
【Key words】Delay tolerant network（DTN）；Urban vehicular network；Delay analysis；Markov chain
0 引言
车载网络是智能城市交通系统的通信基础对于采集和传递交通路况信息、缓解交通拥堵、提高交通运输效率、降低车辆污染等都有重要作用。然而车载网络具有节点移动自主性强、移动速度快、分布不均匀、拓扑变化频繁等特点。这使得现有的移动车载网络通信技术还难以满足智能交通等应用的通信需求。究其根本原因在于底层通信的间歇性链路与上层通信的持续性需求之间存在矛盾（使得Internet或Ad Hoc网络所采用的传统通信技术在车载网络组网实践中面临着巨大的挑战。
许多研究者正试图利用移动容迟网络Delay Tolerant NetworkDTN技术来解决这一矛盾。移动容迟网络是随着无线通信与计算机网络发展而出现的一种新兴技术目的是满足极端环境下计算机网络的数据通信需求其主要特点是使用“存储-携带-转发”（store-carry-forward）[1]的数据通信技术在缺乏底层持续链路的情况下利用被称为“接触”Contact的传输机会以异步的方式来进行逐跳的消息传递。可以看出移动容迟网络技术能够为城市车载网络提供更为完善的组网技术和通信基础平台在提高城市车载网络的可达性、实时性和差异容忍性方面具有十分重要的实用价值和广泛的应用前景。
基于城市车载环境的容迟网络称为城市车载容迟网络Urban Vehicular Delay-tolerant Network或UVDN。地理通信作为UVDN的一大特色功能主要服务于对地理信息敏感的消息。此类消息通常需要被传送到特定的地理位置其可能是路况信息更新、交通事故提醒、免费停车场指引[2]也可能是针对出租车的客流信息传达等。车辆作为UVDN的移动节点同样采用“存储-携带-转发”的模式来满足连接稀疏情况下车载网络的数据通信需求。虽然UVDN以通信效率为代价获得通信的可行性但在实际应用中消息是普遍具有时效性的也就是说一个消息可能只在其产生后的某一段时间内是有价值的。因此UVDN的通信延时分析对路由的设计及网络协议的优化都是十分必要的。然而城市的车辆数目庞大车速在地理上的高度不均车辆移动严格受到道路约束等等因素使得UVDN的延时分析方法在设计上存在挑战。
由于UVDN是容迟网络的特殊应用范例我们希望能从一般容迟网络的延时研究中获得启发。遗憾的是虽然针对一般容迟网络的延时研究已经取得了优秀的成果[3-5]但因为一般容迟网络中节点移动自由度大且缺乏节点定位信息这些成果难以被推广到UVDN的延时分析。部分研究学者[6-7]从车载网络特征出发建立模型给出了以特定地理位置作为通信终点的城郊车载容迟网络的延时分析。由于城郊地区车辆数目有限道路构造简单其研究不考虑消息在车辆间的转发消息只能由车辆携带到通信目的地。然而在城市环境下车辆数目庞大且车辆间的接触频繁为提高通信效率车辆间的消息转发功能是不可忽略的。目前面向地理通信且考虑车辆间转发的UVDN的研究多注重于单副本条件下的路由协议设计[2，8-9]对于多副本条件下的延时等网络性能的理论分析还很缺乏。
2.1.1 符号
通过车辆的实际移动轨迹数据可以得到一组等时间间隔的地图快照。设{X0，X1，X2，…，Xn，…}为地图快照中记录下的某一车辆的轨迹其中Xk（k∈N+）为k时刻该车所在的分区编号。T为车辆轨迹中相邻时刻的时间间隔其也是两个相邻快照间的时长。车辆的行驶轨迹在地理上是连续的为体现这一客观事实间隔时间T的取值不宜过大应尽量使车辆在相邻时刻的快照中处于地理上相邻或相同的分区。记N为车O在T内转发出的消息副本数即单步副本发送数此参数与实际的车载环境密切相关。
2.1.2 假设
我们提出以下三条假设来描述车辆在分区间的位置移动模式。
车辆的移动是彼此间相互独立的一辆车的移动并不受其他车辆移动的干扰。
一辆车在下一时刻所处的分区只与当前时刻所在的分区有关。在城市环境下车辆数目庞大结队出行比例较小。因此车辆的移动可以看作是相互独立的第一条假设是对实际车载环境的合理简化。
城市车辆总体的出行分布受城市人口出行需求的支配具有一定宏观的规律。在车辆数目较大的情况下一个分区的车辆集在短时间内的位置移动分布与车辆个体的历史轨迹并无很强的关联性而与该分区的车辆流动规律有关。并且在UVDN中车O对于转呈节点的选择无个体偏好性。因此将UVDN中的车辆移动简化为马尔科夫过程是具有宏观意义的。
对于第三条假设当T较小时车辆在每一跳的起始和终止分区逗留的时间可看作是相同的。
2.2 一步转移概率矩阵
根据2.1.2中的第二条假设一辆车的轨迹可视为一个马尔科夫过程此马尔科夫链的节点为城市中的各分区。那么如何得到此马尔科夫链的一步转移概率矩阵呢本节我们将介绍如何采用统计的方法从车辆的实际轨迹数据集中得出一步转移概率矩阵。
现有通过MCMS得到的n个分区分别标记为A1，A2，…，An其中An为黑洞区。每隔T拍下一个地图快照该快照上记录了此时刻网络中各个车辆所在的分区共统计k个时刻。
公式（2）表明pij是一步由Ai到Aj的总转移车次数占Ai的总到访车次数的比例。这里需注意只要一辆车在一个快照中的地理位置属于Ai就称该车造访Ai一次。而该车位于Ai的快照个数即为该车造访Ai的次数。公式（2）中总转移车次数与总到访车次数的比值是车辆在k个时刻由Ai到Aj的平均一步转移概率。2.3 消息在分区间传递的效率
一步转移概率矩阵是马尔科夫链的核心要素。接下来将介绍MDM如何利用马尔科夫链理论得到通信延时的分布函数。
2.3.1 首达概率
在2.2中我们给出了车辆在两分区间的一步转移概率的求解公式。根据公式（2）可以得到任意两分区间的一步转移概率。记P为该马尔科夫链的一步转移概率矩阵。
从定理1的推导可见当m取定时通信延时t的分布函数是关于N的增函数。这与现实情况是符合的发送出的副本越多规定时间内到达目标分区的概率就越大。
3 MDM的模型验证与评估
本章的仿真数据集为北京市出租车轨迹数据集。该数据集中的约10000辆出租车均配备有GPS接收器及GPRS无线通信设备。我们选择的地理通信的仿真区域是位于北京市地理中心东北部的一长方形区域。其东西长3.9km南北长4.5km总面积约为17.5km2。以下我们称该区域为区域S。
我们将在区域S上实施MCMS再利用MDM及北京市出租车在2010年6月15日的轨迹数据给出S中分区对间的通信延时累积分布函数。之后我们将MDM得到的理论结果与实际的仿真结果进行了比较两者达到了较高的吻合度。
由于时间对城市车辆出行有重大影响对于一周中的工作日和节假日或一天中的早晚高峰和其他时段车辆的出行数目和热点地区等都会呈现出明显的差别。本文将轨迹数据集按时间划分利用出行规律较为稳定的时段进行延时的分析及仿真。我们选择的仿真时间为一工作日2010年6月15日早高峰时段的4个小时早6：30至10：30共计为14400s。
3.1 地理分区
利用MCMS得到的城市地理分区是MDM的基础结构。如图3所示我们以干路片段为中心对区域S进行划分得到32个分区各分区均包含错综复杂的支路。将除S外的北京市区域定义为黑洞区。在分区的基础上将6月15日早高峰时段4个小时的车辆轨迹数据以15s为间隔获取地图快照并利用2.2节中介绍的统计方法计算分区间的一步转移概率矩阵P。设置消息生命时长TTLTime to Live为1500s。根据我们之前的工作[16]可知1500s内北京市出租车数据集在“两跳”转发模式下每15s的平均副本发送数目N约为0.05因此我们将理论模型中的单步副本发送数N定为0.05。
利用P和N得到任意分区对的理论延时分布函数。
接下来我们将在此32个分区中选择分区对地理通信延时的MDM结果及仿真结果进行比较。
3.3 仿真校验
本节我们选取了不同类型的分区对来对通信延时理论分布函数进行校验。以11区为消息源分区再分别选择2区边邻区、3区顶点临区和1区非临区作为目标分区见图4。得到的理论结果和实际仿真结果如下。
图5表明了UVDN中11区到2区0时刻车O位于11区通信终点为2区的通信延时的理论分布曲线与实际仿真结果的对比。11区与2区是一边相临的分区。图中绿色曲线代表通过MDM得出的延时理论分布曲线红色曲线代表通过实际数据仿真得到的延时分布曲线。从图中我们可以看出理论分布结果在变化趋势和准确度上与仿真结果都吻合的比较好。例如在1500s之内消息可以成功传达到2区的理论概率值为0.32实际的概率值为0.34只相差0.02。且从整体观察两条曲线的最大值差约850s处也只有约0.07。11区到2区的实际延时分布略高于理论分布。分析其原因可能是11区到2区的距离较近其单步平均副本发送数N大于全网平均值0.05。
[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]龚光鲁，钱敏平.应用随机过程教程及在算法和智能计算中的随机模型[M]. 清华大学出版社，2005.