【作者】 刘杰彦；

【导师】 曾家智；

【作者基本信息】 电子科技大学 ， 计算机系统结构， 2012， 博士

【摘要】 近年来，大量无线智能设备的涌现迅速推动了无线自组织网络在各个领域的应用，但在很多应用场景中，由于节点移动、节点稀疏分布、节点通信范围有限等各种原因造成节点间连接经常断开，网络常常被分割成很多不连通的子区域，源节点和目的节点之间不再存在完整的、稳定的端到端路径，数据传输往往要经历较长的延迟，这类网络被称为延迟容忍网络DTN(Delay Tolerant Network)。路由问题是DTN研究的重点问题，面对DTN节点间连接频繁断开、网络常常被分割这些特性，传统移动自组织网络MANET(Mobile Ad Hoc Network)中的路由技术不再适用，DTN间歇连通的网络环境对路由技术提出了更大的挑战。DTN的应用场景很广泛，本文针对DTN的两种具体应用场景——移动传感器网络MSN(Mobile Sensor Network)和具有社会网络特征的DTN，在系统分析现有研究的基础上，深入细致地研究了这两种网络场景中的路由问题，取得了若干创新性成果，本文的主要贡献包括：1.针对MSN路由的主要目标，即在动态变化的网络环境中如何将消息有效的传递到汇聚点，提出了基于节点位置预测的路由协议LPR(Location Prediction basedRouting)，节点与汇聚点的相对距离可用来衡量节点与汇聚点成功通信的可能性，目前很多研究仅基于节点历史上与汇聚点的相对距离来进行路由决策，这种方式对节点未来的移动趋势缺乏考虑，与这些研究不同，LPR根据节点历史上的移动轨迹，基于多重马尔可夫链来对节点未来短期内的位置进行预测，并以预测结果作为路由决策的依据。为优化消息副本管理，LPR基于节点与汇聚点成功通信的可能性来给节点分配消息复制任务，同时引入有效的队列管理机制以降低消息副本冗余并改善传输效率。实验结果表明，与现有的相关协议相比，LPR更好地实现了消息传输成功率和传输能耗、传输延迟之间的平衡。2.根据节点间的接触情况，提出了结合节点传输概率和节点活跃性的路由协议DPAR(Delivery Probability andActivity based Routing)，该协议以传输概率来衡量传感器节点与汇聚点成功通信的可能性，在决定节点的传输概率时，DPAR综合考虑了节点间的直接接触和间接接触，并以节点间接触时长作为计算节点传输概率的主要依据，通过逐跳将消息转发给传输概率更高的节点来将消息传递给汇聚点。在节点稀疏分布的网络环境中，受节点活动范围或移动关联性的影响，低传输概率节点可能长时间不能与高传输概率节点相遇，这将影响消息成功递交，为此，DPAR利用活跃节点充当中继来发现高概率节点，有效改善了上述问题。DPAR还基于消息的优先权来对节点消息缓存进行管理，有效降低了消息副本冗余。实验结果表明，与现有的相关路由协议比较，DPAR以较低的传输延迟获得了更高的消息传输成功率。3.针对具有社会网络特征的DTN，鉴于设备的载体即人具有地点访问偏好性是一稳定且普遍存在的特征，提出了基于节点偏好地点的路由协议PLBR(Preference Location based Routing)，该协议基于节点长期的、周期性的地点访问记录来获取节点的偏好地点，并根据节点偏好地点的相似性来衡量节点间的“亲近度”，路由决策基于节点间的“亲近度”而进行。PLBR用MIT Reality项目所提供的真实节点移动模型来进行实验验证，实验结果表明，与相关的路由协议相比，PLBR更好的实现了消息传输成功率和传输能耗、传输延迟之间的平衡。4.在PLBR的基础上进一步提出基于期望最短路径的路由协议ESPR(ExpectedShortest Path based Routing)。PLBR主要考虑了节点间的直接连通性，通过利用与目的节点间存在直接连通机会的节点来完成消息传输，而ESPR在PLBR的基础上进一步利用了节点间可能存在的间接多跳路径。 ESPR首先基于节点间的“亲近度”来获得节点间的直接距离，在此基础上采用Dijkstra算法来计算节点间的期望最短路径，消息传输时选择到达目的节点期望最短路径更短的节点作为下一跳。与PLBR协议相比，ESPR更加充分利用了网络中可能存在的连接机会。基于节点真实移动轨迹的实验结果表明，与相关路由协议以及PLBR相比，ESPR提高了消息传输成功率并降低了传输延迟。更多还原

【Abstract】 In the last decade, wireless ad hoc network were widely applied in many areas dueto the emergence of plenty of intelligent wireless devices. However, in some specificnetworks, intermittent connectivity might arise due to low density, high mobility,limited transmission range and so on. In such kind of networks, it’s hard to find acomplete route from a source to a given destination, and the data delivery may sufferfrom long delay. Accordingly, these networks are defined as Delay Tolerant Networks(DTNs).Due to the incomplete connectivity, routing is an important issue in DTN, and thetraditional routing mechanisms in Mobile Ad Hoc Network (MANET) cannot beadopted directly, thus the key challenge in DTN is to design the efficient routing schemewhich can provide good delivery performance in front of the intermittently connectednetwork topology. This dissertation focuses on the routing strategies of DTN in twoscenarios: the mobile sensor network (MSN) and the DTN with properties of socialnetwork. Based on the comprehensive analysis of the current research, the author makesa thorough study about the routing strategies in those two scenarios. The majorcontributions of this dissertation are elaborated below.1. How to delivery message to the sink node efficiently in the changeableenvironment is the objective of MSN routing. This dissertation proposes a locationprediction based routing protocol (LPR). LPR uses the relative distance between thesensor node and the sink node to evaluate the possibility of delivering message to thesink node. LPR is different from most existing routing protocols which make routingdecisions only according to nodes historical locations, while nodes moving tendency inthe near future are not considered. Comparing with these protocols, LPR makes locationpredictions for nodes based on k-order Markov chain model, and the predicted resultsare further used to provide guidance for route selection. Meanwhile, LPR assigns tasksof message replication to nodes according to their abilities of delivering message to thesink successfully. Moreover, LPR provides an effective buffer management mechanismto decrease the redundant copies as well as improving the delivery performance. Simulation results show that compares to existing DTN routing protocols, LPR achievesbetter tradeoff between the message delivery ratio and the delivery cost/delay.2. According to encounters between nodes, in this dissertation, a deliveryprobability and activity based routing protocol (DPAR) for MSN is proposed. DPARuses the delivery probability to represent the possibility of delivering message to thesink node, which is achieved according to the encounter duration between nodes. Inorder to deliver messages to the sink node successfully, nodes with higher deliveryprobabilities will be selected as next hops. However, in a typical MSN with large scaleand sparsely nodes distribution, when the message custodian with low deliveryprobability moves along the regularly route or in a limited range in most of the time, thedata delivery may be subject to high latency since the custodian will often have to wait along time until it encounters the node with higher delivery probability. In order to solvethis problem, DPAR leverages active nodes as relays. DPAR also employs an effectivebuffer management mechanism to decrease the redundant message copies as well aspromoting the delivery performance. Simulation results show that DPAR achieveshigher delivery ratio with lower delivery delay comparing with existing routingschemes.3. In DTN with properties of social network, portable devices are carried byhuman, this dissertation proposes a preference location based routing scheme (PLBR)based the observation that human have location visiting preferences in their dailymobility traces. PLBR acquires one’s preference locations according to its long-termand periodically location visiting records, and then the degree of closeness of any pairof nodes is measured by the similarity of their preference locations, moreover, thecloseness metric can be used to provide guidance for data forwarding. Simulations arecarried out based on human mobility traces from MIT Reality project, and the resultsshow that PLBR achieves better tradeoff between the data delivery ratio and thedelivery overhead/delay comparing with existing schemes.4. Based on PLBR, an expected shortest path based routing protocol (ESPR) isproposed. PLBR only considers the direct connection between the current node and thedestination, and messages are thereby forwarded to the node which is the one-hopneighbor of the destination. Different with PLBR, ESPR utilizes the indirect multi-hopconnection between the current node and the destination. Specifically, ESPR gets the direct distance between nodes according to their closeness, and then it employs theDijkstra algorithm to calculate the expected shortest path (ESP) from the source to thedestination, furthermore, messages are forwarded to nodes which have shorter ESPsfrom themselves to the destination than the current node. In brief, ESPR makes a betterutilization of the indirect connection chance between nodes than PLBR. Simulations arealso carried out based on human mobility traces from MIT Reality project, and theresults show that ESPR achieves better performance comparing with existing routingprotocols and PLBR in terms of delivery ratio and delay.更多还原