移动自组网中,网络的拓扑结构可以通过调节每个节点的传输功率加以控制,拓扑控制的基本目标是设计基于功率优化的算法,既能维护网络的连通性,又能降低节点的传输功率,延长节点的生存时间,达到优化网络性能的目的.在GG图的基础上,提出了...移动自组网中,网络的拓扑结构可以通过调节每个节点的传输功率加以控制,拓扑控制的基本目标是设计基于功率优化的算法,既能维护网络的连通性,又能降低节点的传输功率,延长节点的生存时间,达到优化网络性能的目的.在GG图的基础上,提出了一种基于能量效率的拓扑控制算法VCGG(a varying-cone distributed topology-control algorithm on Gabriel graph).算法采用可变扇区的思想,运用优先删除最远节点的方法(FDFN)选择逻辑邻居节点,建立了一个度有界、平面、干扰小的t-支撑图.模拟结果显示:VCGG算法与SΘGG,SYaoGG等算法相比,减少了节点的传输功率,降低了通信邻居节点的数目,减轻了邻居节点的干扰,提高了能量的使用效率.展开更多
A fault-tolerant 1-spanner is used to preserve all the minimum energy paths after node failures to cope with fault-tolerant topology control problems in wireless ad hoc networks. A fault-tolerant 1-spanner is a graph ...A fault-tolerant 1-spanner is used to preserve all the minimum energy paths after node failures to cope with fault-tolerant topology control problems in wireless ad hoc networks. A fault-tolerant 1-spanner is a graph such that the remaining graph after node failures will not only remain connected, but also have a stretch factor of one. The fault-tolerant 1-spanner is used in a localized and distributed topology control algorithm, named the k-Fault-Tolerant 1-Spanner （k-FT1S）, where each node constructs a minimum energy path tree for every local failed node set. This paper proves that the topology constructed by k-FT1S is a k-fault-tolerant 1-spanner that can tolerate up to k node failures, such that the remaining network after node failures preserves all the minimum energy paths of the remaining network gained from the initial network by removing the same failed nodes. Simulations show that the remaining network after removal of any k nodes still has the optimal energy efficiency and is competitive in terms of average logical degree, average physical degree, and average transmission radius.展开更多
With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The proble...With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.展开更多
基金Supported by the National Natural Science Foundation of China under Grant Nos.90304010 60673164(国家自然科学基金)+3 种基金the Program for New Century Excellent Talents in University of China under Grant No.NCET050683(新世纪优秀人才支持计划)the National Research Foundation for the Doctoral Program of Ministry of Education of China under Grant No.20060533057(国家教育部博士点基金)the Provincial Natural Science Foundation of Hu’nan of China under Grant No.06JJ10009(湖南省杰出青年基金)the Scientific Research Fund of Hu’nan Provincial Education Department of China under Grant No.05D054(湖南省教育厅资助科研项目)
文摘移动自组网中,网络的拓扑结构可以通过调节每个节点的传输功率加以控制,拓扑控制的基本目标是设计基于功率优化的算法,既能维护网络的连通性,又能降低节点的传输功率,延长节点的生存时间,达到优化网络性能的目的.在GG图的基础上,提出了一种基于能量效率的拓扑控制算法VCGG(a varying-cone distributed topology-control algorithm on Gabriel graph).算法采用可变扇区的思想,运用优先删除最远节点的方法(FDFN)选择逻辑邻居节点,建立了一个度有界、平面、干扰小的t-支撑图.模拟结果显示:VCGG算法与SΘGG,SYaoGG等算法相比,减少了节点的传输功率,降低了通信邻居节点的数目,减轻了邻居节点的干扰,提高了能量的使用效率.
基金Supported by the National Natural Science Foundation of China (No.60932005)
文摘A fault-tolerant 1-spanner is used to preserve all the minimum energy paths after node failures to cope with fault-tolerant topology control problems in wireless ad hoc networks. A fault-tolerant 1-spanner is a graph such that the remaining graph after node failures will not only remain connected, but also have a stretch factor of one. The fault-tolerant 1-spanner is used in a localized and distributed topology control algorithm, named the k-Fault-Tolerant 1-Spanner （k-FT1S）, where each node constructs a minimum energy path tree for every local failed node set. This paper proves that the topology constructed by k-FT1S is a k-fault-tolerant 1-spanner that can tolerate up to k node failures, such that the remaining network after node failures preserves all the minimum energy paths of the remaining network gained from the initial network by removing the same failed nodes. Simulations show that the remaining network after removal of any k nodes still has the optimal energy efficiency and is competitive in terms of average logical degree, average physical degree, and average transmission radius.
基金by National Key R&D Program of China(No.2019YFB2101604).
文摘With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.
