无线Mesh网络中基于循环囚徒困境的路由算法

A routing algorithm for wireless mesh network based on alternating prisoner's dilemma

本文提出了一种针对支持多速率传输的无线Mesh网络中的寻路方法.该方法以博弈论中的循环囚徒困境为理论基础,提出了节点间亲密度的概念,并以此为因子激励节点间的合作.节点是否对路由请求(routing request,RREQ)分组进行转发取决于是否符合自身利益,它们的决策影响到相关节点间的亲密度.最后通过仿真证明了该方法能够有效地改善网络性能.

Wireless Mesh Network（WMN） is a new distributed broadband access network and has become a hot research topic in the next-generation wireless networks.The routing algorithms of WMN are an important problem for WMN is a wireless multi-hops network.In order to meet the performance requirements of multimedia traffic transmission,the routing protocol designed for WMN must be taken into account of the combination of load balance,fault tolerant and throughput,etc.Recently,many standards,such as IEEE 802.11a and 802.11b begin to support multi-rate transmission,and the routing problem of WMN is becoming more and more complex.For WMN is developed from Ad hoc network,the routing algorithms of Ad hoc network can be also used in WMN.Most of traditional routing algorithms of Ad hoc network focus on finding a minimal-hops path.But a min-hops path is usually not an appropriate route in WMN for it does not take the load balance into account.Even if a node is overload,these algorithms insist on routing on it if it is exactly on the min-hops path.In this paper,a novel routing algorithm for multi-rate wireless mesh network is presented.It aims to achieve load balance and support multi-rate effectively.On the one hand,users of networks usually are selfish.They hopes to occupy the transmission channel immediately as soon as they have packets to send.If the transmission begins,they also like to transmit data with the highest rate.Research shows that,if the selfish users account for 10%~40%,the performance of network will decrease to 16%-32%.On the other hand,the traditional routing algorithm,like ad-hoc on-demand distance vector routing（AODV）,force the users cooperate with each other unconditionally.For example,a user must forward a RREQ,except it forwarded the same one.This unconditional cooperation mode will lead to the min-hops path.Alternating prisoner＇s dilemma is a famous problem in game theory.Tit for tat（TFT） strategy is the best solution of this dilemma.TFT always begins with cooperation.If the other player betrayed in this round,TFT will punish the betrayed one in the next round.If the other player also takes the cooperation strategy in this round,TFT will keep on cooperate with him in the next round.The presented algorithm is based on alternating prisoner＇s dilemma and TFT strategy.A new conception,named consanguinity,is been proposed.This conception is used to inspirit nodes of network to cooperate with each other.The users with higher consanguinity will glad to forward routing request（RREQ） packet.If a node agrees to forward RREQ,the consanguinity with requestor will increase.At the same time,the consanguinity with other nodes which would be interfered by this transmission will decrease.A node forwards RREQ packet whether or not depends the benefit it will achieve.The decision will have an impact on consanguinity of related nodes.Nodes have lower consanguinity with others imply that the RREQ forwarding request have large probability be refused,therefore the routing request maybe fail.Simulation result shows that the proposed approach can improve the performance of WMN effectively.