自组网容错拓扑控制的研究

为省能而提出的拓扑控制若未考虑容错易造成自组网无法面对节点和无线信道失效.本文针对一般的原始平面图G0提出了保持两点之间最大限度K点、K边和K路径容错连通能力的概念.设计了一种基于K条内部节点互不相交路径的分布式拓扑控制算法LKINDP,能够保持G0内任意两点之间最大限度K连通容错能力,并给出了证明.仿真结果表明,LKINDP能够显著减小平均电台半径,简化网络拓扑结构,并且能够通过改变K值来调整网络的容错能力.     

Equilibria in Topology Control Games for Ad Hoc Networks

We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks. A preliminary version of this paper appeared in DIALM-POMC ’03 [8]. Stephan Eidenbenz is a technical staff member in Discrete Simulation Sciences (CCS-5) at Los Alamos National Laboraotry. He received his Ph.D. in Computer Science from the Swiss Federal Institute of Technology, Zurich, Switzerland in 2000. Stephan’s research covers areas in approximability, algorithms, computational geometry, computational biology, large-scale discrete simulation, selfish networking, efficient networking, protocol design and optimization. V. S. Anil Kumar is currently an Assistant Professor in the Dept. of Computer Science and a Senior Research Associate at Virginia Bioinformatics Institute, Virginia Tech. Prior to this, he was a technical staff member in Los Alamos National Laboratory. He received a Ph.D. in Computer Science from the Indian Institute of Science in 1999. His research interests include approximation algorithms, mobile computing, combinatorial optimization and simulation of large socio-technical systems. Sibylle Zust received her Masters degree in mathematics from ETH Zurich in Switzerland in 2002. She wrote her diploma thesis at the University of Copenhagen in Denmark. Sibylle Zust spent two and a half years (2002–2005) as a graduate research assistant at the Los Alamos National Laboratory in New Mexico, USA, where she worked on algorithmic aspects of game theory and scheduling problems. She now works for an insurance company in Zurich, Switzerland.     

Ad Hoc网络拓扑控制算法的研究与仿真

拓扑控制是无线网络优化的核心问题之一，其目的在于降低节点间传输功率，延长网络寿命和减少节点邻居数目。文中介绍了基于节点方向信息和基于位置信息的两种分布式算法并对其进行研究与仿真，并从业务负载量上说明拓扑控制给网络带来的显著优化。     

A Game Theoretical Approach for Topology Control in Wireless Ad Hoc Networks with Selfish Nodes

In ad hoc networks, a significant amount of energy available to devices is utilized in network management operations. Since devices have limited energy resources, therefore, they drop data packets of other nodes to reduce their energy consumption. This selfish behaviour increases number of retransmissions over the link which increases energy consumption of the source node, introduces time delays, and degrades throughput of the network. Although conventional distributed topology control solutions minimize energy utilization of the nodes by adjustment of transmission power, however, selfish behaviour by devices introduce additional complexity in design which make topology control a challenging task. In this paper, we proposed Energy Efficient Topology Control Algorithm (EETCA) using game theoretical approach, in which, utility of the node depends on selfishness of the neighbors, link traffic rate, and link length. In decision-making step, nodes remove the links with other nodes that have high drop rate under the condition that network remains connected. We show that Nash Equilibrium point of the proposed game results in Pareto optimal network topology. We compare results of EETCA with Optimum (OPT) and Minimum Least Power Path Tree (MLPT) algorithms presented in literature. We carried our simulations under multiple sources scenario which show that EETCA outperforms previous approaches when number of nodes in the network increases. Furthermore, we simulate the performance of Ad-hoc On-demand Distance Vector (AODV) routing protocol under EETCA topology and compare it with MLPT and OPT topologies. The results show that the ad hoc network constructed using proposed solution substantially improves throughput of AODV routing protocol as compared to MLPT and OPT topology control algorithms.     

Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is developed. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.     

Topology Management in Directional Antenna-Equipped Ad Hoc Networks

With fully directional communications, nodes must track the positions of their neighbors so that communication with these neighbors is feasible when needed. Tracking process introduces an overhead, which increases with the number of discovered neighbors. The overhead can be reduced if nodes maintain only a subset of their neighbors; however, this may increase the length of paths between node pairs in the network. In this work, we study the tradeoffs between node degree and path stretch. We first design a topology control algorithm to optimize this tradeoff. Assuming that nodes communicate with their directional neighbors using circular directional transmissions, we model the original graph as a unit disk graph (UDG). Given a UDG G, our algorithm finds a sparse subgraph G' with a maximum degree of 6, and connecting each node pair u,v by a path of length hops_{G'}(u,v)=O(hops_G(u,v)+logDelta), where Delta is the maximum degree in G, hops_{G}(u,v) denotes length of the shortest path between u, v in G. We show that this result is near-optimal. Based on the insights gained from this design, we next construct a simpler, more practical scheme that integrates fully-directional neighbor discovery and maintenance with topology control strategy. We simulate both algorithms and compare their performances.     

一种Ad Hoc网络的拓扑功率控制算法

Ad hoc网络是一种无线自组织网络，拓扑功率控制是其网络优化的核心问题之一。它能够有效降低节点间的传输功率，以提高整个网络的稳定性。文章旨在介绍一种基于节点间距离的分布式拓扑功率控制算法，通过改变网络拓扑结构，以达到节省网络能量的效果，并实现了网络中任意两节点间的K连通。     

A Cooperative Nearest Neighbours Topology Control Algorithm for Wireless Ad Hoc Networks

In this article, we introduce a simple distributed algorithm that assigns appropriate individual transmission powers to devices in a wireless ad hoc network. In contrast to many other proposed algorithms, it does without special hardware. It requires only local neighbourhood information and therefore avoids flooding information throughout the network. Finally, the cooperative nature of the algorithm avoids that devices cause excessive interference by using unnecessarily high transmission powers. By means of simulation, we show that the topologies created by this algorithm without any global knowledge are as effective as topologies resulting from a good choice of a common transmission power (which would require global knowledge) in terms of the achievable throughput. This work was supported in part by the German Federal Ministry of Education and Research (BMBF) as part of the IPonAir project.     

Energy‐Connectivity Tradeoff through Topology Control in Wireless Ad Hoc Networks

In this study, we investigate topology control as a means of obtaining the best possible compromise between the conflicting requirements of reducing energy consumption and improving network connectivity. A topology design algorithm capable of producing network topologies that minimize energy consumption under a minimum‐connectivity constraint is presented. To this end, we define a new topology metric, called connectivity efficiency, which is a function of both algebraic connectivity and the transmit power level. Based on this metric, links that require a high transmit power but only contribute to a small fraction of the network connectivity are chosen to be removed. A connectivity‐efficiency‐based topology control (CETC) algorithm then assigns a transmit power level to each node. The network topology derived by the proposed CETC heuristic algorithm is shown to attain a better tradeoff between energy consumption and network connectivity than existing algorithms. Simulation results demonstrate the efficiency of the CECT algorithm.     

SWAN模型速率控制模块性能分析及改进

SWAN是Ad Hoe网络中的一种无状态网络协议,利用分布式控制算法来传递分类服务。这种QoS模型把数据业务分为两类进行不同处理,即对尽力而为的UDP和TCP业务采用速率控制的策略而对实时的UDP业务采用基于源节点的接纳控制策略。本文修改了SWAN模型的速率控制模块,引入队列调度机制,对从上层来的尽力而为数据包进行排队、调度,使其尽可能公平地占用新到资源。在分析中具体给出了修改后速率控制模块的实现过程。通过仿真分析了AIMD算法的参数对修改后速率控制模块性能的影响。     

基于自适应波束天线自组网的能量效率拓扑控制

 针对自适应波束定向天线自组网,运用样方统计法推导自组网高概率连通的关键传输半径和邻居数K,提出一种基于邻居数的分布式拓扑控算法DK-Neigh,构建结点出度等于(或略小于)K的有向连通拓扑图.仿真结果表明:DK-Neigh可以保证网络连通率大于96%;当天线波束宽度小于60时,DK-Neigh的结点节能比全向天线K-Neigh算法提高15%.DK-Neigh在保证网络高概率连通的同时减少结点能耗,提高网络能量效率.     

Interference Aware Route Discovery in Wireless Mobile Ad Hoc Networks

In this paper, we propose an interference aware expanding region search algorithm to locate a destination in mobile ad hoc networks. In the proposed approach, signal to interference plus noise ration (SINR) is used in place of TTL field of a route request packet. The source node initializes the search query with a threshold value of SINR. Each relay node forwards the packet if its SINR satisfies the threshold criteria provided by the source node in RREQ packet. As a result, the low SINR nodes are removed in route discovery phase prior to the establishment of routes. The simulation results show that proposed algorithm provides significant improvement in performance of reactive routing protocol in terms of reduced routing overhead, reduced energy consumption, and increased network throughput.

     

Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks

Among the most critical issues of wireless ad hoc and sensor networks are energy consumption in general and interference in particular. The reduction of interference is consequently considered one of the foremost goals of topology control. Almost all of the related work however considers this issue implicitly: Low interference is often claimed to be a consequence of sparseness or low degree of the constructed topologies. This paper, in contrast, studies explicit definitions of interference. Various models of interference—both from a sender-centric and a receiver-centric perspective—are proposed, compared, and analyzed with respect to their algorithmic properties and complexities.      

A Cross-layer Approach to Channel Assignment in Wireless Ad Hoc Networks

To improve the capacity of wireless ad hoc networks by exploiting multiple available channels, we propose a distributed channel assignment protocol that is based on a cross-layer approach. By combining channel assignment with routing protocols, the proposed channel assignment protocol is shown to require fewer channels and exhibit lower communication, computation, and storage complexity than existing channel assignment schemes. A multi-channel MAC (MC-MAC) protocol that works with the proposed channel assignment protocol is also presented. We prove the correctness of the proposed channel assignment protocol. In addition, through a performance study, we show that the proposed protocol can substantially increase throughput and reduce delay in wireless ad hoc networks, compared to the IEEE 802.11 MAC protocol and an existing multi-channel scheme.

Localized Algorithms for Energy Efficient Topology in Wireless Ad Hoc Networks

Topology control in wireless ad hoc networks is to select a subgraph of the communication graph (when all nodes use their maximum transmission range) with some properties for energy conservation. In this paper, we propose two novel localized topology control methods for homogeneous wireless ad hoc networks. Our first method constructs a structure with the following attractive properties: power efficient, bounded node degree, and planar. Its power stretch factor is at most , and each node only has to maintain at most neighbors where the integer is an adjustable parameter, and β is a real constant between 2 and 5 depending on the wireless transmission environment. It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can be represented in bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is bits. Our second method improves the degree bound to k, relaxes the theoretical power spanning ratio to , where is an adjustable parameter, and keeps all other properties. We show that the second structure can be constructed using at most 3n messages, where each message has size of bits. We also experimentally evaluate the performance of these new energy efficient network topologies. The theoretical results are corroborated by the simulations: these structures are more efficient in practice, compared with other known structures used in wireless ad hoc networks and are easier to construct. In addition, the power assignment based on our new structures shows low energy cost and small interference at each wireless node. The work of Xiang-Yang Li is partially supported by NSFCCR-0311174. Wen-Zhan Song received Ph.D. from Illinois Institute of Technology in 2005, BS and MS from Nanjing University of Science and Technology in 1997 and 2000. He is currently an assistant professor in Washington State University. His current research interest is mainly focus on network protocol and algorithm design, especially in wireless networks, sensor networks and Peer-to-Peer networks. He is a member of the IEEE. Yu Wang received the Ph.D. degree in computer science from Illinois Institute of Technology in 2004, the BEng degree and the MEng degree in computer science from Tsinghua University, China, in 1998 and 2000. He has been an assistant professor of computer science at the Univeristy of North Carolina at Charlotte since 2004. His current research interests include wireless networks, mobile computing, algorithm design, and artificial intelligence. He is a member of the ACM, IEEE, and IEEE Communication Society. Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He hold MS (2000) and PhD (2001) degree at Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Computer Science and Bachelor degree at Business Management from Tsinghua University, P.R. China in 1995. His research interests span the computational geometry, wireless ad hoc networks, game theory, cryptography and network security. He is a Member of the ACM, IEEE, and IEEE Communication Society. Ophir Frieder is the IITRI Professor of Computer Science at the Illinois Institute of Technology. His research interests span the general area of distributed information systems. He is a Member of ACM and a Fellow of the IEEE.     

An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks

The one type of routing in ad hoc and sensor networks that currently appears to be most amenable to algorithmic analysis is geographic routing. This paper contains an introduction to the problem field of geographic routing, presents a specific routing algorithm based on a synthesis of the greedy forwarding and face routing approaches, and provides an algorithmic analysis of the presented algorithm from both a worst-case and an average-case perspective.     

A Mobile-Directory Approach to Service Discovery in Wireless Ad Hoc Networks

We present the Service Directory Placement Algorithm (SDPA), a directory-placement scheme that leverages the performance of existing service discovery protocols over wireless ad-hoc networks. SDPA promotes the deployment of a nomadic service directory, whose current location in the network varies according to the dynamics of service-discovery queries driven by the users' applications and partial knowledge of the network's topology. SDPA is based on a heuristic approach, whose performance is optimized by formulating the directory-placement problem as a Semi-Markov Decision Process solved by means of a reinforcement-learning technique known as Q-Learning. Performance evaluations obtained through computer simulations of networks with up to 45 hosts moving at pedestrian walking speeds equal to or slower than 2 m/s reveal average bandwidth savings close to 50% over a default broadcast approach for service discovery once an efficient directory-placement policy is found.     

分布式无线网络中的自适应控制协议

本文提出了一种新颖的移动分群算法和分群保持策略,它可以用较少的控制开销快速获得网络的分群控制结构并能适应拓扑结构的变化.采用重叠群方案简单可靠地实现了分群大小的优化,将节点密度高的区域灵活地划分成多个节点数较少的群,增大了每个节点的通信容量.提出了网关智能控制协议,该协议缓解了网关成为多信道分群间通信的瓶颈.     

干扰消除对无线Ad Hoc网络传输容量的影响

无线Ad Hoc网络是一个干扰受限系统,网络的容量取决于网络中的干扰信号功率的大小。在目前针对无线Ad Hoc网络容量进行研究的文献中没有使用有效的抑制干扰信号功率的方法,使得网络容量受到很大限制。提出通过设置保护区域的方法来降低干扰信号强度,重新对无线Ad Hoc网络进行建模,并推导了传输容量的上下界。通过仿真结果可以知道,设置保护区域能够极大程度降低网络中的干扰信号强度,合理地设置保护区域大小能有效提高传输容量。