【作者】 郭建立；

【导师】 Daniel P. Siewiorek； 杨孝宗；

【作者基本信息】 哈尔滨工业大学 ， 计算机系统结构， 2009， 博士

【摘要】 移动自组网是由多个移动节点临时组成的一个不依赖任何基础通信设施的多跳无线网络。由于缺乏基础设施的支持,再加上节点有限的传输范围,源节点往往不能直接把数据传到目的节点,而需要借助邻居节点的转发功能。在移动自组网中,如果没有节点间的合作,路由将不能建立,数据包将不会被转发,节点间也就不能存在多跳通讯。但是节点间的合作,例如为其它节点转发数据,不是总能被保证的。网络中的自私节点可能会出于节省自己资源(如能量)的目的,拒绝为网络中的其它节点转发数据,从而表现不合作行为,这将严重影响网络的性能。移动自组网中节点合作方法的目的正是用于迫使或激励自私节点参与网络合作,从而维持网络的正常运行。本文对基于信誉的节点合作方法进行了改进,提出了基于共同邻居监听的节点合作方法(Common-neighbor Monitoring enabled Cooperation enforcementscheme,CMC),通过引入共同邻居监听技术,看门狗在对下一跳转发节点进行监听的同时,还对周围不相关的数据流进行监听,加快了系统对自私节点的检测速度。在路由发现过程中,CMC方法还对路由控制消息进行了过滤,丢弃那些含有自私节点的路由请求包和路由应答包,使源节点所发现的路由能够尽量绕过自私节点,进一步减小自私节点对网络性能的影响。在采用直接信息计算节点信誉值的方法中,虽然检测准确度较高,并且实现相对容易,但对自私节点的检测速度较慢,往往不能及时发现网络中的自私节点,于是本文进一步提出了TORA协议增强合作方法(TORAprotocolwithCooperation Enhanced, TORA CE),采用一跳信息计算节点的信誉值,加快了对自私节点的检测速度。TORA CE方法基于TORA协议,是一种多径路由自组网节点合作方法,每个节点拥有多条通往目的节点的路径,在发现自私节点后,能够快速切换路由,减小了数据传输过程中丢包的概率。TORA CE方法具有更好的分布式特点,能够将自私节点引发的路由变化限制在自私节点附近较小的范围内。利用博弈论和机制设计理论分析并设计节点合作方法是未来发展的必然趋势,本文还对基于VCG机制的节点合作方法进行了分析,并在此基础上提出了低负载合作协议(A Low Message-Overhead Cooperation Protocol,LMOCP)。LMOCP协议是对Ad hoc-VCG和LOTTO协议的一个改进,修正了Adhoc-VCG协议中所存在的四个缺点,并且具有更低的消息负载。通过引入邻居发现过程,节点周期地以最大传输功率发送广播消息,使每个节点都能随时计算出所有邻居到自己的最小传输功率,同时还对路由发现过程进行了改进,减少了路由发现过程中控制消息的数量。本文还从理论上对LMOCP协议的正确性进行了分析,证明了LMOCP协议是事后纳什可实现的,在所有节点都是理性的这一共同知识的假定下,每个节点的最优策略是诚实地报告自己的转发价格。但是LMOCP协议中的消息负载依然很大,为O(n~2),为此本文进一步提出了广播树增强节点合作协议(Broadcast-treeEnhancedCooperationProtocol,BEC)。通过在路由发现过程中创建一棵以目的节点为根的广播树,使控制消息沿着广播树以单播方式传送到根节点,能够进一步减少路由发现过程中控制消息的数量。对于一棵高度为O(lg(n))的广播树,协议的消息负载为O(n lg(n)),低于LOTTO协议的O(n~2)。另外,在BEC协议中,由目的节点收集网络的拓扑信息,并负责计算最小价格路径及各转发节点的支付,不需要假定源节点是诚实的,这更加符合网络的真实情况。更多还原

【Abstract】 Mobile ad hoc network is a Multi-hop Wireless Network which is composed of anumber of mobile nodes and does not rely on any infrastructure communication facility.Due to the lack of infrastructure supporting, coupled with the limited transmission rangeof nodes, the source nodes can not often communicate directly with the destination nodes,so the helps of middle forwarding nodes are demanded. In mobile ad hoc network, ifthere is no cooperation between nodes, routing will not to be set up, packets will not betransmitted, and there cannot exist multi-hop communications between nodes.However, the cooperation between nodes, for example, forwarding data for othernodes, is not always guaranteed. For the purpose of saving their own resources (suchas energy), selfish nodes may refuse to forward packets for other nodes, thus showingthe non-cooperative behaviors, which can seriously affect the network performance. Thepurpose of cooperation scheme is to enforce or incentive the selfish nodes to participatein the network cooperation, maintaining the normal operations of the network.In this thesis, we have improved the reputation based cooperation schemesand proposed the common-neighbor monitoring enabled cooperation enforcementscheme(CMC). Through the introduction of common neighbor monitoring technique, thewatchdog not only monitors the behavior of next hop forwarding node, but also monitorsthe surrounding connections, speeding up the detecting rate to the selfish nodes. In theroute discovery phase, the CMC scheme filters the routing control messages, discardingthose messages which contain selfish nodes, making the route that the source node findsas far as possible bypass the selfish nodes, reducing the impact that selfish nodes have onnetwork performance.The CMC scheme calculates node reputations using the direct information, althougha higher detection accuracy and relatively easy to implement, the detection rate to self-ish nodes is slow. So this thesis further proposed the TORA protocol with cooperationenhanced scheme(TORA CE), which computes the node reputations using one-hop infor-mation, improving the detection rate to selfish nodes. The TORA CE scheme, which isbased on the TORA protocol, is a multi-path ad hoc network nodes cooperation scheme.Each node has multi paths leading to the destination node. After the discovery of a selfish node, the TORA CE scheme can switch route quickly, reducing the probability of drop-ping packets in data transmission phase. The TORA CE method has better distributedcharacteristics, and limiting the route changes that selfish nodes triggered in a smallerrange.Using the game theory and mechanism design theory to analysis and design nodecooperation schemes is the inevitable trend of the future, so this thesis has analyzed theVCG mechanism based cooperation scheme and proposed the low message-overhead co-operation protocol(LMOCP). The LMOCP protocol is an improvement to the Ad hoc-VCG and LOTTO protocol, modifying four drawbacks in the Ad hoc-VCG protocol, andhas a lower message overload. Through the introduction of neighbor discovery process,nodes periodically broadcast“hello”messages in maximum transmitting power, so thateach node can calculate the minimum transmission power from neighbors to itself. Atthe same time, the routing discovery process has been improved to reduce the number ofcontrol messages. This thesis also analyzed the correctness of the LMOCP protocol andproved that the LMOCP protocol is ex post Nash implementable. Under the assumptionthat all nodes are rationality, the optimal strategy for each node is to honestly report theirown forwarding cost.However, the message overhead of the LMOCP protocol is still huge, which isO(n~2), so this thesis further proposed a broadcast tree enhanced node cooperation proto-col (BEC). After the construction of a broadcast tree rooted at the destination node in therouting discovery process, the control messages are transmitted to the destination nodealong the broadcast tree, which can further reduce the control messages. For a broad-cast tree with its height equal to O(lg(n)), the message overhead in BEC protocol isO(n lg(n)), lower than that of LOTTO protocol which is O(n~2). In addition, in BEC pro-tocol, the destination node is responsible for collecting the network topology informationand calculating the minimum cost path from source to destination node, and do not needto assume that the source node is honest, which more satisfies the real situation of thenetwork.更多还原