A Study On Routing Algorithms For Opportunistic Networks Based On Repeated Game

Opportunistic Networks are a kind of delay and division tolerable wireless self-organized networks, and don't require a complete path existing between source node and destination node, utilizing communication opportunities obtained from node movement to forward packets. Because it can communicate in a relatively harsh environment, so Opportunistic Networks have been widely using in vehicular communication, space communication and networking, environment monitoring and other fields. The routing of Opportunistic Networks mainly depends on the collaboration between mobile nodes, and carries out by “story-carry-forward” manner.At present, the studies on Opportunistic Networks are mainly based on the assumption that nodes have good collaboration, and they can help other nodes in the networks relay messages unconditionally. However, nodes would behavior selfishly because of the constrained resources in real application scenarios, and they refuse to supply routing and message forwarding services for other nodes freely. This kind of selfish behavior causes traditional Opportunistic Networks routing mechanism can't work properly, which degrades network performance. Therefore, the core of this paper is to design a reliable routing algorithm in which includes selfish node detection algorithm to detect selfish nodes accurately and make node avoid selfish nodes during the process of their routing selection to promote messages forwarded to their destination nodes successfully; and design reasonable punishment and incentive mechanisms to boost nodes participate in messages forwarding courses positively.Firstly, this paper introduces the background about the subject briefly, the basic concept of Opportunistic Networks, forwarding principle as well as its feature and analyses nodes' selfish behavior. Classify the existing selfish node detection algorithms for Opportunistic Networks with selfish nodes and Opportunistic Networks routing algorithms based on Repeated Game, and take some of classical algorithms to summarize in detail.Secondly, to address the problems existing in the present routing algorithms of Opportunistic Networks, such as packets collision, the intermediate node beyond node's communication range causing detection inaccuracy and credit value threshold can't set precise, leading to low throughput and high control overhead, RRA-ONSN was proposed. RRA-ONSN includes RSND algorithm for Opportunistic Networks we proposed. By employing wrong frame analysis, judgment of separation, probability qualitative and expand auditing four new mechanisms, RSND algorithm eliminates the influence to nodes' selfishness detection due to packets collision and the intermediate node beyond node's communication range, and avoid the difficulty in node credit value threshold setting. RRA-ONSN proposed can improve the accuracy of sefish node detection, network throughput and degrade control overhead.Thirdly, to address the problems existing in the routing algorithm based on Reputation about poor incentive effects and the routing algorithm based on Game Theory about single penalty can't form sufficient deterrent to selfish nodes, this thesis proposes a Repeated Game-based and High-throughput Routing(RGHR) algorithm for Opportunistic Networks. By establishing repeated game model, designing reasonable punishment and incentive mechanism to force selfish nodes to change their strategies during the game, and promote nodes participate in packets forwarding courses positively, which will improve message interaction rate, throughput and degrade message transmission delay.Finally, we give a summary of this thesis, outlook the future of selfish node detection algorithm in Opportunist Networks with selfish nodes and Opportunist Networks routing algorithm based on Repeated Game, and give the directions of the next step of research work.