【作者】 孟坤；

【导师】 杨扬； 林闯；

【作者基本信息】 北京科技大学 ， 通信与信息系统， 2012， 博士

【摘要】 无线自组织网络是一种完全对等的网络通信系统,由具有收发功能的通信终端组成,通过采用相应的MAC协议和路由协议能够在不依赖网络设施的情况下迅速展开,实现通信终端间无线多跳的数据传输。部署的灵活性、网络的自管理性使得其能被广泛的应用于战场通信、紧急救灾通信、车载通信和公共场合临时通信等领域。由于无线自组织网络是完全自治的系统,路由功能需通过部署在节点的路由协议来完成,节点移动和节点行为不受任何外界因素的支配,导致网络变化频繁,势必造成通信链路中断经常发生；此外,节点资源的有限性制约了其缓存网络信息的能力,因此,获得必要的网络信息并基于这些信息设计高效的机制来保证网络运行性能成为了该领域研究的热点。本文在总结无线自组织网络路由关键问题的基础上,针对保护路由的设计展开了研究,在网络边界信息获取方法和分布式保护路由设计方面取得了较好的成果,主要成果可以分为以下五个方面：(1)从搜索论的角度,以信息为主线总结了无线自组织网络路由设计中的关键问题。通过对无线自组织网络路由开展深入的研究,分析了目前路由机制中源节点建立路由过程中所依赖的目的节点信息,并对这些信息进行了分类；在分析这些信息对路由机制效率和网络运行性能影响的基础上,总结了无线自组织网络路由机制设计中应重点关注的关键因素,确定了网络边界值是影响被动式路由机制效率和性能的最重要因素之一。(2)针对网络边界值的确定问题,从节点连接关系角度定义了网络的边界,考虑日益广泛应用的多信道通信模式,提出了多信道确定网络边界值的搜索模型。为满足探询分组容量受信道容量影响规模受限的要求,重点研究了利用容量受限探询分组确定网络边界值的模型,证明了该情况下假设网络边界值上限已知与否对应相同的最优搜索算法,设计了一种能精确确定网络边界值、且所需平均探询次数最少的搜索算法,并从理论上给出了严格证明。(3)基于确定网络边界值的通用模型,为适应信息传输不可靠的无线信道,考虑了搜索反馈信息可能出现错误情况下确定网络边界值的问题,建立了基于探测分组受限的容错搜索模型,针对假设探询过程中所有反馈中至多出现1次错误的特殊情况,设计了最坏情形下探询次数最少的容错搜索算法,并从理论上给出了严格证明。(4)针对无线自组织网络分布式的特点,为提高终端节点对自身存储信息的利用效率,建立了依据终端节点所拥有信息对节点进行分类的方法；通过把节点分为主活动节点、活动节点、备份节点和一般节点,明确了各类节点在路由机制中可行的行为及各类型节点间的转化关系,方便了路径建立和维护；基于上述性质,从关键路径选取、备份节点设定、路径失效处理等方面给出了基于多关键路径的保护路由机制MKRP。(5)此外,为更好地了解无线自组织网络的运行机制及其相关关键问题,在深入研究路由机制关键问题的基础上,基于商业路由器、嵌入式开发板及x86主机建立了无线自组织网络综合测试平台QoS-WADN,并对本文所设计的算法进行了测试与分析。更多还原

【Abstract】 An ad hoc wireless network is a complete autonomous system that consists ofdevices with transmitter and receiver. Recently, Ad hoc wireless networks have beenextensively applied in battle field communication, emergency communication and ve-hicle communication etc. However, nodal mobility lead to that the network topologychanges rapidly and unpredictably over time, and which has became an essential fea-ture considered for designing an efcient network. On the other hand, nodes lack suf-cient power restricts their ability to obtain and maintain sufcient network information.Therefore study on mechanisms to enhance network performance with limited networkinformation becomes one of the hottest direction in this field.Without information about the destination, a route discovery involving expensivenetwork-wide flooding is typically used by reactive routing protocols. Through in-depth studying routing protocols in ad hoc wireless networks, we determine criticalreasons causing broadcast storm when finding routes to the destination and prove thatthe diameter of the network is one of the most fundamental factors. In this article, wepropose a search model of determine the value of network diameter and obtain severaloptimal algorithms. To enhance robustness of routing, we introduce protection routingfor ad hoc wireless networks and obtain a distributed protection routing protocol, sayMKRP (Multiple Key-Routes Protection routing). In detail, the main contributionsinclude the follows.(1) We conclude several critical problems for designing routing protocols. Therouting protocols are modeled with search processes, we model routing protocol withsearch processes and classify information it used as position, direction and distance etc.Through comparing these information’s roles in protocols, we sort their importance andfilters the most critical factors.(2) We propose a method to search the upper boundary of the network diame-ter. With the group testing model, we obtain a method to determine exact value of a network’s diameter. To fit the limitation of resource of nodes, we propose a modelof search with small sets through restricting the above model with limited query vol-ume, and design an algorithm with minimum average queries and prove its optimalitytheoretically.(3) We propose a method to determine the exact value of network diameter eventhough there exists at most feedback fault during whole search process. To fit the un-reliability of wireless channel, based on the general search with small sets, we presenta search with lies and small sets model to design fault tolerant strategies of computingthe networks’diameter. For the case of allowing at most one lie is allowed, we obtaina worst-case optimal algorithm and prove it theoretically.(4) We propose a distributed protection routing MKRP (Multiple Key Routesbased Protection routing). All nodes are classified into primary active nodes, activenodes, backup nodes and normal nodes, according to the information stored in them,and their transfer relationship is defined. Based on the above techniques we obtain andistributed protection routing including node-disjoint key paths discovery, secondarypaths selection, failure maintenance and routing table discard, say MKRP, and its cor-rectness and performance is verified theoretically and experimentally.Besides, we develop a comprehensive performance evaluation test-bed Qos WADN with commercial routing devices, embedded boards and computer servers andverify our designed algorithms such as MKRP in this dissertation.更多还原