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.     

Topology Management for Improving Routing and Network Performances in Mobile Ad Hoc Networks

A distributed topology management algorithm based on the construction of a forest from the topology of the network is proposed. In this algorithm, each tree of the forest forms a zone, and each zone is maintained proactively. As a result, the network can be seen as a set of non-overlapping zones. We introduce the concept of quality of connectivity for extracting the links connecting the pair of best nodes, and use this quality to construct the forest. We characterize the behaviors of the proposed topology management algorithm under various network density. We study the effect of the topology management on the performance of an ad hoc routing protocol. The results demonstrate that the performance of routing can be significantly improved with the help of topology management.     

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.     

Distributed Power Control for Energy Efficient Routing in Ad Hoc Networks

In this paper, distributed power control is proposed as a means to improve the energy efficiency of routing algorithms in ad hoc networks. Each node in the network estimates the power necessary to reach its own neighbors, and this power estimate is used both for tuning the transmit power (thereby reducing interference and energy consumption) and as the link cost for minimum energy routing. With reference to classic routing algorithms, such as Dijkstra and Link State, as well as more recently proposed ad hoc routing schemes, such as AODV, we demonstrate by extensive simulations that in many cases of interest our scheme provides substantial transmit energy savings while introducing limited degradation in terms of throughput and delay.     

移动Ad hoc网络基于链路质量和拓扑质量的路由协议

移动Ad hoc网络中节点的移动性使得频繁的路由失效与路由发现,路由发现中的控制开销是影响路由性能的一个重要的因素。传统的按需路由协议多采用洪泛的方式进行路由发现,并选取最小跳数路由。每个中间节点盲目的转发收到的路由请求包,不仅没有考虑链路质量,而且会引起广播风暴问题。本文提出一种基于链路质量和拓扑质量的路由协议,该协议根据相邻节点之间剩余链路生存期作为链路质量指标,同时根据中间节点与源-目的节点连线的距离关系作为拓扑质量指标。结合两个指标设置转发概率,不仅能避免频繁的路径断开,而且限制了路由请求包的传播范围。模拟结果显示,本文提出的方法在显著地降低路由控制开销的同时,还能够提高分组投递率并降低端到端延迟,从而提高了路由性能。     

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

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

On-Demand Utility-Based Power Control Routing for Energy-Aware Optimization in Mobile Ad Hoc Networks

In this paper, we propose a novel on-demand energy-aware routing protocol, UBPCR [utility-based power control routing], which reduces the trade-offs that arise in the other energy-aware route selection mechanisms that have recently been proposed for mobile ad hoc networks. Our approach is based on an economic framework that represents the degree of link's satisfaction (utility). With UBPCR, the utility function for any transmitter-receiver pair is defined as a measure of the link's preference regarding the signal-to-interference-and-noise ratio (SINR), the transmit power, and the transmitter's residual battery capacity. During a route-searching process, each intermediate node between the source and the destination is executed via two consecutive phases: the scheduling phase and the transmit power control phase. The scheduling algorithm finds the proper qualified data slot for the receiving channel so that the transmissions of independent transmitters can be coordinated. The transmit power control determines the optimal power, if one exists, that maximizes the corresponding link's utility. Extensive simulations show that the UBPCR protocol can achieve incompatible goals simultaneously and fairly. Chan-Ho Min received the B.S. degree in Industrial Management and the M.S. degree in Industrial Engineering from Korea Advanced Institute of Science and Technology (KAIST) in 2000 and 2002, respectively, where he is currently pursuing the doctoral degree in Industrial Engineering (Telecommunication Engineering Interdisciplinary Program) at KAIST. His research interests include the optimization problems of radio resource management for broadband wireless/cellular/ad hoc/satellite communication networks. In particular, he focuses on mobile ad hoc networking. Sehun Kim received the B.S. degree in Physics from Seoul National University, Seoul, Korea, and the M.S .and Ph.D. degrees in Operations Research from Stanford University. In 1982, he joined the faculty of the Korea Advanced Institute of Science and Technology (KAIST), where he is currently a Professor of Industrial Engineering. His research has been in the areas of combinatorial and nonlinear optimization. Recently, he is working on the application of optimization techniques to the design and analysis of computer and communication systems. He has published a number of papers in Mathematical Programming, Operations Research Letters, Journal of Optimization Theory and Applications, IEEE Trans. on Vehicular Technology, and International Journal of Satellite Communications.     

移动自组网中一种基于业务的拓扑控制算法

拓扑控制的实现途径是调节网络中每个节点的传输功率,而其所优化的网络指标有所差别,通常是减少节点的功率消耗以延长网络的生存时间。现有的拓扑控制算法关注在保证连通性的情况下优化网络的功率使用,较少考虑业务QoS指标对网络连接性要求。一种基于业务需求的拓扑控制算法被提出,在拓扑控制算法中引入业务QoS指标,如时延、带宽等。通过理论分析和计算机仿真结果表明,该算法对有QoS要求的业务有较好的支持。     

Cluster-Based Autoconfiguration for Mobile Ad hoc Networks

IP address autoconfiguration of mobile nodes is highly desirable in the practical usage of most mobile ad hoc networks (MANETs). This paper proposes cluster-based autoconfiguration, a novel approach for the efficient address autoconfiguration of MANETs. The cluster structure derived from clustering techniques is used to manage address assignment and conflict resolution. By introducing the concept of virtual address agents (AAs), the proposed approach can be applicable to many existing clustering protocols. Finally, analysis and simulation demonstrate that the proposed scheme outperforms the previous autoconfiguration approaches.

Joint Design of Routing and Medium Access Control for Hybrid Mobile Ad Hoc Networks

Efficient routing and medium access control (MAC) are very important for Mobile Ad hoc Networks (MANETs). Most existing routing and MAC protocols consider homogeneous ad hoc networks, in which all nodes are modeled as the same, i.e., they have the same communication capabilities and characteristics. Although a homogeneous network model is simple and easy to analyze, it misses important characteristics of many realistic MANETs such as military battlefield ad hoc networks. In addition, a homogeneous ad hoc network suffers from poor performance and scalability. In many ad hoc networks, multiple types of nodes do co-exist; and some nodes have larger transmission power, higher transmission data rate, and better processing capability, are more reliable and robust than other nodes. Hence, a hybrid network model is more realistic and provides many advantages for designing better routing and MAC protocols. In this paper, we present a new routing protocol called Hybrid Routing, which is specifically designed for hybrid MANETs. In addition, a novel MAC protocol is jointly designed for hybrid MANETs. Extensive simulations demonstrate that the proposed routing MAC protocols have very good performance.

Internet Connectivity for Ad Hoc Mobile Networks

The growing deployment rate of wireless LANs indicates that wireless networking is rapidly becoming a prevalent form of communication. As users become more accustomed to the use of mobile devices, they increasingly want the additional benefit of roaming. The Mobile IP protocol has been developed as a solution for allowing users to roam outside of their home networks while still retaining network connectivity. The problem with this solution, however, is that the deployment of foreign agents is expensive because their coverage areas are limited due to fading and interference. To reduce the number of foreign agents needed while still maintaining the same coverage, ad hoc network functionality can cooperate with Mobile IP such that multihop routes between mobile nodes and foreign agents can be utilized. In this work, we present a method for enabling the cooperation of Mobile IP and the Ad hoc On-Demand Distance Vector (AODV) routing protocol, such that mobile nodes that are not within direct transmission range of a foreign agent can still obtain Internet connectivity. In addition, we describe how duplicate address detection can be used in these networks to obtain a unique co-located care-of address when a foreign agent is not available.     

Stimulating Node Cooperation in Mobile Ad hoc Networks

Mobile Ad hoc Networks (MANETs) rely on the cooperation of nodes for packet routing and forwarding. Much of the existing work in MANETs assume that mobile nodes (possibly owned by selfish users) will follow prescribed protocols without deviation. However, a user may misbehave due to several advantages resulting from noncooperation, the most obvious being power saving. As such, the network availability is severely endangered. Hence, enforcing the cooperation among nodes becomes a very important issue. Several different approaches have been developed to detect non-cooperative nodes or deal with the non-cooperative behavior of mobile nodes in MANETs. These protocols are first surveyed in details in this paper. It is found that the proposed approaches have several concerns that prevent them from really enforcing the node cooperation in MANETs. Thus, a new scheme that can stimulate and also enforce nodes to cooperate in a selfish ad hoc environment is presented. We also present a mechanism to detect and exclude potential threats of selfish mobile nodes. The simulation results indicate that by using the proposed scheme, MANETs can be robust against nodes’ misbehaving and the performance of the network is enhanced many folds when compared to other existing schemes.

Ad hoc网络功率控制策略研究

文中首先介绍了移动Ad hoc网络及其主要特点，分析了该网络的主要缺陷，以及功率问题对Ad hoc网络性能的影响。并简单阐述了功率控制策略的分类及主要思想，介绍了几种典型的功率控制算法和策略，并比较了其优缺点。文中最后提出了今后功率控制策略的主要发展方向。     

移动自组织网路由稳定性分析

针对移动自组织网络中的路由建立和维护问题,研究了衡量路由稳定性的准则,以节点的不确定性特征作为路由选择的标准,提出了基于局部拓扑结构变化熵度量的稳定路由选择策略,并在此基础上设计了一种稳定路由协议。通过NS-2仿真软件对路由选择策略和路由协议进行了验证,仿真结果表明所提出的稳定路由选择策略和路由协议能够有效地提高移动自组织网络的性能。     

Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks

Geocasting is a variation on the notion of multicasting. A geographical area is associated with each geocast, and the geocast is delivered to the nodes within the specified geographical area. Thus, geocasting may be used for sending a message that is likely to be of interest to everyone in a specified area. In this paper, we propose three geocasting protocols for ad hoc networks, obtained as variations of a multicast flooding algorithm, and then evaluate these approaches by means of simulations. Proposed geocasting algorithms attempt to utilize physical location information to decrease the overhead of geocast delivery.     

ABRP: Anchor-based Routing Protocol for Mobile Ad Hoc Networks

Ad hoc networks, which do not rely on any infrastructure such as access points or base stations, can be deployed rapidly and inexpensively even in situations with geographical or time constraints. Ad hoc networks are attractive in both military and disaster situations and also in commercial uses like sensor networks or conferencing. In ad hoc networks, each node acts both as a router and as a host. The topology of an ad hoc network may change dynamically, which makes it difficult to design an efficient routing protocol. As more and more wireless devices connect to the network, it is important to design a scalable routing protocol for ad hoc networks. In this paper, we present Anchor-based Routing Protocol (ABRP), a scalable routing protocol for ad hoc networks. It is a hybrid routing protocol, which combines the table-based routing strategy with the geographic routing strategy. However, GPS (Global Positioning System) (Kaplan, Understanding GPS principles and Applications, Boston: Artech House publishers, 1996) support is not needed. ABRP consists of a location-based clustering protocol, an intra-cell routing protocol and an inter-cell routing protocol. The location-based clustering protocol divides the network region into different cells. The intra-cell routing protocol routes packets within one cell. The inter-cell routing protocol is used to route packets between nodes in different cells. The combination of intra-cell and inter-cell routing protocol makes ABRP highly scalable, since each node needs to only maintain routes within a cell. The inter-cell routing protocol establishes multiple routes between different cells, which makes ABRP reliable and efficient. We evaluate the performance of ABRP using ns2 simulator. We simulated different size of networks from 200 nodes to 1600 nodes. Simulation results show that ABRP is efficient and scales well to large networks. ABRP combines the advantages of multi-path routing strategy and geographic routing strategy—efficiency and scalability, and avoids the burden—GPS support.     

自组织网中的Anycasting研究

移动无线自组织网络正成为研究的热点,最近在网络通信中提出了一种为任播(anycasting)的通信模式,这里介绍了自组织网中任播的概念以及应用,说明了如何在网络层通过路由实现任播功能。     

Compromise‐Resistant Pairwise Key Establishments for Mobile Ad hoc Networks

This letter presents a pairwise key establishment scheme that is robust against the compromise of nodes in mobile ad hoc networks. Each node establishes local keys with its neighbor nodes that are at most three hops away at network boot‐up time. When any two nodes establish a pairwise key, they receive the secret information from the nodes on the route between them, and construct the pairwise key using the secret information. Here, the local keys are utilized by the nodes on the route to send the secret information securely. The simulation results have proven that the proposed scheme provides better security than the key pre‐distribution‐based scheme.     

On Address Privacy in Mobile Ad Hoc Networks

The network addresses of principals in a mobile ad hoc network (MANET) are conventionally assumed to be public information. This may cause devastating consequences for MANETs deployed in hostile environments. For example, attackers can easily locate a target principal based his known network address and then launch a pinpoint attack. This paper identifies address privacy as a new security requirement to prevent attackers from ascertaining network addresses of MANET principals. We further present Swarms, the first solution to satisfying this requirement. Swarms eliminates the conventionally explicit one-on-one mappings between MANET principals and network addresses and allows any two principals to communicate while blind to each other’s address. We quantitatively measure the address privacy offered by Swarms via an entropy-based information-theoretic metric.