机会网络中的消息路由算法研究

发布时间：2018-05-19 06:31

本文选题：机会网络 + 路由算法　；参考：《华中师范大学》2014年硕士论文

【摘要】：机会网络(Opportunistic Networks)是一种移动自组网的演化,容忍延迟网络的变型,借助节点移动相遇的机会进行通信,解决了消息在频繁断裂网络中的通信难题。节点移动、网络稀疏、资源受限等多方面原因,造成机会网络中的消息路由面临着巨大挑战——在同一时间段内,源节点和目标节点不处于连通域内而无法保证端到端链路,消息路由延迟更大。因此,机会网络无法直接采纳传统移动自组网的路由模式和算法。本文从机会网络节点的特性出发,对该特殊网络场景的路由算法进行了设计和研究。论文首先对已有的典型路由算法展开了分类与比较研究。国内外关于机会网络的路由问题已进行了大量研究,围绕路由算法的性能、复杂度、有效性和实用性等方面做了深入探讨。代表性的路由算法有：基于泛洪的路由算法,基于定额泛洪的路由算法和基于效用的路由算法。基于泛洪的路由算法以增加消息的副本数为代价提高了传输成功率,减小了传输延迟,但会消耗过多的网络资源。基于定额泛洪的路由算法限制了消息的副本数,以此来降低网络资源的消耗。基于效用的路由算法收集不同类型的网络信息,为每个节点赋值一定的转发效用,通过效用值的比较更好地限制消息的副本数,在保证较高水平的成功传输率的同时,消耗更少的网络资源。研究证明,利用人与人之间的相似性进行消息路由,能够减少副本数量(网络资源消耗),提高消息被转发至目标节点的可能性(成功率)。针对已有典型路由算法未充分考虑到节点间的相似性问题,本文提出了一种基于SimRank的路由算法RBSR。算法充分考虑了节点间存在相似性这一社会关系对路由性能的影响,运用节点之间的结构相似性挑选合适的下一跳转发节点。通过与三种典型的路由算法比较,验证了该算法的有效性。机会网络中消息的传播依靠节点移动过程中形成的相遇机会。节点间的历史相遇信息对未来的链路预测,并将链路预测的结果用于消息路由具有重要价值。本文提出了一类基于节点历史相遇信息的路由算法,将历史相遇信息观察和分析得到的社会关系权重值引入到加权链路预测指标CN、RA、AA中,计算节点间的相遇概率值作为转发消息的效用值,当前携带消息的节点选择与目标节点之间效用值较高的节点作为下一跳转发节点。在ONE平台上与Prophet算法的性能相比,结果表明该类算法在消息的传输成功率、网络开销和传输平均延迟方面有较佳的性能。
[Abstract]:The opportunity network (Opportunistic Networks) is a kind of mobile ad hoc network evolution, tolerates the variant of the delayed network, and communicates with the opportunity of moving the meeting with the node. It solves the communication problem in the frequent broken network. The nodes move, the network is sparse, the resource is limited and so on, which causes the message routing in the opportunity network to face. In the same time period, the source node and the target node are not in the connected domain and can not guarantee the end to end link, and the message routing delay is greater. Therefore, the opportunity network can not directly adopt the routing mode and algorithm of the traditional mobile ad hoc network. The routing algorithm is designed and studied.
In this paper, the existing typical routing algorithms are classified and compared. A lot of research on the routing problem of opportunity networks at home and abroad has been carried out, and the performance, complexity, effectiveness and practicability of routing algorithms are discussed. The representative routing algorithms are based on flood routing algorithm, based on the quota. Flood routing algorithm and utility based routing algorithm. Flood based routing algorithm increases the transmission success rate at the cost of increasing the number of messages, reduces transmission delay, but consumes too much network resources. Based on the fixed flood routing algorithm, the number of messages is limited to reduce the consumption of network resources. The utility based routing algorithm collects different types of network information, assigns a certain forwarding utility for each node, and better limits the number of copies of the message through the comparison of utility values. It consumes less network resources while ensuring a higher level of successful transmission.
The research proves that using the similarity between people to route messages can reduce the number of replicas (network resource consumption) and improve the possibility of the message being forwarded to the target node (success rate). In this paper, a SimRank based routing algorithm RBSR is proposed for the existing typical routing algorithms that do not fully consider the similarity between nodes. The algorithm fully considers the influence of the social relationship on routing performance between nodes, and uses the structural similarity between nodes to select the appropriate next hop forwarding node. By comparing with the three typical routing algorithms, the effectiveness of the algorithm is verified.
The communication of messages in the opportunity network depends on the chance of meeting in the process of node movement. The historical encounter information between nodes is expected to predict the future link, and the result of link prediction is of great value to the message routing. The weight value of the social relationship is introduced into the weighted link prediction index CN, RA, AA, the meeting probability value between the nodes is used as the utility value of the forwarding message, and the node that carries the message node selection and the higher value of the utility value between the target nodes is the next hop forwarding node. Compared with the performance of the Prophet algorithm on the ONE platform, the node is compared to the performance of the Prophet algorithm. The results show that the algorithm has better performance in message transmission success rate, network overhead and average transmission delay.
【学位授予单位】：华中师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN929.5

【相似文献】