【作者】 吴静；

【导师】 顾国昌；

【作者基本信息】 哈尔滨工程大学 ， 计算机应用技术， 2009， 博士

【摘要】 随着网络规模的不断扩大,可扩展性问题被列为了自组网中几个亟待解决的问题之一,而分级结构已成为该问题的主要解决方案,对分级结构的研究具有很高的理论价值和应用价值。目前,分级结构包括两层分级结构和多层分级结构,虽然现有多层分级结构(MHS)比两层分级结构的可扩展性好,但也存在着结构稳定性较差和结构维护开销大等问题。针对上述问题,提出一种稳定多层分级结构(SMHS),并继而对SMHS的关键技术展开了深入地研究。主要研究内容包括如下四部分:(1)针对MHS存在的问题,提出一种稳定多层分级结构(SMHS)及其分群算法。SMHS采用一种“结构不依赖于某些易于变化的中心节点,而是依赖于一些相对稳定的群”的新策略,当发生群代表轮换时,只要节点不离开群,它的分级地址(HID)就不会变更,这提高了结构的稳定性,进而降低了结构的维护开销;同时,它采用“高层虚拟链路以一些变更频率相对较低的群为构成元素”的新策略,这提高了高层虚拟链路的稳定性,从而也降低了结构的维护开销。SMHS的分群算法包括底层分群算法和高层分群算法,选择有利于提高底层分群稳定性的考虑运动相关性分群算法中在稳定性度量方面考虑最全面的典型分群算法MSWCA所采用的分群标准来进行底层分群,而以最大连接群度为分群标准来进行高层分群。(2)针对SMHS底层分群算法存在的“只考虑底层群内稳定性,而忽视底层群间稳定性”的问题,提出一种稳定多层分级结构(SMHS)的底层改进方法——增强分群稳定性的底层分群算法(BCAECS),该算法基于移动预测思想,综合考虑底层群内稳定性、底层群间稳定性和底层分群优化,通过调节权值使算法适用于不同的场景,这提高了底层分群稳定性,并降低了底层分群维护开销。(3)针对SMHS不存在与其匹配的层次路由协议的问题,借鉴典型的基于多层分级结构MHS的层次路由协议HSR的思想,并结合SMHS的特点,提出一种基于稳定多层分级结构(SMHS)的层次路由协议(HRP)。HRP的结构和高层虚拟链路具有较高的稳定性,这提高了协议的可靠性,还降低了丢包数目和重路由次数,从而降低了协议的传输时延和路由开销;同时,HRP的结构维护开销和位置管理开销相对较低,这也降低了协议的路由开销。(4)为了提高SMHS的底层分群稳定性,提出一种稳定多层分级结构(SMHS)的底层改进方法——构建半径为多跳的底层分群,采用一种适用范围较广泛的典型混合式平面结构路由协议ZRP作为底层群内路由协议。半径为多跳的底层分群算法只需要对SMHS底层分群算法进行略微修改即可得到,故不将它作为研究重点,而是将底层群内路由协议ZRP作为研究重点。针对“SMHS的底层群内路由协议ZRP的域间路由维护策略使ZRP具有较多的丢包数目和较多的路由重发现次数;前者使ZRP的数据包投递率较低,这使ZRP的可靠性较低;后者使ZRP的传输时延和路由开销较高。”的问题,提出一种基于分段修复的底层群内路由协议(SRBIRP)。在SRBIRP中,每个节点通过维护一个基于域内拓扑结构的有向无环图DAG来保存到达其域内每个节点的多条备份路由,尽量利用备份分段路由进行域间路由修复。SRBIRP的域间路由维护策略降低了丢包数目和路由重发现次数,这提高了协议的数据包投递率,并说明SRBIRP提高了协议的可靠性;同时,这还降低了协议的传输时延和路由开销。以上的研究工作不但促进了分群算法、基于分级结构的层次路由协议和平面结构路由协议等相关理论的发展,而且还为自组网的可扩展性提供了更好的支持。更多还原

【Abstract】 As ad hoc networks’scale increasing constantly, scalability problem has been listed as one of the several problems urgent to be solved, and hierarchical structure has been a main solution to this problem. And researches on hierarchical structure have very high theory value and application value. At present, hierarchical structure includes two-layer hierarchical structure and multi-layer hierarchical structure. The scalability of present multi-layer hierarchical structure (MHS) is better than that of two-layer hierarchical structure, but MHS also exists some problems such as poor structure stability and large structure maintenance overheads. Aiming at above problems, a stable multi-layer hierarchical structure (SMHS) is proposed, and then SMHS’s key technologies are researched in depth. The main research content includes the following four parts:(1) Aiming at the problems existing in MHS, stable multi-layer hierarchical structure (SMHS) and its clustering algorithm are proposed. SMHS adopts a new scheme that“a structure doesn’t rely on some centered nodes apt to vary, but relies on some relatively stable clusters”. As long as a node doesn’t leave a cluster, its HID (Hierarchical ID) doesn’t change with the cluster-representative’s alteration, which improves structure’s stability and furthers to reduce structure’s maintenance overheads. Meanwhile, SMHS adopts a new scheme that“a high-layer virtual link is composed of some clusters with relatively low alternation frequencies”, which improves the stability of a high-layer virtual link and then also reduces structure’s maintenance overheads. SMHS’s clustering algorithm includes bottom-layer clustering algorithm and high-layer clustering algorithm. The bottom-layer clustering is proceeded by the clustering criterion adopted by the typical clustering algorithm MSWCA which has the most comprehensive consideration on stability measurement in clustering algorithms with motion-correlativity consideration that is favorable for improving bottom-layer clusters’stability. And high-layer clustering is proceeded by making the biggest connectivity cluster-degree as its clustering criterion.(2) Aiming at the problem existing in SMHS’s bottom-layer clustering algorithm that“it only considers on bottom-layer intracluster stability, but neglects bottom-layer intercluster stability”, the bottom-layer improving method of stable multi-layer hierarchical structure (SMHS) that“bottom-layer clustering algorithm which enhances clusters’stability (BCAECS)”is proposed. Based on mobility prediction idea, BCAECS considers on bottom-layer intracluster stability, bottom-layer intercluster stability and bottom-layer clusters’optimization comprehensively, and it’s adapted to different scenarios by adjusting weights, which improves bottom-layer clusters’stability and reduces bottom-layer clusters’maintenance overheads.(3) Aiming at the problem that SMHS doesn’t exist a matched hierarchical routing protocol, the stable multi-layer hierarchical structure (SMHS) based hierarchical routing protocol (HRP) is proposed, which refers to the thought of a typical multi-layer hierarchical structure MHS based hierarchical routing protocol HSR and combines SMHS’s characteristic. HRP’s structure and high-layer virtual links have higher stability. It improves the protocol’s reliability and also reduces the lost-packets’number and rerouting times, and then reduces the protocol’s transmission delay and routing overheads. Meanwhile, HRP’s structure maintenance overheads and position management overheads are relatively low, which also reduces the protocol’s routing overheads.(4) To improve the stability of SMHS’s bottom-layer clusters, the bottom-layer improving method of stable multi-layer hierarchical structure (SMHS) that“bottom-layer clusters with multi-hop radius are constructed, and a typical hybrid flat structure routing protocol ZRP with a wide application range is adopted as bottom-layer intracluster routing protocol”is proposed. The bottom-layer clustering algorithm with multi-hop radius can be achieved by a little modification of SMHS’s bottom-layer clustering algorithm, so the bottom-layer clustering algorithm is not the research emphasis, but the bottom-layer intracluster routing protocol ZRP is. Aiming at the problem that“interzone-route maintenance scheme of SMHS’s bottom-layer intracluster routing protocol ZRP makes ZRP have many lost packets’number and many route rediscovering times; the former makes ZRP’s delivery ratio of data packets low, which makes ZRP’s reliability low; the latter makes ZRP’s transmission delay and routing overheads high.”, the segment repair based bottom-layer intracluster routing protocol (SRBIRP) is proposed. In SRBIRP, each node saves multiple backup routes to each node in its intrazone by maintaining an intrazone topology structure based directed acyclic graph (DAG), and an interzone route is repaired by using backup segment-routes as much as possible. SRBIRP’s interzone-route maintenance scheme reduces lost packets’number and route rediscovering times. It improves delivery ratio of data packets of the protocol and shows that SRBIRP improves the protocol’s reliability, and it also reduces the transmission delay and routing overheads of the protocol.The above research work not only prompts developments of correlative theories such as clustering algorithms, hierarchical structure based hierarchical routing protocols and flat structure based routing protocols but also provides a better support to scalability of ad hoc networks.更多还原