Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Germany Madhu Sudan Microsoft Research, Cambridge, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
6221
Gopal Pandurangan V. S. Anil Kumar Gu Ming Yunhao Liu Yingshu Li (Eds.)
Wireless Algorithms, Systems, and Applications 5th International Conference, WASA 2010 Beijing, China, August 15-17, 2010 Proceedings
13
Volume Editors Gopal Pandurangan Nanyang Technological University Singapore E-mail:
[email protected] V. S. Anil Kumar Virginia Tech Blacksburg, VA, USA E-mail:
[email protected] Gu Ming Tsinghua University Beijing, China E-mail:
[email protected] Yunhao Liu Hong Kong University of Science and Technology Kowloon, Hong Kong E-mail:
[email protected] Yingshu Li Georgia State University Atlanta, GA 30303, USA E-mail:
[email protected]
Library of Congress Control Number: 2010931794 CR Subject Classification (1998): F.1, F.2, D.1, D.2, D.4, C.2, C.4, H.4 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues ISSN ISBN-10 ISBN-13
0302-9743 3-642-14653-8 Springer Berlin Heidelberg New York 978-3-642-14653-4 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. springer.com © Springer-Verlag Berlin Heidelberg 2010 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper 06/3180
Preface
Over the past decade, signficant advances in wireless communication and computing technologies have led to the proliferation of reliable and ubiquitous infrastructure and infrastructureless wireless networks all over the world, as well as a diverse range of new applications, such as mobile social networking, and the surveillance and protection of critical infrastructures and environments. At the same time, these applications have raised new challenges ranging from the theoretical foundations of these systems, algorithms and protocol design, security and privacy to rigorous and systematic design and evaluation methodologies and new architectures for next-generation systems. The annual International Conference on Wireless Algorithms, Systems, and Applications (WASA) provides a forum for researchers and practitioners worldwide to exchange ideas, share new findings, and discuss challenging issues for the current and next-generation wireless networks. Past WASA conferences were held in Xian (2006), Chicago (2007), Dallas (2008), and Boston (2009). WASA 2010, the 5th WASA conference, took place at the Beijing Wenjin International Hotel in Beijing during August 15–17, 2010. Each submission was reviewed by at least three Program Committee members, who in some cases were assisted by external referees. Following a rigorous review process, 29 (19 regular and 10 short) papers were selected for presentation at the conference. The best paper award was given to the paper titled “Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs” by Wei Li, Yong Cui, Shengling Wang, and Xiuzhen Cheng. Four workshops were also organized along with WASA 2010: the Workshop on the Security of Wireless and Ad-hoc Networks (SWAN) 2010, the Workshop on Data Management and Network Control in Wireless Networks (DMNC), the First Workshop on Radar and Sonar Sensor Networks (RSSN), and the First Workshop on Compressive Sensing for Communications and Networking (CSCN). Eighteen papers from these workshops also appear in these proceedings. We thank the respective workshop organizers for their efforts in organizing these workshops and contributing to the success of the WASA 2010 conference. We thank all the authors for submitting their papers to the conference. We also thank all the members of the Program Committee and external referees for their help in completing the reviewing process, especially under the tight time constraints. We are grateful to the members of the Steering Committee for their involvement, encouragement, and help throughout this process.
VI
Preface
Finally, many other people contributed to the success of WASA 2010 directly and indirectly. Even though their names cannot be listed here because of space limitation, we owe them our gratitude. August 2010
Gopal Pandurangan V.S. Anil Kumar Gu Ming Yunhao Liu Yingshu Li
Organization
Honorary General Chair Sun JiaGuang
Tsinghua University, China
General Co-chairs Gu Ming Yunhao Liu
Tsinghua University, China Hong Kong University of Science and Technology, China
Program Committee Co-chairs Gopal Pandurangan Anil Vullikanti
Nanyang Technological University, Singapore and Brown University, USA Virginia Tech, USA
Registration Co-chair Min Song
Old Dominion University, USA
Local Arrangements Co-chairs Zhiguo Wan Jizhong Zhao
Tsinghua University, USA Xi’An Jiaotong University, China
Publicity Co-chairs Jen-Yeu Chen Qilian Liang
National Dong-Hwa University, Taiwan University of Texas at Arlington, USA
Workshop Co-chairs Costas Busch Xiuzhen Cheng
Louisiana State University, USA George Washington University, USA
Publication Co-chair Yingshu Li
Georgia State University, USA
VIII
Organization
Steering Committee Peng-Jun Wan Xiuzhen Cheng Wei Zhao Ty Znati
Illinois Institute of Technology, USA (Chair) The George Washington University, USA University of Macau, China National Science Foundation, USA
Program Committee Members John Augustine Nanyang Technological University, Singapore Costas Busch Louisiana State University, USA Jiannong Cao Hong Kong Polytechnic University, China Jen-Yeu Chen National Dong-Hwa University, Taiwan Susan Cheng George Washington University, USA Yong Cui Tsinghua University, China Sajal Das NSF and University of Texas - Arlington, USA Amitabha Ghosh University of Southern California, USA Sukumar Ghosh University of Iowa, USA Seth Gilbert EPFL, Switzerland Chuanhe Huang Wuhan University, China Anura Jayasumuna Colorado State University, USA Krishna Kant Intel and NSF, USA Maleq Khan Virginia Tech, USA Bhaskar Krishnamachari University of Southern California, USA Wonjun Lee Korea University, Korea Deying Li Renmin University of China, China Minming Li City University of Hong Kong, China Benyuan Liu University of Massachusetts - Lowell, USA Wei Lou Polytechnic University of Hong Kong, China Madhav Marathe Virginia Tech, USA Frederique Oggier Nanyang Technological University, Singapore Marimuthu Palaniswami University of Melbourne, Australia Christos Papadopoulos Colorado State University, USA Srinivasan Parthasarathy IBM Research, USA Sriram Pemmaraju University of Iowa, USA S.S. Ravi SUNY at Albany, USA Michael Segal Ben Gurion University, Israel Yi Shi Virginia Tech, USA Violet Syrotiuk Arizona State University, USA Jian Tan Ohio State University, USA Bharadwaj Veeravali National University of Singapore, Singapore Peng-Jun Wan Illinois Institute of Technology, USA Amy Wang Tsinghua University, China Qing Wang IBM Research, China Kui Wu University of Victoria, Canada Xinbing Wang Shanghai Jiaotong University, China
Organization
IX
Workshop Committee on the Security of Wireless and Ad-hoc Networks Costas Busch Bo Sheng Haodong Wang Hui Chen Xiuzhen Cheng Guevara Noubir Chiu C. Tan Lei Xie Kai Xing Shuhui Yang
Louisiana State University, USA (General Chair) Northeastern University, USA (Workshop Program Co-chair) Virginia State University, USA (Workshop Program Co-chair) Virginia State University, USA George Washington University, USA Northeastern University, USA College of William and Mary, USA Nanjing University, China University of Science and Technology of China, China Purdue University at Calumet, USA)
Workshop Committee on Data Management and Network Control in Wireless Networks Jinshu Su Wei Cheng Nan Zhang Hongyang Chen Tingjian Ge Mikyung Kang Murat Kantarcioglu Yujun Liu Wei Peng Guangming Song Chiu C. Tan Lingyu Wang Kai Xing Mira Yun
National University of Defense Technology, China (General Chair) The George Washington University, USA (Workshop Program Co-chair) The George Washington University, USA (Workshop Program Co-chair) University of Tokyo, Japan University of Kentucky, USA ISI, University of Southern California, USA University of Texas at Dallas, USA Academy of Armored Forces Engineering, China National University of Defense Technology, China Southeast University, China College of William and Mary, USA Concordia University, Canada University of Science and Technology of China, China The George Washington University, USA
X
Organization
Workshop Committee on Radar and Sonar Sensor Networks Jing Liang Qingchun Ren Scott C.-H. Huang Ting Jiang Qilian Liang Sherwood W. Samn Lingming Wang Xinsheng Xia Liang Zhao Zheng Zhou
University of Texas at Arlington, USA (Workshop Program Co-chair) Microsoft, Seattle, USA (Workshop Program Co-chair) City University of Hong Kong, Hong Kong Beijing University of Posts and Telecommunications, China University of Texas at Arlington, USA Air Force Research Laboratory/RHX, San Antonio, USA iBiquity Digital Corporation, Basking Ridge, New Jersey, USA Tellabs Inc, New Jersey, USA Airvana Inc., Chelmsford, Massachusetts, USA Beijing University of Posts and Telecommunications, China
Workshop Committee on Compressive Sensing for Communications and Networking Jing Liang Dechang Chen
Qilian Liang Xiuzhen Cheng Ting Jiang Qingchun Ren Sherwood W. Samn LingmingWang Xinsheng Xia Liang Zhao Zheng Zhou
University of Texas at Arlington, USA (General Chair) Uniformed Services University of the Health Sciences, USA (Workshop Program Co-chair) University of Texas at Arlington, USA (Workshop Program Co-chair) George Washington University, USA Beijing Univerisity of Posts and Telecommunications, China Microsoft, Seattle, USA Air Force Research Laboratory/RHX, Texas, USA iBiquity Digital Corporation, Basking Ridge, New Jersey, USA Tellabs Inc., New Jersey, USA Airvana Inc., Chelmsford, Massachusetts, USA Beijing University of Posts and Telecommunications, China
Organization
External Referees Dilum Bandara Andrew D. Berns Wei Cheng Dulanjalie Dhanapala Fei Huang
Yuan Le Jia Liu Guanhong Pei Mohan Raj Sasanka Roy
Sponsoring Institution Tsinghua University
Vaishali Sadaphal Sushant Sharma Amin Teymorian Yan Wu Zhao Zhao
XI
Table of Contents
Topology Control and Coverage Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Haisheng Tan, Yuexuan Wang, Xiaohong Hao, Qiang-Sheng Hua, and Francis C.M. Lau
1
Heuristic Algorithms for Constructing Connected Dominating Sets with Minimum Size and Bounded Diameter in Wireless Networks . . . . . . Jiguo Yu, Nannan Wang, and Guanghui Wang
11
Energy-Efficient Algorithm for the Target Q-coverage Problem in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hui Liu, Wenping Chen, Huan Ma, and Deying Li
21
Approaching the Optimal Schedule for Data Aggregation in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pei Wang, Yuan He, and Liusheng Huang
26
Theoretical Foundations Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wei Li, Yong Cui, Shengling Wang, and Xiuzhen Cheng
36
Minimum CDS in Multihop Wireless Networks with Disparate Communication Ranges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lixin Wang, Peng-Jun Wan, and Frances Yao
47
Minimum Edge Interference in Wireless Sensor Networks . . . . . . . . . . . . . . Trac N. Nguyen, Nhat X. Lam, D.T. Huynh, and Jason Bolla Maximum Weighted Independent Set of Links under Physical Interference Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xiaohua Xu, Shaojie Tang, and Peng-Jun Wan
57
68
Energy-Aware Algorithms and Protocol Design A QoS-Guaranteed Energy-Efficient Packet Scheduling Algorithm for WiMax Mobile Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hung-Cheng Shih and Kuochen Wang
75
XIV
Table of Contents
Minimum Energy Cost k -barrier Coverage in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Huiqiang Yang, Deying Li, Qinghua Zhu, Wenping Chen, and Yi Hong On the Performance of Distributed N -Cooperation Power Allocation via Differential Game in Cognitive Radio System . . . . . . . . . . . . . . . . . . . . . Shunxi Gao, Long Zhang, Suqin Fan, Wei Huang, Qiwu Wu, and Yu Deng Energy-Efficient Restricted Greedy Routing for Three Dimensional Random Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minsu Huang, Fan Li, and Yu Wang
80
90
95
Wireless Sensor Networks and Applications Adaptive Energy and Location Aware Routing in Wireless Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hong Fu, Xiaoming Wang, and Yingshu Li
105
Utilizing Temporal Highway for Data Collection in Asynchronous Duty-Cycling Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tao Chen, Deke Guo, Honghui Chen, and Xueshan Luo
110
The Impact of Reader to Tag Collision on RFID Tag Identification . . . . . Yiyang Zhao, Weijun Hong, S.C. Cheung, and Shufang Li
115
A Desynchronization Tolerant RFID Private Authentication Protocol . . . Qingsong Yao, Yong Qi, Ying Chen, and Xiao Zhong
120
Study of Joint Routing and Wireless Charging Strategies in Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zi Li, Yang Peng, Wensheng Zhang, and Daji Qiao
125
Page Size Optimization for Code Dissemination in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wei Dong, Xi-bin Zhao, and Min Xi
136
Dynamic Routing Algorithm for Priority Guarantee in Low Duty-Cycled Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Guodong Sun and Bin Xu
146
Applications and Experimentation Heterogeneity of Device Contact Process in Pocket Switched Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ye Tian and Jiang Li
157
Table of Contents
XV
Delay Minimization of Tree-Based Neighbor Discovery in Mobile Robot Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heejun Roh, Kyunghwi Kim, and Wonjun Lee
167
Two-Stage Target Locating Algorithm in Three Dimensional WSNs under Typical Deployment Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lei Mao, Junzhao Du, Hui Liu, Deke Guo, Xing Tang, and Ning Wei
172
Scheduling and Channel assignment Interference Analysis for FH-Based Multi-radio Wireless Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Davis Kirachaiwanich and Qilian Liang Interference-Aware Gossiping Scheduling in Uncoordinated Duty-Cycled Multi-hop Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xianlong Jiao, Wei Lou, Xiaodong Wang, Junchao Ma, Jiannong Cao, and Xingming Zhou
182
192
A Game Theoretic Approach to Multi-radio Multi-channel Assignment in Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Devu Manikantan Shila, Yu Cheng, and Tricha Anjali
203
PAPR Analysis for SOFDM and NC-SOFDM Systems in Cognitive Radio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xue Li, Chi Zhou, Xiangqian Zhou, Zhiqiang Wu, and Bing Xie
209
Coding, Information Theory and Security Application of Compressed Sensing for Secure Image Coding . . . . . . . . . . Gesen Zhang, Shuhong Jiao, and Xiaoli Xu
220
Efficient Wireless Broadcasting Using Onion Decoding . . . . . . . . . . . . . . . . Pei Wang, Qunfeng Dong, Mingjun Xiao, and Liusheng Huang
225
A Spectrally Efficient Anti-Jamming Technique Based on Message Driven Frequency Hopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lei Zhang, Jian Ren, and Tongtong Li
235
Security of Wireless and Ad-Hoc Networks Secure RFID Application Data Management Using All-Or-Nothing Transform Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Namje Park and Youjin Song
245
Prevention of Wormhole Attacks in Mobile Ad Hoc Networks by Intrusion Detection Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ming-Yang Su and Kun-Lin Chiang
253
XVI
Table of Contents
Data Management and Network Control in Wireless Networks A Publicly Verifiable Encryption Scheme with Short Public/Private Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yujun Liu, Yonggang Cui, and Limin Liu
261
Algorithm on Self-organization of Wireless or Connectionless Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zhen Shen, Sheng Qiang, and Dong-yun Yi
266
A Strongly Partitioned Operating System Model for Data Link Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xiaoming Tang, Yuting Zhao, Yinjuan Li, and Yujun Liu
274
Twin Hybrid ElGamal Encryption over Signed Quadratic Residue Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yonggang Cui and Yujun Liu
282
Extra Slot Allocation for Fair Data Collection in the Slot-Based Grid Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Junghoon Lee and Gyung-Leen Park
287
An Efficient Multipath Existence Checking Scheme for Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Feng Wei, Yingchang Xiang, and Bowu Zhang
291
Data Collection Scheme for Two-Tier Vehicular Sensor Networks . . . . . . . Junghoon Lee and Mikyung Kang
295
Radar and Sonar Sensor Networks Energy Efficient Water Filling Ultra Wideband Waveform Shaping Based on Radius Basis Function Neural Networks . . . . . . . . . . . . . . . . . . . . Weixia Zou, Bin Li, Zheng Zhou, and Shubin Wang An Introduction to Bayesian Techniques for Sensor Networks . . . . . . . . . . Bin Liu Fuzzy C-Means Clustering Based Robust and Blind Noncoherent Receivers for Underwater Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . Bin Li, Zheng Zhou, Weixia Zou, and Shubin Wang Research on Enhanced Spectrum Efficiency for BWA Networks . . . . . . . . Xu-hui Wang and Cheng-lin Zhao
299 307
314 322
Table of Contents
XVII
Compressive Sensing for Communications and Networking Improved Channel Estimation Based on Compressed Sensing for Pulse Ultrawideband Communication System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dejian Li, Zheng Zhou, Feng Zhao, Weixia Zou, and Bin Li Compressive Sensing Using Singular Value Decomposition . . . . . . . . . . . . . Lei Xu and Qilian Liang The Wideband Spectrum Sensing Based On Compressed Sensing and Interference Temperature Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ting Jiang and Shijun Zhai
330 338
343
The Applications of Compressive Sensing to Radio Astronomy . . . . . . . . . Feng Li, Tim J. Cornwell, and Frank De hoog
352
Compressive Sensing for Autoregressive Hidden Markov Model Signal . . . Ji Wu, Qilian Liang, and Zheng Zhou
360
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
365
Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks Haisheng Tan1 , Yuexuan Wang2 , Xiaohong Hao2 , Qiang-Sheng Hua1 , and Francis C.M. Lau1 1 2
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong, China Institute for Theoretical Computer Science, Tsinghua University, Beijing, 100084, China
Abstract. Coverage is critical for wireless sensor networks to monitor a region of interest and to provide a good quality of service. In many application scenarios, full coverage is required, which means every point inside the region (excluding the obstacles) must be covered by at least one sensor. The problem of using the minimum number of sensors to achieve full coverage for an arbitrary region with obstacles is NP-hard. Most existing coverage methods, such as contour-based ones, simply place sensors along the boundaries to cover the holes that are near the obstacles and the region boundary. These methods are inefficient especially when the obstacles or the region are irregular. In this paper, based on computational geometry, we design a full coverage method, which accurately finds the uncovered holes and places sensors efficiently for both the regular and irregular obstacles and regions. Specifically, we show that the more irregular the obstacles and the region are, the more sensors our method can save. Keywords: Wireless sensor networks, Coverage, Obstacles, Computational Geometry.
1
Introduction
Wireless sensor networks (WSNs) have been applied extensively in military and civilian applications, and health care, for such purposes as environmental monitoring, intrusion detection, cancer monitoring, and smart agriculture [1]. Coverage is one of the fundamental issues in WSNs. It is measured by how well the region can be monitored and certain services can be provided. Paper [3] studies how to place disks to fully cover a plane. The authors prove that it is asymptotically optimal, in terms of the number of disks used, to place disks
The work presented in this paper was supported in part by Hong Kong RGC-GRF grants (7136/07E and 714009E), the National Basic Research Program of China Grant Nos. 2007CB807900, 2007CB807901, the National Natural Science Foundation of China Grant Nos. 60604033,60553001, and the Hi-Tech research and Development Program of China Grant No. 2006AA10Z216.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 1–10, 2010. c Springer-Verlag Berlin Heidelberg 2010
2
H. Tan et al.
Fig. 1. The optimal placement pattern on a plane
Fig. 2. Coverage of a sensor in a finite rectangle with an obstacle (the gray area is covered)
on the vertices of equilateral triangles (Figure 1). Several other optimal deployment patterns have also been proposed to achieve full coverage and k-connectivity (k ≤ 6) on a plane in [4]. The Art Gallery problem [14] studies how to guard a gallery with the minimum number of cameras, where a location is guarded as long as there is line-of-sight from a camera. In this paper, in addition to the constraint of the limited sensing radius (rs ), the coverage of a sensor (s) is also affected by obstacles and the region boundary (Figure 2). The problem of using the minimum number of sensors to achieve full coverage for a region with obstacles has been proved to be NP-hard [5]. Paper [2] categorizes the approaches for coverage into three groups: force based [6,7], grid based [4,8,13], and computational geometry based [10,11,12]. The authors of [7] propose a virtual force algorithm (VFA) to enhance an initial random placement over a region with obstacles. Their method extremely depends on the sensors’ mobility and energy. In [9], an efficient algorithm is designed for a √robot to place sensors amid obstacles. Paper [12] deploys sensors with distance 2rs along the boundaries of obstacles and the region. Then Delaunay triangulation is applied to determine the positions for additional sensors for full coverage. The whole region is divided into single-row and multi-row regions in [13]; besides full coverage, the authors also guarantee network connectivity. In order to cover the holes, they deploy sensors along the boundaries of obstacles and the region with a constant distance based on a relationship between rs and the sensor’s communication radius rc . To handle areas near obstacles and the region boundary, existing methods for stationary sensors [9,12,13] would simply place sensors along the boundaries with constant distances. We call these methods contour-based. To achieve full coverage, contour-based methods are effective for simple regular regions and obstacles, such as where the boundaries are long straight lines. However, for obstacles and regions that are arbitrarily irregular, such as when there are comb-shaped boundaries, these methods become inefficient. Without considering the specific shapes of boundaries, they may not produce full coverage unless additional sensors are placed at each turning point on the boundaries. In fact, even the best results by contour-based methods that place sensors with dynamic distances can be inefficient (Figure 3). In this paper, in view of the inefficiency of existing deployment methods when handling irregular boundaries, we consider the shapes of boundaries explicitly. Using computational geometry techniques, our algorithms can find the holes accurately and cover them efficiently. Our method performs excellently for both regular and irregular obstacles and regions, including some extremely irregular
Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks
(a)
(b)
3
(c)
Fig. 3. Coverage near a part of the boundary: (a) the contour-based placement with a constant distance: 5 sensors, (b) the best for the contour-based methods: 2 sensors, (c) the optimal placement: 1 sensor
ones. The rest of the paper is organized as follows: in Section 2, we define the models and the problem; Section 3 describes our placement method; Section 4 gives the analysis and experimental results; Section 5 discusses some variations of our method; Section 6 concludes the paper and points out some future work.
2
Problem Definition
The region of interest, denoted as A, is a 2D finite area with an arbitrary boundary and contains arbitrary obstacles. There are no isolated subregions, and the obstacles have no holes inside themselves. The area that needs to be covered is the region minus the obstacles. Both the region and obstacles are modeled as simple polygons of finite sizes on the 2D plane. The sensors are stationary and homogenous with a fixed sensing radius rs . Here we assume the binary sensor model: the sensing range of s is a disk centered at s with a radius of rs ; a point is covered by a sensor if it is within a distance of rs and there is a line of sight from the sensor. The coverage of a sensor with obstacles, Cov(s), may be a partial disk (Figure 2). If there are n obstacles inside A, and the obstacle i occupies an area Obsi , the total area occupied can be denoted as O = ∪i∈[1,n] Obsi . And Cov(s) is defined as: Cov(s) = {u ∈ A − O| u − s ≤ rs , ku + (1 − k)s ∈ A − O, ∀k ∈ [0, 1]} Full coverage for a sensing region A means every point in the area A−O must be within Cov(s) of at least one sensor s. Our sensor placement problem is defined as placing the minimum number of sensors in a finite region with arbitrary boundary and obstacles to achieve full coverage.
3
Sensor Placement Algorithms
To achieve full coverage for a region A, our method works in four procedures: 1) to deploy a regular pattern over the region; 2) to find the uncovered holes; 3) to partition the holes into triangulations; and 4) to place sensors to cover the holes. In the following, we explain these procedures in details. 3.1
Optimal Regular Pattern Deployment (ORPD)
We firstly deploy the regular pattern in Figure 1, which is optimal for covering a plane, for the region A disregarding obstacles and the region boundary. The
4
H. Tan et al.
starting position can be randomly chosen at (x, y) ∈√A. The sensors are placed at (x, y) as well as its six neighbors with distance 3rs in the pattern. Note that we assume a sensor can be ‘placed’ inside an obstacle or outside A in this procedure. For each sensor, as long as it is in A, sensors are added at its neighbor locations. We continue doing this until every neighbor of the sensors inside A is occupied by one sensor. We use three lists Lobs , Lin and Lout to keep track of the sensors placed inside obstacles O, inside A − O, and outside A respectively. Figure 4 gives an example.
Fig. 4. The region after Fig. 5. Finding a hole the ORPD: the white area (gray areas are hole(s)) is A − O
3.2
Fig. 6. Holes are found and merged (gray areas are holes)
Finding Holes
After the ORPD procedure, there may be some subareas near an obstacle or the region boundary, called holes, that are not covered, which is due to: 1) the lack of sensors: some sensors are placed into obstacles or outside the region, such as s1 and s2 in Figure 4; 2) blocking: some sensors’ coverage is blocked by obstacles or the region boundary, such as s3 and s4 . The arbitrary shapes of the obstacles and the region make it difficult to cover these holes efficiently. Our method overcomes this by firstly accurately finding the holes. The ORPD procedure can be regarded as a tessellation of regular hexagons with edge rs inscribed in the circles (Figure 1). Therefore, we model the sensing range of a sensor s by the regular hexagon, and denote it as H(s). Then, it is easy to find the holes caused by the lack of sensors. For each sensor deployed inside obstacles or outside A, the hole of s, hole(s) is the overlap, Hin (s), between H(s) and A − O. It is not as easy to calculate the holes caused by blocking (Figure 5). For a sensor deployed inside A − O, we also first calculate Hin (s). If Hin (s) is nonempty, holes may exist inside it. We denote the perimeter of an area as P (area). P (Hin (s)) consists of PH (s), the blue lines in Figure 5, and PA (s), the red lines excluding the intersection points with PH (s). Note that PH (s) is a part of P (H(s)), and PA (s) is a part of P (A − O). Next, we draw directed lines from s to each vertex v of Hin (s) and extend them until reaching P (H(s)). The line → − sv crosses P (Hin (s)) at points p1 , p2 , ..., pn (n > 0) listed in increasing distances → from s. The segment of − sv inside H(s) is denoted as (s, p1 , p2 , ..., pn ). We set p0 = s and obtain Theorem 1 for finding the vertices of hole(s). Theorem 1. Given (s, p1 , p2 , ..., pn ), for ∀k ∈ [1, n), pk is a vertex of hole(s) if and only if one of the following conditions is satisfied:
Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks
5
1) pk+1 ∈ PH (s) 2) pk+1 ∈ PA (s) AND pk +p2 k+1 ∈ Hin (s) p +p 3) pk−1 ∈ PA (s) AND k 2 k−1 ∈ Hin (s) 4) pk−1 ∈ PA (s) AND pk+1 ∈ PA (s) For k = n, pn is a vertex of hole(s) if and only if pn ∈ PH (s) and pn−1 = s. → Proof. As each − sv stops at P (H(s)), we can get k = n ⇐⇒ pk ∈ P (H(s)), and k ∈ [1, n) ⇐⇒ pk ∈ PA (s). P (H(s)) − PH (s) is inside obstacles or outside A. Therefore, pn is a vertex of hole(s) if and only if pn ∈ PH (s) and pn−1 is not s. As for k ∈ [1, n), the theorem is proved by enumerating all the cases of the positions of pk , pk−1 and pk+1 as follows: pk PA (s) PA (s) PA (s) PA (s) PA (s) PA (s)
pk−1 s s s PA (s) PA (s) PA (s)
pk+1 pk is a vertex of hole(s) PH (s) True P (H(s))−PH (s) False PA (s) True iff pk +p2 k+1 ∈ Hin (s) PH (s) True P (H(s))−PH (s) True iff pk +p2 k−1 ∈ Hin (s) PA (s) True
As the perimeter of hole(s) can only consist of parts of P (Hin (s)) and segments → on each directed line − sv, we have Theorem 2: →i , i = Theorem 2. Connecting the vertices of hole(s) along P (Hin (s)) and − sv 1, 2, ..., m, where m is the number of vertices in Hin (s), we get hole(s). For a single sensor, hole(s) may comprise a set of subholes. We merge the subholes that share at least a point. For all the sensors placed, we continue merging their holes, and denote the final set of holes as HOLE. According to our finding process, we can see that the holes have good properties: 1) narrow in width: the width of the hole for a single s is no larger than √ rs . After merging, each part of a hole in HOLE has a width no larger than 3rs ; otherwise there must be some sensors inside the hole, which is a contradiction; √ 2) accurate in size: if the sensing range of s is simulated as H(s) of area 3 2 3 rs2 as we do now, HOLE is exactly the uncovered area. Actually the range is a disk √ of area πrs2 . Then hole(s) is at most (π − 3 2 3 )rs2 larger than the real uncovered area in the sensing range of s. Algorithm 1 implements the whole procedure, and Figure 6 gives an example. 3.3
DT-Based Partition of Holes
To cover a hole in HOLE, we partition it into triangles whose edges are no longer than rs , so that a sensor can be placed at any of the three vertices of a triangle. We achieve this by the following three steps: Step 1: Partitioning the long edges. If an edge of the hole is longer than rs , rls − 1 points are added to partition it evenly, such as AB in Figure 7. We treat the newly added points as vertices of the hole.
6
H. Tan et al.
Algorithm 1. Finding Holes Input:the region A, obstacles O, Lin , Lout and Lobs Output: the holes HOLE 1: For each item s ∈ Lout ∪ Lobs do 2: hole(s) = H(s) ∩ (A − O) 3: if hole(s) = ∅, HOLE = HOLE ∪ hole(s) 4: End For 5: For each item s ∈ Lin do 6: Hin (s) = H(s) ∩ (A − O) 7: If Hin (s) = ∅, Then 8: Finding the vertices of hole(s) /* Theorem 1 */ Compute and merge subholes to get hole(s); update HOLE /* Theorem 2 */ 9: End If 10: End For 11: For each pair of items hole1 and hole2 in HOLE 12: if hole1 ∩ hole2 = ∅, hole = hole1 ∪ hole2 and update HOLE 13: End For
Step 2: Applying Delaunay triangulation. We apply DT over the vertices of the hole, and get a triangulation of the hole. Here DT is chosen because 1) it is efficient (O(nlogn) time, where n is the number of vertices), and 2) the minimum angle of all the triangles is maximized thus avoiding skinny triangles [14]. Based on the advantage of DT and the property that our holes are narrow, the triangulation will add no or just a few long edges that need to be handled in next step. Step 3: Partitioning triangles with an edge longer than rs , such as CD in Figure 7. Also, to avoid skinny triangles, we always partition the longest edge among all the triangles. This step stops until all the edges are bounded by rs and we finally get a partition, Thole , over the hole. The partition for a hole from Figure 6 is illustrated in Figure 7. After handling all the holes in HOLE, we get a set of partitions, Tholes , as described in Algorithm 2. 3.4
Placing Sensors to Cover Holes
Based on the partition, full coverage is equivalent to satisfying the requirement that at least one vertex of each triangle in Tholes is placed a sensor. For each Thole in Tholes , we first compute its dual graph, D(Thole ), which has a node v for every triangle t(v) in Thole . Two nodes u and v form an edge if t(v) and t(u) share at least a point. If D(Thole ) is a tree, it is 3-colorable. When performing DFS (Depth-First Search) on the tree, for each v being visited except the root, there must be one or two (when t(v) shares only a vertex with the triangle visited in the last step) free nodes uncolored in t(v). However, in our case, D(Thole ) may be a graph with cycles and not 3-colorable. In order to ensure that every triangle has three different colored vertices, we allow a vertex to be ‘doubly colored’. When performing DFS on the graph, for the last node v in a cycle, the free vertex in t(v) has been colored. We check whether the three vertices of t(v) have had three different colors. If yes, we go on to visit the next node directly; if no, we append the absent color to a colored free vertex and make it doubly colored,
Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks
7
Algorithm 2. DT-based partition of Holes Input: the set of holes HOLE Output: a partition Tholes over HOLE 1: For each hole in HOLE do 2: Initialize an array Lp , a partition Thole and a sorted array Le empty 3: Lp = Lp ∪ vertices of hole 4: For each edge e of hole do /* Step 1 */ add length(e) − 1 points evenly on e and append the points to Lp rs End For /* Step 2 */ 5: Do DT over Lp and store the triangulation of hole to Thole 6: Insert edges in Thole longer than rs to Le in decreasing order of lengths /* Step 3 */ 7: While(Le is nonempty) do 8: add length(e) − 1 points evenly on the first item e and remove it rs 9: For each triangle containing e do connect the points added to the vertex that is not on e; update Thole 10: if there are edges added longer than rs , insert them to Le 11: End For 12: End While 13: Tholes = Thole ∪ Tholes 14: End For
such as the vertex D in Figure 7. After coloring, we choose the smallest group of the vertices with the same color to place our sensors. Because for each cycle in D(Thole ), there is at most one vertex in Thole doubly colored, we have Theorem 3: Theorem 3. For a hole h, if it has n vertices in Th and c cycles in D(Th ), n+c 3 sensors can always fully cover it. After placing sensors to cover all the holes, together with the sensors in Lin , we can get full coverage of the region A (Figure 8).
Fig. 7. Partition a hole into triangles and color the vertices.
4
Fig. 8. Full coverage: red Fig. 9. Cover a rectangle of and green points are sen- long edges: red and green sors points are sensors
Analysis and Experiments
Because of the arbitrary obstacles and the region, to analyze the bounds on the number of sensors for full coverage, we need to use parameters from both the input
8
H. Tan et al.
region and our placement algorithms. For the region A, nv is the number of vertices on P (A − O), and the length of each edge i on P (A − O) is leni . For the holes in HOLE, the number of vertices located on {PH (s)|hole(s) = ∅} is nvph , and = ∅} is nvpa . The number of sensors to the number of vertices on {PA (s)|hole(s) cover HOLE is nch . k is the number of vertices to divide long edges after applying DT over HOLE. Recall that there are no or at most a few edges longer than rs after DT, so k is small. m is the total number of cycles in the dual graphs of Tholes . m is also small and closely related to the shapes and positions of obstacles and the region boundary. The size of Lin is nin , and the number of vertices in Tholes is nvt . Then the number of sensors to achieve full coverage of A is: N = nin + nch ≤ nin + (nvt + m)/3 / ∗ T heorem 3 ∗ / i nvph + nvpa + i ( len rs − 1) + k + m = nin + 3 leni nvph + nv + i ( rs − 1) + k + m ≤ nin + / ∗ nvpa ≤ nv ∗ / 3 area(A − O) area(A − O) √ N≥ = area(H(s)) 3 3rs2 /2
(1) (2) (3) (4)
nin is the asymptotically optimal number of sensors to cover the region excluding i HOLE by the ORPD procedure. nvph approximates to nvpa + i ( len rs − 1) in most cases, and for irregular obstacles and regions, nvph can be much i smaller. So, the upper bound of the sensors for holes is nearly 23 (nv + i ( len rs − 1)). However, for contour-based methods, the sensors placed along boundaries can i − 1), where r is the constant placement distance not larger reach nv + i ( len r √ than 2rs . We carried out experiments to validate the above analysis and to show the effectiveness of our approach for both regular and irregular cases. The example in Figure 8 illustrates the effectiveness of our approach in handling comb-shaped boundaries. Figure 9 is to cover a rectangle, which illustrates the handling of long straight lines. Moreover, we conducted simulations for four types of regions (Figure 10) using three types of sensors with different rs . Figure 11 compares our results with the contour-based ones’. ‘Contour-based-1’ is to first place sensors along the boundaries, and then add extra sensors for full coverage via a nearoptimal placement. ‘Contour-based-2’ applies the ORPD procedure and then places sensors along the boundaries to cover the holes. When executing ORPD in ’Contour-based-2’ and in our method, we try different locations for the first sensor, and choose the one leading to the fewest sensors for full coverage. Greedily, we place the first sensor r2s away from the longest boundary and rotate the regular pattern to fully cover the longest boundary. We can see that the more irregular the obstacles and region are, the more sensors our method can save.
5
Discussion
We have considered only opaque obstacles which neither allow sensors to be deployed inside nor allow the sensing signal to pass through. There exist other
Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks
(a)
(b)
(c)
9
(d)
Fig. 10. Four types of regions: (a) a regular region and obstacles (b) an indoor-like region (c) an outdoor-like region (d) an extremely irregular region and obstacles
Fig. 11. Comparison of the contour-based methods with ours in above 4 regions
kinds of obstacles such as transparent obstacles (ponds are examples) which do not allow sensors placed inside but allow signals to pass through. When the obstacles and region boundary are all transparent, the holes appearing after the ORPD procedure are only those due to the lack of sensors. We can compute Hin (s) for each s ∈ Lout ∪ Lob . For each nonempty Hin (s), we need to add at most 5 sensors to cover it [5]. Setting n = |{s ∈ Lout ∪ Lob |Hin (s) = ∅}|, we have the upper bound of the sensors needed as nin + 5n. Note that the upper bound in [5] is incorrect because it sums up each Hin (s) without considering their positions which are as crucial as their sizes. An example to refute their upper bound is a w × l rectangle with w → 0. In practice, due to the inherent uncertainty of a sensor’s sensing ability, the probabilistic sensor model is more reasonable than the binary model [7]. As full coverage is achieved in our placement, for any point in A − O, there must be at least one sensor s within a distance rs . Therefore, our coverage probability for any β point is not smaller than e−λre , where λ, re and β are parameters in the model. If a higher probability is required, we need to use a virtual sensing radius r instead β of rs , where rs − re ≤ r < rs , so that the probability e−λ(r+re −rs ) is guaranteed. For arbitrary obstacles, the effective coverage of a sensor can be infinitesimal. The number, shapes, sizes as well as relative positions of obstacles make it hard to design and analyze algorithms for full coverage. In practice, obstacles are rarely extremely irregular. Therefore, we may choose to study coverage for a limited number of special sizes and shapes of obstacles. Moreover, instead of full coverage, we may also choose to ignore holes smaller than a certain predefined threshold.
10
6
H. Tan et al.
Conclusion and Future work
In this paper, we propose an efficient full coverage method for a sensing region with arbitrary boundary and obstacles. We achieve this by carefully studying how the obstacles and the region boundary block coverage. The holes arising from an optimal regular pattern deployment are efficiently and accurately calculated. Algorithms based on Delaunay triangulation and 3-coloring are designed to cover these holes. Compared with other methods, the proposed method can achieve full coverage while dramatically saving sensors especially when the region and obstacles are irregular. Besides the extension mentioned in the previous section, future work can be carried out in many directions, such as multiple connectivity and coverage with obstacles, 3D coverage and the surface coverage [15] with obstacles, coverage by mobile and heterogeneous sensors, etc.
References 1. Wu, J.: Handbook on Theoretical & Algorithmic Aspects of Sensor. In: Ad Hoc Wireless, and Peer-to-Peer Networks. Auerbach Publication, US (2006) 2. Aziz, N.A.A., Aziz, K.A., Ismail, W.Z.W.: Coverage Strategies for Wireless Sensor Networks. World Academy of Science, Engineering and Technology 50 (2009) 3. Kershner, R.: The Number of Circles Covering a Set. American Journal of Mathematics 61, 665–671 (1939) 4. Bai, X., Xuan, D., Yun, Z., Lai, T.H., Jia, W.: Complete Optimal Deployment Patterns for Full-Coverage and k-Connectivity (k ≤ 6) Wireless Sensor Networks. In: Proc. of ACM MobiHoc 2008 (2008) 5. Shyam, M., Kumar, A.: Obstacle Constrained Total Area Coverage in Wireless Sensor Networks. CoRR abs/1001.4753 (2010) 6. Howard, A., Poduri, S.: Potential Field Methods for Mobile-Sensor- Network Deployment. In: Bulusu, N., Jha, S. (eds.) Wireless Sensor Networks A System Perspective. Artech House, London (2005) 7. Zou, Y., Chakrabarty, K.: Sensor deployment and target localization based on virtual forces. In: IEEE INFOCOM 2003 (2003) 8. Shen, X., Chen, J., Wang, Z., Sun, Y.: Grid Scan: A Simple and Effective Approach for Coverage Issue in Wireless Sensor Networks. IEEE International Communications Conference, volume: 8, pp. 3480-3484. (2006) 9. Chang, C.Y., Chang, C.T., Chen, Y.C.: Obstacle-Resistant Deployment Algorithms for Wireless Sensor Networks. IEEE Trans. on Veh. Tech. (2009) 10. Wang, G., Cao, G., Porta, T.L.: Movement-Assisted Sensor Deployment. In: IEEE INFOCOM 2004, vol. 4, pp. 2469–2479 (2004) 11. Megerian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.: Worst and Best-Case Coverage in Sensor Networks. IEEE Trans. on Mob. Comput. 4(1), 84–92 (2005) 12. Wu, C.H., Lee, K.C., Chung, Y.C.: A Delaunay Triangulation based method for wireless sensor network deployment. Computer Communications 30 (2007) 13. Wang, Y.C., Hu, C.C., Tseng, Y.C.: Efficient Placement and Dispatch of Sensors in a Wireless Sensor Network. IEEE Trans. on Mob. Comput. 7(2) (2008) 14. Berg, M., Cheong, O., Kreveld, M.V., Overmars, M.: Computational geometry: algorithms and applications, 3rd edn. Springer Press, Heidelberg (2008) 15. Zhao, M.C., Lei, J., Wu, M.Y., Liu, Y., Shu, W.: Surface Coverage in Wireless Sensor Networks. In: IEEE INFOCOM 2009, pp. 109–117 (2009)
Heuristic Algorithms for Constructing Connected Dominating Sets with Minimum Size and Bounded Diameter in Wireless Networks Jiguo Yu1, , Nannan Wang1 , and Guanghui Wang2 1
School of Computer Science, Qufu Normal University, Ri-zhao, Shandong, 276826, P. R. China
[email protected],
[email protected] 2 School of Mathematics, Shandong University, Ji-nan, Shandong, 250100, P.R. China
[email protected]
Abstract. Connected dominating set (CDS) is widely used in wireless networks as a virtual backbone for communication and routing between nodes. In order to measure the quality of a CDS, most researches in this area focus on reducing the size of a CDS, neglecting other important metrics, such as diameter between two communication parties. This paper considers the diameter as a quality factor for CDS construction, and develops two new heuristic algorithms. In particular, the CDS computed by the first algorithm has constant ratios 9 and 3 for its size and diameter, respectively. And that of the second algorithm has constant ratios 5 + ln 10 and 2. Both theoretical analysis and simulation show out the performance of the algorithms.
1
Introduction
Wireless ad-hoc networks are multi-hop, self-organizing autonomous networks, do not rely on any existing or predefined network infrastructure. And terminal nodes randomly dispose. Wireless sensor networks are decentralized distributed systems. Numerous sensors are densely disposed in the monitor region with a random manner. The sensors are used for collecting physical parameters such as light intensity, sound, or temperature. Wireless networks including wireless adhoc networks and wireless sensor networks have been attracting more and more attentions in the recent years and they are being used in a variety of military and civil applications such as battle fields, disaster recoveries, conferences, concerts, environmental detections, health applications and so on.
The work is supported by NNSF (60373012, 10871119) of China, NSF (ZR2009GM009, ZR2009AM013), Promotional Foundation (BS2009DX024) for Middle-aged or Young Scientists, EDRP (J07WH05) of Shandong Province, DRF and UF (XJ0609) of QFNU. The corresponding author.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 11–20, 2010. c Springer-Verlag Berlin Heidelberg 2010
12
J. Yu, N. Wang, and G. Wang
An undirected graph G = (V, E) is usually used to represent a wireless network. V is the set of mobile hosts in the network and E represents all the links in the network. It is assumed that all the hosts are deployed in a 2-D plane and their maximum transmission range R are the same. Thus the resultant topology graph of the network is modeled as an undirected Unit Disk Graph (UDG) [3]. Otherwise, it is a general graph [13]. In the context of graph theory, we call a host as a node. A link between nodes u and v exists if and only if their distance is at most R. Although a wireless network has no physical backbone, many researchers have proposed the concept of virtual backbone infrastructure [5], which organizes a hierarchical structure of ordinary nodes to achieve scalability and efficiency. Finding a connected dominating set (CDS) of a given graph is an effective way for constructing a virtual backbone. In general, a dominating set (DS) of a graph G = (V, E) is a subset V ⊂ V such that each node in V − V is adjacent to at least one node in V . A connected dominating set (CDS) is a dominating set whose induced subgraph is connected. The nodes in the CDS are called the dominators. Other nodes in V are called dominatees. With the help of the CDS, the routing is easier and can adapt quickly to the topology changes, and only the nodes in the CDS need to maintain the routing information. Then the search space for the route is reduced only within the CDS. The construction of a minimum-sized CDS in an UDG is proved to be NP-hard [7]. In order to measure the quality of a CDS, the size of the CDS is the primary concern. However, there exist other important metrics that are also needed to be taken into account. In addition to size, this paper also considers diameter as a metric to evaluate the constructed CDS. The diameter of a given connected graph is the length of the longest shortest paths between a pair of nodes in the graph. Mohammed et al. [12] pointed out that in wireless networks, the probability of message transmission failure often increases when a message is sent through a longer path. The rest of the paper is organized as follows. Section 2 reviews some related works. Section 3 presents our two heuristic algorithms for constructing a CDS, and theoretical analysis shows out the performance of the algorithms. Section 4 gives the results of simulation. Section 5 concludes this paper.
2
Related Works
The idea of using a CDS as a virtual backbone for routing was proposed in [6]. Since then many efforts [1, 2, 4, 8, 11, 12] have been made to design approximations or heuristics for MCDS in wireless networks which focus on devising algorithms to produce a small approximation ratio. However, all of the above works only consider the size of a CDS. The diameter of a CDS which is also an important parameter should be another primary concern when constructing a CDS. In [12], the diameter of a CDS is taken into account. However, the performance ratio of the algorithm is not given. Kim et al. proposed a heuristic algorithm (CDS-BD) for constructing a CDS with bounded diameters in wireless networks [10]. This paper improves the CDS-BD algorithm and develops two heuristics for constructing connected dominating set with minimum size and bounded
Heuristic Algorithms for Constructing Connected Dominating Sets
13
diameter. It also proves that our algorithms have constant performance ratios for the size and diameter of the constructed CDS.
3
Heuristic Algorithms
In order to develop algorithms for wireless networks and give mathematical proofs of their correctness and performance, appropriate models are needed [13]. Let V ⊂ 2 be a set of nodes in the 2-dimensional plane. The Euclidean graph G = (V, E) is called unit disk graph (UDG) if any two nodes are adjacent if only if their Euclidean distance is at most 1. That is, for arbitrary u, v ∈ V , it holds that {u, v} ∈ E ⇔ |u, v| ≤ 1. In other words, two nodes are adjacent if and only if they are within each other’s transmission range. For simplicity, in the following selection of dominators, we use node rank as the deterministic criterion. Define the rank of node u to be an ordered pair of (du , idu ), where du is the node degree and idu is the node ID of u. We say that a node u with rank (du , idu ) has a higher order than a node v with rank (dv , idv ) if du > dv , or du = dv and idu < idv . The new CDS construction algorithms have two phases. First to construct an MIS for the graph G. Then to connect the MIS. The detailed process of the phase 1 is as follows. ——————————————————————————————————– Phase 1: M IS(G) (G = (V, E)) ——————————————————————————————————– /* find an MIS in the following way: */ 1. Choose a root r ∈ V (i.e. using a leader selection algorithm); 2. Compute the hop distance from r to each node (i.e. using breadth first search); 3. Let Vk = {y ∈ V |Hopdist(r, y) = k}, kmax is the maximum k, and Gk is the subgraph of G induced by Vk ; /* Hopdist(x,y) is the hop distance from node x to node y over the shortest path between them. */ 4. Find a maximal independent set(MIS) Ik of Gk for all odd k. Let I be the Ik ; union of Ik for all odd k, thus I = k∈odd
5. Color all nodes of I in black and color every node adjacent to a black in gray; 6. Return I. —————————————————————————————————— Lemma 1. For any unit disk graph G, the size of a maximal independent set is at most 3 ∗ opt + 3, where opt is the size of a minimum connected dominating set. This lemma has been proved in [14], and the bound is tight. Theorem 1. I returned from phase 1 is an MIS of the whole graph G.
14
J. Yu, N. Wang, and G. Wang
Proof. From phase 1, we can see that I =
Ik , that is, I is the union of
k∈odd
Ik for all odd k. Thus I dominates all the nodes of Vk . Furthermore, phase 1 colors every node adjacent to a black in gray, thus all the nodes of Vk−1 are gray. When the phase 1 finishes, each node in V is either black or gray, dominated by I. Therefore, I is an MIS of G. When the phase 1 ends, an MIS I of G is obtained. The next phase is to find the least connectors to connect the nodes in the MIS to form a CDS of G. The main difficulty in lowering the approximation ratio between CDS and MCDS lies in the reduction of connectors used to connect the nodes in the MIS [9]. There are two methods to connect the nodes in I obtained from the phase 1. —————————————————————————————————— Phase 2: CDS(G) (M IS(G), G = (V, E)) —————————————————————————————————— Method 1: /* connect I into a CDS in the following way: */ 1. Suppose k is odd; 2. for k = 1 to kmax do 3. if Ik has i (i ≥ 2) black nodes 4. for m = 2 to i do 5. if there are m black nodes in Ik which have common parent nodes in Vk−1 6. then color the parent node y with highest rank in black; 7. else Each of the m black nodes selects a parent node u with the highest rank in Vk−1 , and colors u in black. Suppose v is u’s parent node with the highest rank in Vk−2 , color v in black; 8. end for 9. else if Ik has only one black node x 10. then color y ∈ Vk−1 in black, which is the neighbor of x with the highest rank; Suppose z is y’s parent node with the highest rank in Vk−2 , color z in black; 11. end if 11. end for 12. Add all black nodes into C; 13. Return C. Method 2: /* connect I into a CDS in the following way: */ 1. Initialize the set of blue nodes S as ∅; 2. while there are more than one connected black-blue components exist do /*A black-blue component is a connected component of the sub-graph induced only by black and blue nodes without considering connections between blue nodes.*/ 3. Choose the vertex v that connects the maximum number of black-blue components, change it’s color from gray to blue;
Heuristic Algorithms for Constructing Connected Dominating Sets
15
4. And set S = S ∪ {v}; 5. end while 6. Return the blue node set S; 7. Denote C as the set of black and blue nodes in V , thus C = I ∪ S; 8. Return C. —————————————————————————————————— Theorem 2. C returned from method1 in phase 2 is a CDS of G. Proof. After phase 1, all the nodes should be black or gray, and all the black nodes (set I) form a dominating set. Now we need to prove that C formed by adding more black nodes to I is connected. As we all know, if a graph is connected, then every node (except the root r) has a path to the root node. Therefore, in order to show C is connected, we now prove by induction that there exists a path from every black node x ∈ V /r to the root r. Let x be a black node in V2i−1 . When i = 1, x is connected to r, since r is the only parent node of x. Assume for i ≤ k, all the black nodes are connected to r. For a black node x ∈ V2(k+1)−1 , we color y ∈ V2k black where y is the highest rank parent node of x’s parent nodes in V2k . Furthermore, y is gray before becoming black, dominated by I2k−1 , that is, y is dominated by a black node z in V2k−1 , thus x is connected with z. Owing to for i ≤ k, all the black nodes are connected to r, thus z is connected to r. Therefore, the black node set C is a CDS of G. Theorem 3. C returned from method2 in phase 2 is a CDS of G. Proof. After phase 1, an MIS I of G is obtained, then I is also a dominating set of G. In the method2, a CDS is constructed by selecting blue nodes to connect the nodes in the MIS I. In this method, we select the node that could connect the maximum number of connected black-blue components together each time, and color the node in blue. A black-blue component is a connected component of the sub-graph induced only by black and blue nodes, without considering connections between blue nodes. Using this heuristic algorithm, we can select the least blue nodes to connect the nodes in I. Finally, the set C of black and blue nodes is a CDS of G. Thus, phase 1 and method1 of the phase 2 constitute the first algorithm for CDS, and phase 1 and method2 of the phase 2 constitute the second algorithm. The following analyzes the performance ratios for the size and diameter of CDS constructed by the two algorithms. Theorem 4. Let set C is the CDS constructed by the first heuristic algorithm, opt is the size of a minimum connected dominating set of G. Then |C| ≤ 9 ∗ opt + 7. Proof. The main idea of the algorithms is first to construct an MIS I of G, then to select connectors for connecting the nodes in I to form a CDS. Therefore, set
16
J. Yu, N. Wang, and G. Wang
C includes the nodes of I and connectors, thus |C| = |I| + |connectors|. From lemma 1, we know that |I| ≤ 3 ∗ opt + 3. Now we consider the size of connectors. If there are α black node groups in I having common parent nodes, and m is the average size of these groups. Then we have |connectors| ≤ 2(α + |I| − mα − 1) = 2(|I| − (m − 1)α − 1),
(1)
|C| = |I| + |connectors| = 3|I| − 2(m − 1)α − 2.
(2)
Suppose the worst happens, that is, none of the black nodes in I has common parent nodes. Then, α = 0. Therefore, |C| = 3|I| − 2.
(3)
Furthermore, |I| ≤ 3 ∗ opt + 3, therefore, |C| ≤ 9 ∗ opt + 7.
(4)
Lemma 2. Let S is the set of blue nodes obtained from method2 in phase 2, opt is the size of a minimum connected dominating set for an Unit Disk Graph G. Then |S| ≤ (2 + ln 10) ∗ opt. This lemma has been proved in [15]. Theorem 5. Let set C is the CDS constructed by the second heuristic algorithm, opt is the size of a minimum connected dominating set of G. Then |C| ≤ (5 + ln 10) ∗ opt + 3. Proof. From the method 2 in the phase 2, we know |C| = |I| + |S|. From the lemma 1, we have |I| ≤ 3 ∗ opt + 3, and from the lemma 2, we have |S| ≤ (2 + ln 10) ∗ opt. Therefore, |C| = |I| + |S| ≤ (5 + ln 10) ∗ opt + 3.
(5)
Theorem 6. In the first algorithm, every black node in Vk is away from root r within a distance of at most Tk , where Ti =
1 3 3 i − , i ∈ (1, 3, 5, · · ·), Ti = i − 1, i ∈ (2, 4, 6, · · ·). 2 2 2
(6)
Proof. Let Di be the distance within which a black node in Vi is away from r. According to the method1, if k is an odd number, then the maximum number of introduced black nodes is 2. Therefore, the distance between a node at level k to a node at level k − 2 is at most 3, i.e. Dk ≤ Dk−2 + 3. Therefore, D1 = 1, D3 ≤ D1 + 3, . . . , Dk ≤ Dk−2 + 3
(7)
Heuristic Algorithms for Constructing Connected Dominating Sets
17
By solving these inequalities, we have: Dk ≤ 3( k2 − 12 ) + D1 = 32 k − 12 .
(8)
If k is an even number, one black node at level k is adjacent to a black node at level k − 1. Thus, Dk ≤ Dk−1 + 1 = 32 (k − 1) −
1 2
+ 1 = 32 k − 1.
Since Ti is the maximum Di , the theorem is true.
(9)
Theorem 7. In the second algorithm, every black node in Vk is away from root r within a distance of at most Tk , where Ti = i, i ∈ (1, 3, 5, · · ·).
(10)
And every blue node in Vk is away from root r within a distance of at most Tk , where Ti = i, i ∈ (2, 4, 6, · · ·). (11) Proof. Let Di be the distance within which a black node in Vi is away from r. According to the method2, if k is an odd number, then the maximum number of introduced connectors is 1. Therefore, the distance between a node at level k to a node at level k − 2 is at most 2, i.e. Dk ≤ Dk−2 + 2. Therefore, D1 = 1, D3 ≤ D1 + 2, . . . , Dk ≤ Dk−2 + 2
(12)
By solving these inequalities, we derive: Dk ≤ k − 1 + D1 = k.
(13)
k is an even number if one blue node is at level k. And one blue node at level k is adjacent to a black node at level k − 1. Thus, Dk ≤ Dk−1 + 1 = k − 1 + 1 = k. Since Ti is the maximum Di , the theorem is true.
(14)
Theorem 8. Let D∗ be the diameter of any optimal CDS of a graph G, then the diameter of CDS C constructed by our first algorithm satisfies: Diam(C) ≤ 3D∗ + 5, while the diameter of CDS C constructed by our second algorithm satisfies: Diam(C) ≤ 2D∗ + 4. Proof. Let p denote the longest shortest-path from a node u to a node v in graph G. According to the definition of diameter, we have |p| = Diam(G). From our algorithms, we can see that a tree based on breadth first search is built first. Thus, it is obvious that Diam(G) ≥ kmax . The diameter of a CDS is at least Diam(G)-2, i.e. D∗ ≥ Diam(G) − 2. Since there exists a path p between u and v, which only includes nodes in C except u and v. If u and v are dominatees, we have D∗ ≥ |p | − 2.
18
J. Yu, N. Wang, and G. Wang
Meanwhile, |p | ≥ Diam(G). Therefore, D∗ ≥ |p | − 2 ≥ Diam(G) − 2 ≥ kmax − 2
(15)
According to the theorem 6, the maximum distance from any black node to r is 3 1 2 kmax − 2 . Thus, Diam(C) ≤ 2( 23 kmax − 12 ) = 3kmax − 1 (16) = 3(kmax − 2) + 5 ≤ 3D∗ + 5 According to the theorem 7, the maximum distance from any node in C to r is kmax . Thus, Diam(C) ≤ 2kmax = 2(kmax − 2) + 4 = 2D∗ + 4.
(17)
4
Simulation
This section shows the results of simulations and evaluates the performance of the algorithms through comparing with the size and diameter of CDS constructed by our two algorithms, CDS-1 and CDS-2, and two centralized algorithms in [10], CDS-BD-C1 and CDS-BD-C2. Simulations are carried out under an ideal network environment. There is no consideration of node’s movement and channel
(a) r= 1 5
(b) r= 2 0
(c) r= 2 5
(d) r= 3 0
Fig. 1. CDS size comparison when the transmission range of nodes is (a)15, (b)20, (c)25, (d)30.
Heuristic Algorithms for Constructing Connected Dominating Sets
( a) r = 1 5
( b) r = 2 0
(c ) r= 2 5
( d) r = 3 0
19
Fig. 2. CDS diameter comparison when the transmission range of nodes is (a)15, (b)20, (c)25, (d)30.
collision. All simulations are implemented in C++. In order to generate a random network, n nodes are randomly distributed in a 100 × 100 2D space. We need to set two parameters. One is the number of nodes in the network, n (ranging from 0 to 100 by 5). The other one is the transmission range of each node, r (varying among 15, 20, 25 and 30). For each fixed number of nodes, we perform the simulation for 200 times and compute the average value. Figure 1 shows the comparison of the four algorithms in terms of CDS size when the maximum transmission range of nodes is 15, 20, 25 and 30. No matter how many the transmission range of nodes, the CDS constructed by CDS-2 has the smallest size, while CDS-BD-C1 obtains the largest CDS size. And the results of CDS-1 and CDS-BD-C2 are close, but that of the CDS-BD-C2 is slightly better than CDS-1. Moreover, as the number of nodes in the network and the transmission range are increasing, CDS-2 is more better than other three algorithms. Figure 2 shows the comparison of the four algorithms in terms of CDS diameter when the maximum transmission range of nodes is 15, 20, 25 and 30. CDS-2 always generates CDS with the shortest diameter, regardless of the number of nodes or transmission range. As the transmission range of nodes is increasing, the diameter of CDSs constructed by the four algorithms is reducing.
5
Conclusion
This paper studies on constructing a minimum CDS with bounded diameter in wireless networks, and proposes two heuristic algorithms. First to construct a maximal independent set MIS for the graph G, then to select connectors to connect the nodes in MIS using two heuristic rules for obtaining a CDS. Theoretical
20
J. Yu, N. Wang, and G. Wang
analysis and simulation results prove that the two algorithms have good performances on CDS size and diameter. In particular, the second one has better performance ratios than other related algorithms in the literature.
References 1. Alzoubi, K.M., Wan, P.J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (June 2002) 2. Cardei, M., Cheng, M.X., Cheng, X., Du, D.-Z.: Connected domination in ad hoc wireless networks. In: International Conference on Computer Science and Informatics (2002) 3. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discrete Mathematics 86, 165–177 (1990) 4. Cheng, X., Ding, M., Du, H., Jia, X.: Virtual backbone construction in multi hop ad hoc wireless networks. Wireless Communications and Mobile Computing 6(2), 183–190 (2006) 5. Das, B., Bharghavan, V.: Routing in ad hoc networks using minimum connected dominating sets. In: ICC 1997, Montreal, Canada (June 1997) 6. Ephremides, A., Wieselthier, I., Baker, D.: A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. IEEE 75(1), 56–70 (1987) 7. Garey, M.L., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979) 8. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998) 9. Islam, K., Akl, S.G., Meijer, H.: A Constant Factor Localized Algorithm for Computing Connected Dominating Sets in Wireless Sensor Networks. In: 2008 14th IEEE International Conference on Parallel and Distributed Systems, pp. 559–566 (2008) 10. Kim, D., Li, Y., Zou, F., Du, D.-Z.: Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks. IEEE Transactions on Parallel and Distributed System 20(2), 147–157 (2009) 11. Marathe, M.V., et al.: Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995) 12. Mohammed, K., Gewali, L., Muthukumar, V.: Generating quality dominating sets for sensor networks. In: Proceedings of the Sixth International Conference on Computational Intelligence and Multimedia Applications, pp. 204–211 (August 2005) 13. Schmid, S., Wattenhofer, R.: Algorithmic models for sensor networks. In: Proc. of the 14th International Workshop on Parallel and Distributed Real-Time Systems (2006) 14. Vahdatpour, A., Dabiri, F., Moazeni, M., Sarrafzadeh, M.: Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks. In: Proceedings of the 22nd International Symposium on Distributed Computing, pp. 481–495 (2008) 15. Zou, F., Li, X., Kim, D., Wu, W.: Construction of Minimum Connected Dominating Set in 3-Dimensional Wireless Network. In: Li, Y., Huynh, D.T., Das, S.K., Du, D.-Z. (eds.) WASA 2008. LNCS, vol. 5258, pp. 134–140. Springer, Heidelberg (2008)
Energy-Efficient Algorithm for the Target Q-coverage Problem in Wireless Sensor Networks Hui Liu, Wenping Chen, Huan Ma, and Deying Li Key Laboratory of Data Engineering and Knowledge Engineering, MOE School of Information, Renmin University of China, China
[email protected]
Abstract. In this paper we study the target Q-coverage (TQC) problem where each target needs to be covered by different numbers of sensors. We try to find a collection of Q-covsets which satisfy the coverage quality requirement to maximize the network lifetime. We first prove that the problem is NP-Hard. Then we design a greedy algorithm to efficiently compute the Q-covsets. Finally, simulation results are presented to verify our approach. Keywords: target Q-coverage, network lifetime, greedy algorithm, wireless sensor network.
1
Introduction
Target coverage is a fundamental problem in wireless sensor networks for environment monitoring and surveillance purposes. In general, sensor nodes are powered by limited battery resources. To maximize the network lifetime, many algorithms were proposed to organize sensors into a number of subsets, such that each set completely covers all the targets, and scheduling the time to make these subsets activated successively, such that only one set is active at any time instant [1]-[3]. In [4], the authors studied the maximizing lifetime for multi-attributes of target coverage problem in wireless sensor networks. [6] [7] studied k-coverage problem with the assumption that a sensor can monitor only one target at a time. In practical applications, individual targets are usually associated with different importance. According to the importance of every target, different quality of coverage is required, that is to say, each target needs different numbers of sensors to cover to satisfy its QoS requirement. This problem is called target Q-coverage problem which is first defined in [8]. The authors [8] proposed the column general based approach to solve the problem, but time complexity of the approach may not be a polynomial time. In [9], a simpler heuristic algorithm for the target Q-coverage problem is proposed. [5] studied target coverage in directional sensor network where each target has differentiated coverage quality requirement.
Corresponding author.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 21–25, 2010. c Springer-Verlag Berlin Heidelberg 2010
22
H. Liu et al.
In this paper, we also study target Q-coverage problem. The rest of this paper is organized as follows. Section 2 describes the target Q-coverage problem. We prove it is NP-hard and give a greedy algorithm to solve this problem in Section 3. Section 4 presents the simulation results for comparing our algorithm with the HESL algorithm in [9].
2
Network Model and Problem Description
Suppose there are a number of targets {a1 , a2 , · · · , am } with known locations deployed in a plane, while a great number of sensors {s1 , s2 , · · · , sn } are randomly scattered around the targets and continuously observe (cover) them. Each sensor si has its sensing radius ri . A target aj can be sensed by a sensor si if and only if the distance between aj and si is at most si ’s sensing radius. Suppose sensor si has a initial lifetime Ei . We use an integer vector Q = {q1 , q2 , · · · , qm } to express coverage requirement of targets, where qj is the minimum number of sensors which simultaneously cover target aj . To extend the network lifetime and meet coverage demand, we use the sensing scheduling that alternates the sensors between active state and sleep state and guarantees that each target can be covered by at least the requirement number of sensors. Definition 1. Target Q-coverage (TQC) problem: Given m targets and n sensors in an energy constrained wireless sensor network, how to schedule at least qj (qj ≥ 1) sensors at any time cover aj target (j = 1, · · · , m) such that the network lifetime is maximized. Definition 2. A subset D of sensors is called Q-covset if it can satisfy the coverage requirement, i.e., for each target aj , there are at least qj sensors in D which can cover aj . Our goal is to try to find a collection of Q-covsets and assign the lifetimes of Q-covsets to maximize the network lifetime.
3
The Greedy Algorithm
In this section, we first prove that the TQC problem is NP-hard. Theorem 1. The TQC problem is NP-hard. Proof: The maximum set covers (MSC)[1] is a special case of the TQC problem. This is because when qj = 1 for each target aj , the TQC problem becomes the MSC problem. Since the MSC problem is NP-hard [1], thus the TQC problem is NP-hard. In the following, we propose a greedy algorithm for the TQC problem: Greedy with the More Uncovered Targets (the GMUT algorithm). The main idea of the GMUT algorithm is follows:
Energy-Efficient Algorithm for the Target Q-coverage Problem
23
Firstly, we form a Q-covset Dk (k = 1, · · · , K). Here we sort sensors by the decreasing number of covering uncovered targets(If there are some sensors with the same numbers of covering uncovered targets, we list these sensors in order of the decreasing available lifetime). Next we put the first sensor su from the sort set to Dk and modify the values of correlated variables, such as the requirement of targets covered by it. Then repeat these steps till we form a Q-covset. Secondly, we allocate a time slot to every Q-covset Dk . tk is used to represent the time that each Q-covset is active. We set tk as the smaller value between the minimum available lifetime E[i] from Dk and a given small constant w. Next we update the correlated variables’ values, for example the sensors’ available lifetimes in Dk . At last, we continue to find the next Q-covset till there are not enough sensors with available lifetimes to cover the targets. The greedy algorithms returns Knumber of Q-covsets: D1 , D2 , · · · , DK with lifetime t1 , t2 , · · · , tK . The GMUT algorithm is formally represented as follows:
Algorithm 1. GMUT-TQC(S, A, Ei , Q) 1: SET E[i] = Ei , i = 1, 2, · · · , n, K = 1 2: WHILE each target aj is covered by at least qj available sensors in S do 3: Stemp = S, Atemp = A, DK = ∅, Q[j] = qj , j = 1, · · · , m = ∅ do 4: WHILE Atemp 5: sort sensors by the decrement of the numbers of uncovered targets that sensors cover. If some sensors have the same numbers, give the priority to the sensor with maximum available lifetime. 6: Choose the first sensor su ∈ Stemp from the sort set 7: let DK = DK ∪ {su }, Stemp = Stemp − {su } 8: FORALL target aj ∈ Atemp do 9: IF aj is covered by su then 10: Q[j] = Q[j] − 1 11: IF Q[j] == 0 then 12: Atemp = Atemp − {aj } 13: tK = min(minsi ∈DK E[i], w), T = T + tK 14: FORALL sensors si ∈ DK do 15: E[i] = E[i] − tK 16: IF E[i] == 0 then 17: Stemp = Stemp − {si } 18: K++ 19: Return K Q-covsets: D1 , D2 , · · · , DK with lifetime t1 , t2 , · · · , tK .
The input parameters of this algorithm are below: S as the set of sensors, A as the set of targets, Ei as the initial lifetime of the ith sensor and Q = {q1 , · · · , qm } as the targets’ coverage requirements. The set Stemp maintains the list of sensors that have the residual lifetimes greater than zero, thus these sensors can participate in additional Q-covsets. The set Atemp contains the targets that still have not be covered by the current Q-covsets Dk .
24
H. Liu et al.
The Performance Evaluation below shows our algorithm is more better than the HESL algorithm in [9]. This is because each time we select the sensor which covers the maximal number of uncovered targets and has higher residual lifetime to form Dk , thus the formed Q-covset Dk is with both less number and higher residual lifetime. However the HESL algorithm just chooses the sensor with the highest residual lifetime, therefore, its Q-covset may not be better in energyefficient and its network lifetime may lesser than ours.
4
Performance Evaluation
In this section, we will compare our algorithm with the algorithm (HESL) in [9]. In our simulation, we deploy the sensor nodes and targets randomly in a region of 300m × 300m area. To evaluate the performance of our algorithm, we consider the following tunable parameters: the number of sensors N , the number of targets M and the sensing range of sensors R. We suppose each sensor has initial energy Ei randomly from 1 to 10, each target’s coverage requirement qj is selected randomly from 1 to 3, and the time slot w is 0.1. In each experiment, we run 100 times and compute its average value. In first case, we set the sensing range of each sensor is 60m and the target number is fixed 10. From Fig.1, we find that the network lifetime increases as the number of sensors increasing. In second case, we set the sensing range of sensors is 60m and there are 200 sensors deployed randomly in the area. We can see that
180 Network Lifetime
120
HESL GMUT
90 60 30
150
HESL GMUT
120 90 60 30 0
0 60
70
80
90
5
100 110 120 130 140 150
Number of Sensors
Fig. 1. Network lifetime vs. N
10
15
20 25 30 35 Number of Targets
250 HESL GMUT
200 150 100 50 0 50
60
70
40
45
Fig. 2. Network lifetime vs. M
300 Network Lifetime
Network Lifetime
150
80
90 100 110 120 130 140 150 Sensing range
Fig. 3. Network lifetime vs. sensing range
50
Energy-Efficient Algorithm for the Target Q-coverage Problem
25
the network lifetime decreases with the increasing of the number of targets from Fig.2. In third case, we have the parameters setting as that: 100 sensors and 15 targets, and from Fig.3 we find that the network lifetime increases with the increasing of the sensing range. Obviously, our algorithm is much better than the HESL algorithm.
5
Conclusion
In this paper, we study the target Q-coverage problem. First prove the problem is NP-hard. Then a greedy algorithm is proposed to solve this problem. At last, we compare our greedy algorithm with the HESL algorithm and simulation results show that our algorithm is more better than the HESL algorithm.
Acknowledgment This paper was supported in part by Renmim University of China under Grants 10XNJ032 and 10XNG037.
References 1. Cardei, M., Thai, M.T., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: INFOCOM (2005) 2. Cardei, M., Du, D.-Z.: Improving wireless sensor network lifetime through power aware organization. ACM Wireless Networks 11(3), 333–340 (2005) 3. Liu, H., Wan, P., Yi, C., Jia, X., Makki, S., Niki, P.: Maximal lifetime scheduling in sensor surveillance networks. In: INFOCOM (2005) 4. Wang, L., Li, D.-Y., Li, Z.: Maximizing lifetime for multi-attributes of target coverage problem in wireless sensor networks. In: CWSN (2009) 5. Yang, H., Li, D.-Y., Chen, H.: Coverage quality based target-oriented scheduling in directional sensor networks. In: ICC (2010) 6. Liu, H., Wan, P., Jia, X.: Maximal lifetime scheduling for sensor surveillance systems with K sensors to 1 target. IEEE Transactions on Parallel and Distributed Systems 17(12), 1526–1536 (2006) 7. Liu, H., Jia, X., Wan, P., Yi, C., Makki, S.K., Pissinou, N.: Maximizing lifetime of sensor surveillance systems. IEEE Transactions on Networking 15(4), 334–345 (2007) 8. Gu, Y., Ji, Y., Li, J., Zhao, B.: QoS-aware target coverage in wireless sensor network. Wireless Communications and Mobile Computing 9(12), 1645–1659 (2009) 9. Chaudhary, M., Pujari, A.-K.: Q-coverage problem in wireless sensor networks. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol. 5408, pp. 325–330. Springer, Heidelberg (2009)
Approaching the Optimal Schedule for Data Aggregation in Wireless Sensor Networks Pei Wang1 , Yuan He2 , and Liusheng Huang1 1
Department of Computer Science University of Science and Technology of China, China 2 Department of Computer Science Hong Kong University of Science and Technology, China
Abstract. Due to the large-scale ad hoc deployments and wireless interference, data aggregation is a fundamental but time consuming task in wireless sensor networks. This paper focuses on the latency of data aggregation. Previously, it has been proved that the problem of minimizing the latency of data aggregation is NP-hard [1]. Using maximum independent set and first fit algorithms, in this study we design a scheduling algorithm, Peony-tree-based Data Aggregation (PDA), which has a latency bound of 15R + Δ − 15, where R is the network radius (measured in hops) and Δ is the maximum node degree. We theoretically analyze the performance of PDA based on different network models, and further evaluate it through extensive simulations. Both the analytical and simulation results demonstrate the advantages of PDA over the state-of-art algorithm in [2], which has a latency bound of 23R + Δ − 18. Keywords: wireless sensor networks, data aggregation, latency.
1
Introduction
A wireless sensor network (WSN) consists of a large number of sensor nodes which communicate with each other via their RF transceivers. Owing to the ad hoc deployments and self-organizing characteristics of sensors, WSNs are suitable for a wide variety of applications such as scientific observation, environmental monitoring, health care, and military surveillance [3,4,5,6,7,8,9]. In those applications, the operation of data aggregation is often used for querying information like event numbers. Shortening the latency of data aggregation is a fundamental requirement in WSNs, especially in real-time applications. In this paper, we focus on reducing the latency of data aggregation by designing a good schedule. This is a challenging issue mainly because of the intrinsic interference in WSNs. When two interfering signals are sent simultaneously, neither of them can be received correctly. Certainly, we can schedule the transmissions of data aggregation to avoid interference. The latency of data aggregation, however, will thus be increased inevitably. Without a good scheduling scheme, data aggregation will result in an impractically high latency. G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 26–35, 2010. c Springer-Verlag Berlin Heidelberg 2010
Approaching the Optimal Schedule for Data Aggregation
27
Previously, it has been proved that the problem of minimizing the latency of data aggregation is NP-hard [1]. Many scheduling algorithms have been proposed to reduce the latency of data aggregation [1,2,10].Theoretically, Chen et al. in [1] prove that the problem of minimizing the latency of data aggregation is NP-hard. They also design an algorithm for data aggregation which has a latency bound of (Δ − 1)R, where Δ is the maximum node degree and R is the network radius measured in hops. Kesselman and Kowalski [10] design an algorithm which has a latency bound of O(log(N )). However, they assume that each node can learn the distance to the closest neighbor and has a special collision detection capability, although such conditions cannot always be guaranteed in WSNs. Among all the existing works, the proposal of Wan et al. in [2] is the closest to our work. They propose a scheduling algorithm based on maximum independent set, which has a latency bound of 23R+Δ−18. They mainly focus on a special scenario, however, in which the communication range equals the interference range. Wan’s results are the state-of-arts on scheduling algorithms of data aggregation. The objective of our study in this paper targets approaching the optimal schedule of data aggregation. We design a scheduling algorithm for data aggregation which has a latency bound of 15R + Δ − 15. Our proposed algorithm, Peonytree-based Data Aggregation, or PDA in short, works as follows. Initially, a data aggregation tree called peony tree is constructed by using maximum independent set and first fit algorithms. The data aggregation process mainly consists of two phases: local aggregation and global aggregation. In local aggregation, raw data at the leaf nodes are transmitted to their corresponding parent nodes for aggregation. In global aggregation, data gathered in local aggregation are further aggregated layer by layer in a bottom-up manner. The latency bounds of the two phases are Δ − 1 and 15R − 14, respectively. We also theoretically analyze the performance of PDA and deduce the latency bound based on a more generic network model, which does not assume equal communication and interference ranges. The rest of this paper is organized as follows. Section 2 introduces the terminology, models, and assumptions in this paper as well as the problem formulation. In Section 3 we elaborate the scheduling algorithm of data aggregation. Section 4 presents the proofs of correctness and theoretical performance analysis, followed by the simulations results in Section 5. We conclude the work in Section 6.
2 2.1
Preliminaries Network Model
We consider a WSN consisting of one sink node s and N sensor nodes. Every sensor node is equipped with only one radio. All nodes share a common wireless channel to communicate. We also assume omni-directional antennas and unit-disk model. A node is only able to communicate with nodes within the communicate range rc and be interfered by nodes within the interference range ri . A node u can receive data correctly if and only if there is exactly one node sending data in the interference range ri of u. Otherwise, collision happens and node u cannot receive data correctly. Our algorithm has no assumptions on rc
28
P. Wang, Y. He, and L. Huang
and ri . For ease of presentation, we first assume rc = ri when elaborating the algorithm in Section 3. We will remove this assumption in Section 4. As for the process of data aggregation, we partition time into slots. A node can either send or receive a data packet in a time slot. The latency of data aggregation in this paper refers to the number of time slots passed during the entire course of data aggregation. Consider a sending node set A and its corresponding receiving node set B. We say data can be aggregated from A to B in a time slot if and only if all nodes in B can receive data correctly when all nodes in A transmit data simultaneously. Now we formulate the problem of data aggregation. We use an undirected graph G = (V, E) to represent a WSN of N nodes, where V denotes the set of nodes and E denotes the set of edges. There is an edge between node u and node v if and only if the Euclidean distance between them is not greater than rc . A feasible data aggregation schedule is a sequence of node-disjoint sending i=K sets {S1 , S2 , ..., SK }, where Si = V − {s}. All nodes in Si can transmit data i=1
simultaneously without interference in the ith time slot. After all nodes in SK finish transmitting data in the Kth time slot, all data are aggregated to the sink node. That is, the latency of data aggregation with the above schedule is K. Denote the corresponding receiving set of Si by Ri . It can be seen that l=K Ri ⊆ ( Sl ) {s}. l=i+1
2.2
Independent Set and Concurrent Set
Node u and node v are independent if and only if they are not within the interference range of each other. If all nodes in X are independent from each other, we call node set X is an independent set. When node u and node v are not independent from each other, we call u and v cover each other. We will use independent set to select dominative nodes in the aggregation tree. Consider two links l1 : p → q and l2 : u → v where p, q, u and v are four nodes. Link l1 and link l2 are independent if and only if p is independent from v and q is independent from u. When link l1 and link l2 are independent, node p and node u can transmit simultaneously without interference. Let L = (VS , VR , f ) be a link set, where VS is the sending set, VR is the receiving set, and f is a mapping function from VS to VR . If all links in L are independent from each other, link set L is an independent link set. Thus, transmissions through the links in an independent link set can be executed simultaneously without interference. Here we call the sending set VS as a concurrent set. Later in this paper, we will use concurrent set to divide the nodes into multiple sets and correspondingly schedule data transmissions into different time slots.
3
Peony-Tree-Based Data Aggregation (PDA)
PDA mainly consists of three components, the construction of peony tree, local aggregation, and global aggregation.
Approaching the Optimal Schedule for Data Aggregation
3.1
29
Construction of Peony Tree
We construct a tree called peony tree for data aggregation, which includes all the nodes in the network. First, an approximately maximum independent set is formed to cover all the nodes. We call nodes in the maximum independent set as dominative nodes. Some additional nodes are then selected to connect dominative nodes so that all dominative nodes are reachable from the sink node. The selected nodes are called connective nodes. Each of the other nodes in the network selects a neighboring dominative node as its parent, and the peony tree is constructed. A node which is neither a dominative node nor a connective node is called a white node. Therefore we have three types of nodes in total. Different from the algorithm proposed in [2] which selects connective nodes arbitrarily, we try to select the minimum number of connective nodes to avoid collision and reduce the aggregation latency. 1. Dominative nodes selection. Initially, we construct a common breadth first search tree TBF S rooted at the sink node s. Denote the depth of TBF S by R. All nodes in the network are thus divided into layers L0 , L1 , ..., LR , according to their depths in TBF S . Specially, L0 = {s}. We denote the maximum independent set by D. At the beginning, D = φ. To minimize the aggregation latency, dominative nodes in D are selected layer by layer in a top-down manner. For a node u in Li , if u is independent from all the other nodes in D, add u into D and remove u and its neighbors from all layers. Otherwise, remove u from Li . Repeat this procedure until Li is empty. When there is no node in Li , continue the procedure in Li+1 . After the procedure finishes at LR , the resulting set D is a maximum independent set, i.e. the dominative nodes are selected. 2. Determination of connective nodes and white nodes. The connective nodes and dominative nodes together constitute the backbone of the network. According to the selection of dominative nodes, a connective node may cover one or more dominative nodes. When connective nodes are selected arbitrarily [2], the number of connective nodes are often more than necessary, reducing the rate of data aggregation. Based on such observation, we select minimum number of connective nodes by using first fit algorithm. Denote the peony tree by T = (V, E }, where V is the node set and E is the edge set. We may divide the dominate nodes into layers D0 , D1 , ..., DR according to their hops to the sink node. For a dominative node u in Di , select a node v in Li−1 , which is a neighbor node of u. Node v is set as the parent of all the dominative nodes in Di which cover v. Remove all the children of node v from Di . Then a dominative node p in Di−1 which covers v is set as the parent of v. Repeat this procedure until Di is empty. When there is no node in Di , repeat the procedure in Di−1 . The procedure continues until no dominative node remains in D2 . At last, set s as the parent of all connective nodes in L1 . Thus all the connective nodes are selected.
30
P. Wang, Y. He, and L. Huang
Those nodes which are neither dominative nodes nor connective nodes are set as white nodes. Denote the set of white nodes by W . For each white node w in W , a dominative node is selected as its parent, which has the lowest depth among all the dominative nodes covering w. Given the depth of TBF S as R, according to the construction of peony tree, there are both connective nodes and dominative nodes in each layer of TBF S , except in layer 0, layer 1, and Layer R. Specifically, sink node s is the unique dominative node in layer 0. There are no dominative nodes in layer 1. There are no connective nodes in layer R of TBF S , either. Consequently, the depth of the peony tree is 2(R − 2) + 1 + 1 + 1 = 2R − 1. 3.2
Local Aggregation
During the local aggregation phase, white nodes transmit the sensory data to their parents (the corresponding dominative nodes) for aggregation. Meanwhile, a dominative node takes aggregation operations when all its child nodes have transmitted data. Because transmissions on dependent links should transmit data in different time slots, to avoid interference and minimize the latency in local aggregation, the set of white nodes W is divided into k node-disjoint maximum concurrent sets. Denote these node-disjoint maximum concurrent sets by U Wi (i = 1, 2, ..., k), where k is the number of the node-disjoint maximum concurrent subsets of W . Therefore, nodes in U Wi can transmit data without interference in the ith time slot. Then the latency of data aggregation in the phase of local aggregation is k. U Wi (i = 1, 2, ..., k) are iteratively determined by using first fit algorithm. The first fit algorithm for constructing node-disjoint maximum concurrent sets works as follows. Consider a link set L = (VS , VR , f ), where VS is sending node set, VR is its corresponding receiving node set, and f is a mapping function from VS to VR . Denote all maximum concurrent sets by U1 , U2 , ..., Uh , where h is the number of maximum concurrent sets. For each node u in VS , if link l : u → f (u) is independent from all links in {l : v → f (v) | v ∈ Ui }, add u into Ui and remove u from VS . When there is no more node to add into Ui , repeat the above procedure to form the next maximum concurrent set Ui+1 until no node remains in VS . 3.3
Global Aggregation
Global aggregation involves two types of transmissions. One is from a dominative node to its parent connective node, and the other is from a connective node to its parent dominative node. Global aggregation starts with the transmission from the dominative nodes in LR to their parent connective nodes in LR−1 . The above two types of transmissions run alternately until the data are aggregated from the connective nodes in layer 1 to the sink node. To avoid interference and minimize the latency of global aggregation, we divide dominative nodes and connective nodes in each layer of TBF S into nodedisjoint maximum concurrent sets. Denote them by U Di,1 , U Di,2 , ..., U Di,mi and
Approaching the Optimal Schedule for Data Aggregation
31
U Ci,1 , U Ci,2 , ..., U Ci,ni respectively, where mi is the number of maximum concurrent subsets of Di and ni is the number of maximum concurrent subsets of Ci . Specially, s is sink node and the unique one in layer 0, m0 = 0. Because there is no dominative nodes in layer 1, m1 = 0. Similarly, we have nR = 0. Similarly with local aggregation, we allocate different time slots for different maximum concurrent sets. Data are aggregated layer by layer in a bottom-up manner. A node transmits data after all its children transmit data. Due to the fact that the latency at local aggregation phase is k, we schedule all dominative nodes and connective nodes as follows. Connective nodes in U Ci,j transmit data l=i+1 in the ( (ml + nl ) + j + k)th time slot. Dominative nodes in U Di,j transmit l=R
l=i+1
data in the (
l=R
(ml + nl ) + ni + j + k)th time slot. We can imply that the
latency of global aggregation is
l=1 l=R
4
(ml + nl ) slots.
Discussion
In this section, we first prove the latency bound of our algorithm based on the assumption rc = ri , and then we remove the constraint and deduce the latency bound based on a generic network model. 4.1
Correctness
Theorem 1. The latency bound of data aggregation in local aggregation is Δ−1. Proof. Due to the page limit, we skip the proof here. Theorem 2. The maximum number of dominative neighbors for a connective node is 5. Proof. Due to the page limit, we skip the proof here. Theorem 3. The maximum number of connective neighbors of a dominative node is 12. Proof. Due to the page limit, we skip the proof here. Theorem 4. The latency bound of data aggregation on a peony tree is 15R + Δ − 15. Proof. Recall that our schedule consists of local aggregation phase and global aggregation phase. As the latency bound of local aggregation phase is Δ − 1 according to Theorem 1, we analyze the latency bound of global aggregation phase before we get the latency bound of data aggregation on a peony tree. Recall that in a peony tree, dominative nodes are in the even layers while connective nodes are in the odd layers, so there are two transmission patterns
32
P. Wang, Y. He, and L. Huang
in global aggregation. One is data transmission from a dominative node to a connective node, and the other is data transmission from a connective node to a dominative node. First, according to Theorem 2, a connective node has at most 5 dominative neighbors and one of them is its parent. So the number of dominative children of a connective node is at most 4. Consequently, the latency bound of data aggregation from dominative nodes in an even layer to connective nodes in the upper layer is 4. Second, according to Theorem 3, a dominative node has at most 12 connective neighbors and one of them is its parent node. So the number of connective children of a dominative node is at most 11. Consequently, the latency bound of data aggregation from connective nodes in an odd layer to dominative nodes in the upper layer is 11. Specially, the sink node is a dominative node without parent. The latency bound of aggregation from connective nodes in layer 1 to the sink node is 12. In the peony tree, the number of layers which contain connective nodes is R−1. The number of layers which contain dominative nodes except sink node s is also R − 1. Basing on the above analysis, the latency bound of global aggregation is 11(R − 2) + 12 + 4(R − 1) = 15R − 14. Therefore, the latency bound of data aggregation on a peony tree is (Δ − 1) + (15R − 14) = 15R + Δ − 15. 4.2
On Generic Model
Most existing works base their schemes on the assumption rc = ri , so far we also discuss based on this assumption. Indeed, our scheme is not constrained by the assumption, and in this section we remove it. As data aggregation is conducted layer by layer, nodes suffer interference only from nodes in the same layer when they transmit data simultaneously. As mentioned above, there are three types of transmissions during the course of data aggregation, below we will discuss separately. For simplicity, we normalize the communication range rc = 1 and the interference range ri = ρ. Denote the upper bound of the number of independent nodes in a radius of ρ by Γ (ρ). Before deducing the latency of data aggregation, we first present two theorems related to Γ (ρ). Theorem 5. (Wegner Theorem [11]) The area of the convex hull of n (n ≥ 2) non-overlapping unit-radius circular disks is at least √ √ √ (1) 2 3(n − 1) + (2 − 3) 12n − 3 − 3 + π Theorem 6. Γ (ρ), the upper bound of the number of independent nodes in a radius of ρ, satisfies the condition that √ √ 2 3(Γ (ρ) − 1) + (2 − 3) 12Γ (ρ) − 3 − 3 + π ≤ (2ρ + 1)2 π (2)
Approaching the Optimal Schedule for Data Aggregation
33
Fig. 1. The maximum number of independent node in a radius of ρ
Proof. Consider independent nodes in a disk of radius ρ centered at point o as shown in Fig. 1. Place a small disk with radius 0.5 centered at each independent node. Because the distance between any two independent nodes is greater than 1 (rc = 1), all the small disks are non-overlapping. According to Theorem 5, the area covers all the small disks of radius 0.5 is at least √ of the convex hull√which (2 3(Γ (ρ) − 1) + (2 − 3) 12Γ (h) − 3 − 3 + π)/4. Because all the small disks are in a big disk of radius h + 0.5 centered at point o, the convex hull which covers all the small disks is also in the big disk. The area of the convex hull is not greater than that of the big disk, so Γ (ρ) satisfies the inequation 2. Now we deduce the latency of data aggregation on generic model. 1. Transmissions from white nodes to dominative nodes. When ρ ≤ 1, a dominative node receives data from at most Δ − 1 white neighbors. Hence, the latency bound of transmissions from white nodes to dominative nodes is still Δ−1. When ρ > 1, a dominative node can be interfered by all the white nodes in the interference range, no matter whether or not they are neighbors. Thus the latency bound is affected by the maximum number of white nodes in a radius of ρ. As there are at most Γ (ρ) dominative nodes in a radius of ρ and a dominative node has at most Δ − 1 white neighbors, the latency bound of transmissions from white nodes to dominative nodes is Γ (ρ)(Δ − 1). 2. Transmissions from dominative nodes to connective nodes. For a connective node u, there are at most Γ (ρ) dominative nodes in a radius of ρ and one of them is its parent. Consequently, the latency bound of transmissions from dominative nodes to connective nodes is Γ (ρ) − 1. 3. Transmissions from connective nodes to dominative nodes. Because a connective node connects dominative nodes in the adjacent layer, the number of connective nodes in a radius of ρ is not more than the number of dominative nodes in a radius of 1 + ρ. Hence, a dominative node has at most Γ (1 + ρ) connective neighbors. Meanwhile, one of those connective nodes is the parent of the dominative node. The latency bound of transmissions from connective nodes to dominative nodes is Γ (1 + ρ) − 1. Specially, the latency from connective nodes in layer 1 to the sink node is at most Γ (1 + ρ).
34
P. Wang, Y. He, and L. Huang
Theorem 7. The latency bound of data aggregation in a peony tree is (Γ (ρ) + Γ (1 + ρ) − 2)(R − 2) + Γ (ρ)Δ + Γ (1 + ρ) − 1
(3)
Proof. Recall that there are no connective node in layer R and no dominative node in layer 1 of the tree. The latency from connective nodes in layer 1 to sink node is Γ (1 + ρ). So the latency bound of data aggregation on peony tree is Γ (ρ)(Δ − 1) + (Γ (ρ) − 1) + ((Γ (ρ) − 1) + (Γ (1 + ρ) − 1))(R − 2) + Γ (1 + ρ) = (Γ (ρ) + Γ (1 + ρ) − 2)(R − 2) + Γ (ρ)Δ + Γ (1 + ρ) − 1.
5
Performance Evaluation
In the simulations, we let all sensor nodes have the identical communication range rc and identical interference range ri , where rc = ri = 10m. Sensor nodes are randomly deployed into a 100m × 100m area for multiple times to generate different network topologies. 20 different topologies are generated with network sizes (measured by the number of nodes) varying from 400 to 2000. We compare PDA with the algorithm proposed by Wan et al. in [2] (denoted as WALG in short in the figures) by measuring the number of time slots to aggregate all the sensory data in a WSN. Figure 2(a) plots the number of connective nodes selected by PDA and WALG (note that the numbers of dominative nodes selected by the two algorithms are same, so we do not show them in the figures). We can see the number of connective nodes selected by PDA is much less than that of WALG. Also, WALG is slightly affected by the network size, while PDA performs consistently with different network sizes. The total aggregation latency by using PDA is about 20% shorter than that of using WALG, as shown in Fig. 2(b).
(a) Number of connective Nodes
(b) Total aggregation latency
Fig. 2. Comparison with different network sizes
6
Conclusion
We study the issue of minimizing the latency of data aggregation in WSNs and propose a scheduling algorithm named PDA. PDA has a latency bound of
Approaching the Optimal Schedule for Data Aggregation
35
15R + Δ − 15, where R is the network radius (measured in hops) and Δ is the maximum node degree. To the best our knowledge, this latency bound is by far the lowest one. Moreover, we remove the constraint of equal communication and interference ranges used in most existing works and discuss the latency bound of PDA based on a generic network model. We compare PDA with the state-of-arts algorithm proposed in [2] through simulations and the results show that PDA significantly outperforms existing designs.
References 1. Xujin, C., Xiaodong, H., Jianming, Z.: Minimum data aggregation time problem in wireless sensor networks. In: 1st International Conference on Mobile Ad-hoc and Sensor Networks, pp. 133–142. IEEE Press, Wuhan (December 2005) 2. Scott, C.-H.H., Peng-Jun, W., Chinh, T.V., et al.: Nearly constant approximation for data aggregation scheduling in wireless sensor networks. In: Proceedings of INFOCOM, pp. 366–372. IEEE Press, Anchorage (May 2007) 3. Ian, F.A., Weilian, S., Yogesh, S., Erdal, C.: Wireless sensor networks: a survey. Computer Networks 38(4), 393–422 (2002) 4. Mo, L., Yunhao, L.: Underground structure monitoring with wireless sensor networks. In: Proceedings of ACM/IEEE IPSN, pp. 69–78. ACM Press, Cambridge (April 2007) 5. Robert, S., Alan, M.M., Joseph, P., et al.: An analysis of a large scale habitat monitoring application. In: Proceedings of ACM SenSys, pp. 214–226. ACM Press, Baltimore (November 2004) 6. Mo, L., Yunhao, L.: Iso-map: Energy-efficient contour mapping in wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering (TKDE) 22(5), 699–710 (2010) 7. Mo, L., Yunhao, L., Lei, C.: Non-threshold based event detection for 3d environment monitoring in sensor networks. IEEE Transactions on Knowledge and Data Engineering (TKDE) 20(12), 1699–1711 (2008) 8. Kebin, L., Mo, L., Yunhao, L., et al.: Passive diagnosis for wireless sensor networks. In: Proceedings of ACM SenSys, pp. 113–126. ACM Press, Raleigh (November 2008) 9. Lufeng, M., Yuan, H., Yunhao, L., et al.: Canopy closure estimates with greenorbs: Sustainable sensing in the forest. In: Proceedings of ACM Sensys, pp. 99–112. ACM Press, Berkeley (November 2008) 10. Alexander, K., Dariusz, R.K.: Fast distributed algorithm for convergecast in ad hoc geometric radio networks. J. Parallel Distrib. Comput. 66(4), 578–585 (2006) ¨ 11. Wegner, G.: Uber endliche kreispackungen in der ebene. Studia Scientiarium Mathematicarium Hungarica 21, 1–28 (1986)
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs* Wei Li1, Yong Cui2, Shengling Wang2, and Xiuzhen Cheng3 1
Beijing University of Posts and Telecommunications, Beijing, P.R.China
[email protected] 2 Tsinghua University, Beijing, P.R.China {cy,slwang}@csnet1.cs.tsinghua.edu.cn 3 The George Washington University, Washington DC, USA
[email protected]
Abstract. In this study, we investigate the problem of achieving proportional fairness via Access Point (AP) association in multi-rate WLANs. This problem is formulated as a non-linear program with an objective function of maximizing the total user bandwidth utilities in the whole network. It is NP-hard, and therefore effort in this paper is made to seek approximate solutions. We propose a centralized algorithm to derive the user-AP association via relaxation. Such a relaxation may cause a large integrality gap. Therefore a compensation function is introduced to guarantee that our algorithm can achieve at least half of the optimal solution in the worst-case scenario theoretically. Extensive simulation study has been reported to validate and compare the performances of our algorithms with those of the state-of-the-art. Keywords: AP association, bandwidth allocation, multi-rate WLANs, proportional fairness.
1 Introduction By default, each user in IEEE 802.11 WLANs associates with the AP that has the largest received signal strength indicator (RSSI). As typically users are not uniformly distributed among all APs, RSSI based approach may overload some APs while leave others carrying very light load or even being idle. This load unbalancing could result in unfair bandwidth allocation. Although the network is supposed to serve fairly at high performance, fairness and efficiency are often in conflict with each other. With the development of multi-rate WLANs, this problem has become even more challenging, as users with different bit rates intend to share the same WLAN. 802.11 MAC protocol provides equal long-term transmission opportunities to users. Therefore, users with the same frame size can achieve equal throughput (i.e. throughput-based fairness). However, in multi-rate WLANs, throughput-based fairness requires that users with lower bit rates occupy the channel for a longer time *
Supported by National Natural Science Foundation of China (no.60873252), National Major Basic Research Program of China (no.2009CB320503), and the US National Science Foundation (CNS-0831852).
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 36–46, 2010. © Springer-Verlag Berlin Heidelberg 2010
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs
37
than those with higher bit rates, drastically reducing the network throughput [1]. To overcome this problem, time-based fairness is proposed such that each user can obtain an equal share of channel occupancy time. Recent research [1] has shown that timebased fairness outperforms throughput-based fairness in multi-rate WLANs. There are two fairness criteria that are widely used in network resource assignment. Max-min fairness [2] distributes resources as equally as possible among users. While proportional fairness [3], on the other hand, allocates bandwidth to users in proportion to their bit rates to maximize the sum of the bandwidth utility of all users. Proportional fairness has been utilized to effectively exploit the tradeoff between fairness and network performance [3], [4]. Fairness, load balancing, and AP selection are three interrelated dimensions of the resource management problem. Nevertheless, very few recent researches jointly consider these three dimensions in multi-rate WLANs. Though different algorithms have been proposed to achieve fairness [1], [5], they only consider the problem at a single AP instead of the whole network. Other approaches optimize the AP association for efficient resource assignment [6], but they do not consider fairness. Load balancing has been proposed to optimize the resource assignment in [7], but fairness again is not considered. It has been observed that jointly considering AP association and fairness can effectively improve the aggregated network throughput [4], [8] in WLANs, since users may reside in the overlapping coverage areas of multiple APs while each user is only associated with one AP at a time. Li et al. [4] propose two approximate AP selection schemes, cvapPF and nlapPF, for periodic offline optimization. Both cvapPF and nlapPF rely on relaxation and rounding to obtain an integral user-AP association. Bejerano et al. [8] demonstrate the strong correlation between fairness and load balancing, and propose a load balancing technique to obtain an optimal max-min fair bandwidth allocation. In this paper, we propose an algorithm for AP selection to achieve proportional fairness. In our system model, the resources at all APs are considered as a whole when allocating bandwidth fairly to users. With this network-wide fairness objective, load balancing is automatically considered. Our Non-linear Approximate Optimization for Proportional Fairness (NLAO-PF) is centralized and can be adopted periodically in real multi-rate WLANs applications. Since the non-linear optimization problem is NP-hard [4], NLAO-PF is decomposed into four steps to simplify the issue and improve the degree of approximation. Our problem formulation is motivated by the non-linear program in [4] but we adopt a completely different approach to relax the variables in our approximation algorithm design. By introducing a compensation function to the objective function to narrow down the gap caused by relaxation, the total utility of the bandwidth allocation via NLAO-PF is proved to be at least 1/2 of the optimal in the worst case. Our comparison-based simulation study indicates that NLAO-PF performs well when the users are distributed randomly and uniformly in the network. Moreover, the performance is even better when users are distributed in a hot spot area. The rest of the paper is organized as follows. Our system model is introduced in Section 2. The algorithm is detailed in Sections 3. After presenting the evaluation results in Section 4, we conclude this paper in Section 5.
38
W. Li et al.
2 System Model Our network topology models an IEEE 802.11 based multi-rate WLAN network that consists of multiple APs. Each AP has the same limited coverage area and serves users in its area. Overlapping coverage areas of adjacent APs may exist. The union of the coverage areas of all APs forms the network coverage area. We assume that each AP transmits messages with the same power as defined by IEEE 802.11. We further assume that each user is covered by at least one AP, and each AP has at least one associated user. The notations and definitions to be utilized are summarized in Table 1. Table 1. Notations Symbol A Ai n U m
Jij gij pj N0 wi bi rij xij X tij T
Semantics The set of all access points (AP). The set of APs that can be associated with (cover) user i. n=|A|, the number of APs. The set of all users m=|U|, the number of users. The SINR of user i when associated with AP j. The channel gain from AP j to user i. The transmission power of AP j. The receiver noise power. The weight of user i. The effective bandwidth allocated to user i. The effective bit rate between user i and AP j. The association coefficient between user i and AP j. The 0-1 user-AP association matrix. The transmission time between user i and AP j. The transmission time allocation matrix.
Table 2. The Relationship between SINRs and Rates
Jij (dB) rij (Mbps)
6-7.8 6
7.8-9 9
9-10.8 12
10.8-17 18
17-18.8 24
18.8-24 36
24-24.6 48
24.654
As we have known, a user in an overlapping coverage area will be interfered by other APs. The effective bit rate of a user in an 802.11 network is determined by the experienced SINR of the user. More precisely, let γij denote the SINR of user i when associated with AP j. We have, g ij p j (1) γ ij = . ∑ g ik p k + N 0 k∈ Ai ∩ k ≠ j
Further, the relationship between the effective bit rates and the SINR ranges in the 802.11 network is shown in Table 2 [9]. It is assumed that the network is saturated such that all APs are busy all the time and all users always have data ready to send. We will consider a unit of time in which the network is stable, with no new user joins and no current user leaves. This means that under our consideration the total transmission time of an AP is equal to 1. Each AP assigns transmission times to users in accordance with proportional fairness. A user is allowed to choose only one AP within the unit time.
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs
39
We formulate the AP association problem based on proportional fairness to a nonlinear program. In our system model, the resources at all APs are considered as a whole when allocating bandwidth to users. With this network-wide fairness objective, load balancing is automatically taken into account. We intend to maximize the total utility of the user bandwidth, which is defined to be the sum of logarithms of the bandwidths allocated to all users [3]. Since the effective bandwidth of user i is bi = ∑nj=1xijtij rij , we obtain the following optimization formulation:
max ∑im=1 wi log(∑nj =1 xij t ij rij ) s.t. 1≤ i ≤ m,∑nj =1xij =1 ,
(a)
1≤ j ≤ n,∑im=1xijtij =1 ,
(b)
1≤i ≤ m,1≤ j ≤n, xij ∈{0,1} ,
(c)
1≤ i ≤ m,1≤ j ≤ n,t ij ∈[0,1] .
(d)
(2)
Eq. (2) is referred as a Non-linear Program (NLP). Note that our objective function considers the weights of users, which reflects their priorities in a real network. The constraint (a) indicates that each user can associate with one and only one AP; the constraint (b) requires that the total transmission time of each AP j is equal to 1; the constraint (c) assures that xij is a binary variable that is equal to 1 if and only if user i associates to AP j; and the constraint (d) specifies the range of the variable tij. We can prove that NLP is NP-hard by slightly adapting the reduction procedure proposed in [4]. Note that this problem formulation is motivated by [4] but our approach to solving the problem via relaxation, as elaborated in Section 3, is fundamentally different and totally novel.
3 The NLAO-PF Algorithm Since NLP is NP-hard, we propose an approximation algorithm Non-Linear Approximate Optimization for Proportional Fairness (NLAO-PF) outlined in Alg.1, to simplify the issue and improve the degree of approximation. Algorithm 1. NLAO-PF 1. {t’ij}= solve r-NLP {{wi}, {rij}}. 2. Get fractional solution {x’ij}= solve c-NLP {{wi}, {rij}, {t’ij}}. 3. Get integral solution {xij} by a rounding process {{t’ij}, {x’ij}}. 4. Redistribute transmission time to obtain {tij} and calculate {bi}.
The basic idea of NLAO-PF is to relax the binary variable xij such that each user is allowed to associate with multiple APs within a unit time. This relaxation may result in a large integrality gap [10]. To overcome this problem, we modify the objective function of NLP by adding a compensation function g(X,T) in NLAO-PF, which is defined as follows. Definition 1. The compensation of user i on AP j is defined by wi xijtij log(rij ) , if rij>0;
0, otherwise. Thus the compensation of user i to all APs can be expressed
40
W. Li et al.
by wi (∑nj =1xij t ij log(rij )) . Therefore the compensation function g(X,T) can be defined correspondingly as follows: g ( X ,T ) = ∑im=1wi (∑ nj=1xij t ij log(rij )) .
(3)
This compensation function is introduced to improve the lower bound of our algorithm to effectively narrow down the integrality gap caused by relaxation. The steps of NLAO-PF are detailed in the following subsections. 3.1 Relaxed Optimization Program
The first step of NLAO-PF is to solve the following relaxed optimization problem to obtain an optimal {t’ij}. max
∑i =1wi log(∑ j =1t ij′ rij )+∑i =1wi (∑ j =1t ij′ log(rij )) m
n
m
n
s.t. 1≤ i ≤ m,∑nj =1tij′ ≤1 ,
(a)
1≤ j ≤ n,∑im=1tij′ =1 ,
(b)
1≤ i ≤ m,1≤ j ≤ n,t ij′ ∈[0,1] .
(c)
(4)
Eq. (4) is referred as the relaxed Non-linear Program (r-NLP). Compared with Eq. (2), r-NLP replaces tij by t’ij, sets xij =1, and includes the compensation function in its objective function. The constraint (a) indicates that the total transmission time of user i with all APs cannot surpass 1; the constraint (b) requires that the total transmission time of each AP is equal to 1, which means that all APs are saturated in the unit time; and the constraint (c) defines the range of the variable t’ij. Obviously, the optimal solution for {t’ij} from Eq. (4) can be found in polynomial time [4]. 3.2 Fractional Association
After solving r-NLP, we obtain the transmission time {t’ij}. Now we take {t’ij} as the input, and get the fractional user-AP association {x’ij}. Because of the requirements for solving convex programs, we change the linear equality constraint of NLP to a linear inequality constraint in the following problem formulation, which does not change the solution value. max ∑im=1wi log(∑nj =1xij′ tij′ rij ) + ∑im=1wi (∑nj =1xij′ tij′ log(rij )) s.t. 1≤ i ≤ m,∑ nj =1xij′ > 0 ,
(a)
1≤ j ≤ n,∑im=1xij′ t ij′ =1 ,
(b)
1≤ i ≤ m,1≤ j ≤ n, xij′ ≥ 0 .
(c)
(5)
Eq. (5) is referred as the complemented Non-linear Program (c-NLP). Its objective function is designed to approximate the optimal solution to NLP. The constraint (a) indicates that a user should connect with at least one AP; the constraint (b) forces the total transmission time of each AP be equal to 1; and the constraint (c) defines the
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs
41
range of x’ij for the case of fractional association. Note that here we take {t’ij} obtained from Eq. (4) as the input to c-NLP and obtain the optimal association {x’ij} for c-NLP given {t’ij}. We can prove that the gap introduced by our relaxation procedure is bounded. Let f ( X ,T ) = ∑im=1wi log(∑nj=1xijtij rij ) , h( X ,T ) = f ( X ,T )+ g ( X ,T ) .Then the objective functions of r-NLP and c-NLP become h(X=1, T) and h(X,T), respectively. Correspondingly, h(X=1, T’) and h(X’,T’) are the solutions obtained from r-NLP and c-NLP, respectively. Theorem 1. Let f(X*,T*) be the optimal solution to NLP. Then f(X*,T*)≤h(X’,T’)≤2 f(X*,T*). Proof. With
m ∑i=1xij′ tij′ =1 (constraint (b) in Eq. (5)) and rij ≥ 1, f(X’,T’)≥g(X’,T’)≥0.
Thus h(X’,T’) ≤2f(X’,T’) ≤2f(X*,T*). Note that f(X*,T*) is also feasible to c-NLP from the relationship between NLP and c-NLP. Thus we have, f(X*,T*) ≤f(X=1,T’)+g(X=1,T’)=h(X=1,T’)≤h(X’,T’), where the last inequality holds true from the fact that h(X=1, T’) is feasible to c-NLP. ■ 3.3 Optimization Program Rounding
In this step, we use the rounding algorithm proposed in [11] to obtain an integral association matrix X. That is, we fix the time allocation {t’ij} and replace the fractional association {x’ij} by a 0-1 variable {xij} that encodes the desired association of users to APs. The description of the rounding scheme is as follows. First, we construct a bipartite graph G(x)=(U,V,E), where the set U represents the users in the network, and the set V consists of AP nodes denoted by V={vjk: j=1,…,n,
⎡
⎤
k=1,…,Qj }, with Qj = ∑i=1xij . This means that each AP may have multiple nodes in m
V. The edges in G(x) are constructed in the following way. If Qj≤1, there is only one node vj1 corresponding to AP j. For each x’ij>0, add an edge e(ui, vj1) to E, and set x’(ui, vj1)=x’ij, where x’(e) is the fractional association weight of the corresponding user and AP. Otherwise, find the minimum index ik such that ∑iik=1xij′ ≥ k . For i=ik-1 +1,…, ik
-1 and x’ >0, add edges e(u , v ) and set x’(u , v )=x’ . ij
i
jk
ik −1 ′ i =ik −1 +1x (ui ,v jk ) .
edge e(ui, vjk) and set x′(ui ,v jk ) =1−∑
i
If ∑
jk
ik ′ i =1 xij
ij
For i=ik, add the
> k , add the edge e(ui,
vj(k+1)) and set x′(ui ,v j(k +1) ) = ∑iik=1x′(ui ,v jk )−k . The profit of each edge e(ui, vjk) in E is defined to be wi log(t ij′ rij ) .
Second, we find a maximum-profit matching M(x) that matches each user node to an AP node in G(x). For each edge e(ui, vjk) in M(x), schedule user i on AP j and set xij=1. Set other xij’s to be 0. Since the fractional association {x’ij} specifies a fractional matching, such a maximal matching does exist and it determines the integral association {xij}. More details can be found in [11]. Note that {t’ij} and {x’ij} are computed from r-NLP and c-NLP, respectively. The rounding scheme constructs an integral assignment {xij}. We denote this integral solution as f (Xa,T’), which is also feasible to NLP. We have
42
W. Li et al.
Theorem 2. f (Xa,T’) ≥ f (X*,T*)/2. Proof. Note that {xij} is obtained by employing the rounding scheme proposed by Shmoys and Tardos in [11], which proves the following property: f(Xa,T’)≥f(X’,T’). Thus, f(Xa,T’)≥f(X’,T’)≥[f(X’,T’)+g(X’,T’)]/2=h(X’,T’)/2≥f(X*,T*)/2, where the last ■ inequality holds from Theorem 1. 3.4 Transmission Time Redistribution
Since the user-AP association changes after rounding, we need to redistribute the transmission time. This is the last step of NLAO-PF, in which we assign transmission times to users according to proportional fairness. Theorem 3. Let {xij} be the integral user-AP association coefficients obtained from the rounding procedure outlined in Section 3.3. Given {xij}, the unique optimal transmission time assigned to user i by AP j according to proportional fairness
is tij = xij wi (∑m k =1xkj wk ) . Proof. (a) First, we consider the case of a single AP. Assume that the number of users covered by the AP is m. Since the objective function of Eq. (2) is the sum of logarithms, maximizing the total utility of the user bandwidth (Eq. (2)) is equivalent to maximizing Eq. (6): m m m m ∏i =1(tij rij )wi = ∏i =1(ti1ri1)wi = ∏i =1(ti1) wi ∏i =1(ri1)wi .
(6)
Note that {ri1} is the set of optimization constant. Therefore maximizing Eq. (6) is equivalent to maximizing Eq. (7):
t11 t11)(t t21 t21)"(t t
" " ∏i=1(ti1)wi = (t 11 21 1tm 1" m m1) .
m
w1
Since ∑im=1ti1 =1 ,
Eq.
(7)
w2
is
maximized
(7)
wm
if
and
only
if if t11 w1
t 21
1 (¦ (∑m k =1wk ) . (b) Now we consider the case of multiple APs. Let xkj be a 0-1 variable denoting
w2
t m1 wm
m i 1 wi ) . Thus we have ti1 = wi
the association coefficient between user k and AP j. Then ∑m k =1xkj wk is the sum of the weights of all users associated to AP j. With a similar analysis as that of case (a), the optimal transmission time given {xij} can be calculated by Eq. (8). tij = xij wi (∑m k =1xkj wk ) .
(8)
We conclude that given {xij}, our transmission time assignment based on proportional fairness is unique and optimal. ■ The solution obtained from our algorithm NLAO-PF can be denoted as f (Xa,Ta). Based on Theorems 2 and 3, we have f (Xa,Ta) ≥ f (Xa,T’) ≥ f (X*,T*)/2. That is, the approximate solution obtained from NLAO-PF is no less than half of the optimal solution of NLP.
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs
43
4 Evaluation For ease of comparison, we employ the same simulation settings as those in [4], which are detailed as follows. We place a total of 20 APs on a 5 by 4 grid, with each AP on a grid point. The coverage area of each AP is set to 150 meters and the distance between two adjacent APs is set to 100 meters. We arrange 50~300 users to simulate different levels of network loads. Assume that the transmission power of each AP is 20dBm [12]. The coverage area of the network is the union of the coverage areas of all APs. Assume that all users have the same weight. There are two types of user distributions under our consideration: (1) users are randomly and uniformly distributed within the coverage area of the network; (2) users are randomly positioned in a circle-shaped hotspot with a radius of 100 meters near the center of the 20-AP network. We employ a simple wireless channel model in which the effective bit rate only depends on the experienced SINR. For simplicity, we adopt the values commonly advertised by 802.11a which is shown in Table 2. The channel gain is modeled by the following equation,
gij = sij dij−4 ,
(10)
Table 3. Data Analysis on Different Algorithms Case
Uniform
Hotspot
Algorithm FraOp NLAO-PF cvapPF SSF LLF FraOp NLAO-PF cvapPF SSF LLF
Ave.(Mbps) 4.82 4.79 4.19 4.82 3.87 4.06 4.05 3.55 2.04 3.17
(a) uniform case
Var.(Mbps) 3.42 3.78 3.75 9.12 3.36 1.07 1.23 1.53 14.29 1.93
Fairness 0.87 0.86 0.87 0.71 0.85 0.94 0.93 0.93 0.39 0.85
Total utility 129.18 128.01 117.32 120.18 109.53 119.51 118.73 108.01 38.12 92.64
(b) hotspot case
Fig. 1. The user bandwidth of different AP association algorithms
44
W. Li et al.
where sij is a log-normally distributed shadowing factor, and dij is the distance between user i and AP j. Shadowing factors are generated according to the Viterbi model [13], with E(sij)=0dB and σ(sij)=10dB. The receiver noise power N0 is set to -80dBm. Fairness is quantified by the Jain’s fairness index [14], which is defined as follows,
∈
J = (∑im=1bi2 ) (∑im=1bi )2 ,
(11)
where larger values of J [0,1] indicate a better fairness. In proportional fairness, larger values of the total utility, which reflects the tradeoff between the aggregated throughput and fairness, indicate a better performance. During our simulation, the network topology structure and the effective bit rates are assumed to be steady. There is no backhaul capacity limitation. We compare the performances of the following algorithms: (1) NLAO-PF; (2) cvapPF [4]; (3) Strongest Signal First (SSF); (4) Least Load First (LLF) [8]; (5) Since the problem of AP association based on proportional fairness is NP-hard, NLAO-PF and cvapPF only obtain approximate solutions. For comparison purpose, we use the result obtained from r-NLP without the compensation function g(X,T) as a benchmark and call it FraOp. We have performed extensive simulations by varying the number of users and obtained qualitatively similar results. Thus in this subsection we only report the results for the 200-user case. The statistics of achieved bandwidth, Jain’s fairness index, and total bandwidth utility of different algorithms are presented in Table 3. First Fig.1 plots the achieved per-user bandwidth in Mbps vs. user index, with the users sorted by their bandwidths in increasing order. In the uniform case, SSF achieves a little bit higher average bandwidth, demonstrating a much larger variance in the bandwidth allocation and a poorer fairness. However, in the hotspot case where users reside in the vicinity of certain APs, leading to a more intensive competition for resources and a more imbalanced network load. Obviously, SSF aggravates the extent of load imbalance and enlarges the bandwidth allocation variances without considering fairness. It is also difficult for LLF to enhance the user bandwidth effectively because it only takes into account load balancing but ignores the user rate. On the other hand, in these two cases, NLAO-PF and cvapPF can both achieve proportional fairness, but NLAO-PF outperforms cvapPF in terms of bandwidth allocation with a value closer to FraOp. The fairness index of these two algorithms is almost the same. Moreover, the total utility of NLAO-PF is 99% of that of FraOp, while that of cvapPF is about 90%. Therefore, we conclude that NLAO-PF outperforms cvapPF, SSF and LLF. Second, the number of users vs. AP index is shown in Fig.2, with the APs sorted by their users in increasing order. The number of users associated with an AP is considered as the load metric. In these two cases, both NLAO-PF and LLF perform better than the other two algorithms in terms of load balancing. However, from Table 3, we observe that LLF has a lower average bandwidth and a poorer fairness than NLAO-PF, since it ignores the user rate. It can be concluded that NLAO-PF offers a more effective tradeoff between the bandwidth allocation and load balancing. Besides per-user bandwidth, we also compare the aggregated throughput of all algorithms. Fig.3 plots the aggregated throughput in Mbps vs. the number of users. In the uniform case, although SSF achieves a higher aggregated throughput, it reduces the level of fairness in bandwidth allocation. Among the remaining three algorithms
Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs
(a) uniform case
45
(b) hotspot case
Fig. 2. The load of different AP association algorithms with 200 users
(a) uniform case
(b) hotspot case
Fig. 3. The aggregated throughput of different AP association algorithms
(except FraOp), NLAO-PF obtains much higher aggregated throughputs than the other two algorithms, especially in the hotspot case. On the other hand, compared with cvapPF, NLAO-PF has a higher approximate degree, and its optimization results are more prominent. What is more, in the hotspot case, advantages of our algorithm are even more significant.
5 Conclusion The widespread of multi-rate WLAN applications makes the network management more complex and critical. Fairness and AP association are two hot issues. In multirate WLANs, some users may get starved if fairness is not carefully considered. In this paper, we investigate how to optimize user-AP association to achieve proportional fairness, and propose a new AP association algorithm termed NLAO-PF for this purpose. Although the problem of AP association for proportional fairness is NP-hard, NLAO-PF obtains a result that is guaranteed to be at least half of the optimal solution via a compensation function. Simulations confirm that our scheme can achieve proportional fairness in bandwidth allocation and enhance the aggregated throughput effectively. Moreover, in the hotspot case, the advantage of our algorithm is even more significant.
46
W. Li et al.
References 1. Tan, G., Guttag, J.: Time-based Fairness Improves Performance in Multi-rate WLANs. In: The USENIX Annual Technical Conf., Boston (2004) 2. Bertsekas, D., Gallager, R.: Data Networks, pp. 524–529. Prentice-Hall, Englewood Cliffs (1987) 3. Kelly, F.P.: Charging and rate control for elastic traffic. European Transactions on Telecommunications 8(1), 33–37 (1997) 4. Li, L., Pal, M., Yang, Y.R.: Proportional Fairness in Multi-rate Wireless LANs. In: IEEE INFOCOM, Phoenix, pp. 1004–1012 (2008) 5. Bredel, M., Fidler, M.: Understanding Fairness and its Impact on Quality of Service in IEEE 802.11. In: IEEE INFOCOM, Rio de Janeiro, pp. 1098–1106 (2009) 6. Abusubaih, M., Wolisz, A.: An Optimal Station Association Policy for Multi-Rate IEEE 802.11 Wireless LANs. In: 10th ACM Symposium MSWiM, pp. 117–123 (2007) 7. Rahul, H., Edalat, F., Katabi, D., Sodini, C.: Frequency-Aware Rate Adaptation and MAC Protocols. In: 15th ACM International Conf. MobiCom, Beijing, pp. 193–204 (2009) 8. Bejerano, Y., Han, S.-J., Li, L.E.: Fairness and load balancing in wireless LANs using association control. IEEE/ACM Trans. Networking 15(3), 560–573 (2007) 9. High-speed Physical Layer in the 5 GHz Band, IEEE Standard 802.11a (1999) 10. Azar, Y., Epstein, A.: Convex Programming for Scheduling Unrelated Parallel Machines. In: 30th ACM symposium Theory of computing, Baltimore, pp. 331–337 (2005) 11. Shmoys, D.B., Tardos, E.: An approx algorithm for the generalized assignment problem. Math. Program 62(3), 461–474 (1993) 12. Radio Resource Measurement of Wireless LANs, IEEE Standard 802.11k (2008) 13. Viterbi, A.J.: CDMA: Principles of Spread Spectrum Communication, pp. 185–186. Addison-Wesley, New York (1995) 14. Jain, R., Chiu, D.-M., Hawe, W.R.: A quantitative measure of fairness and discrimination for resource allocation in shared computer system. Digital Equipment, Technical report, DEC-TR-301 (1984)
Minimum CDS in Multihop Wireless Networks with Disparate Communication Ranges Lixin Wang1 , Peng-Jun Wan1 , and Frances Yao2 1 2
Illinois Institute of Technology, Chicago IL 60616, USA City Univesrsity of Hong Kong, Kowloon, Hong Kong
Abstract. Connected dominating set (CDS) has a wide range of applications in mutihop wireless networks. The Minimum CDS problem has been studied extensively in mutihop wireless networks with uniform communication ranges. However, in practice the nodes may have different communication ranges either because of the heterogeneity of the nodes, or due to interference mitigation, or due to a chosen range assignment for energy conservation. In this paper, we present a greedy approximation algorithm for computing a Minimum CDS in multihop wireless networks with disparate communications ranges and prove that its approximation ratio is better than the best one known in the literature. Our analysis utilizes a tighter relation between the independence number and the connected domination number.
1
Introduction
Connected dominating set (CDS) has a wide range of applications in multihop wireless networks (cf. a recent survey [2] and references therein). It plays a very important role in routing, broadcasting, and connectivity management in wireless ad hoc networks. Consider a multihop wireless network with undirected communication topology G = (V, E). A CDS of G is a subset U ⊂ V satisfying that each node in V \ U is adjacent to at least one node in U and the subgraph of G induced by U is connected. A minimum CDS (MCDS) of G is a CDS of G with the smallest size. The problem of computing a MCDS in a multihop wireless networks with uniform communications ranges has been intensively studied in the literature. This problem is NP-hard [3], and a number of distributed algorithms for constructing a small CDS in wireless ad hoc networks have been proposed in [1,5,7,8] among others. However, in practice the nodes may have different communication ranges either because of the heterogeneity of the nodes, or due to interference mitigation, or due to a chosen range assignment for energy conservation. In this paper, we assume all the nodes V lie in an Euclidean plane, and each node v has a communication radius rv . The communication topology of such a network is defined
This work was supported in part by NSF of USA under grants CNS-0831831 and CNS-0916666, by the RGC of Hong Kong under Project No. 122807, and by the National Basic Research Program of China Grant 2007CB807900, 2007CB807901.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 47–56, 2010. c Springer-Verlag Berlin Heidelberg 2010
48
L. Wang, P.-J. Wan, and F. Yao
by a graph G = (V, E) in which there is an edge between two nodes u and v if and only if they are within each other’s communication range. By proper scaling, we assume that the smallest communication radius is one and the largest communication radius is R. Under the assumption that G is connected, any pair of nodes are apart by a distance of at most n − 1 and consequently we always assume that R ≤ n − 1. MCDS in multihop wireless networks with disparate communication ranges have been studied in [6] and [9]. Thai et al. [6] applied the approximation algorithm given in [7] for MCDS in multihop wireless networks with uniform communication ranges to compute a CDS in a multihop wireless network with disparate communication ranges. The approximation bound of this algorithm involves the relation between the independence number α (the size of a maximum independent set) and connected domination number γc (the size of a minimum connected dominating set) of the communication topology. It was shown in [6] that α ≤ 10 logg R γc √
where g = 1+25 is the such a bound on α, an approxima golden ratio. With tion bound 10 logg R + 2 + log 10 logg R was derived in [6]. Xing et al. [9] targeted at obtaining a tighter approximation bound of the same approximation algorithm. claimed (in Theorem 3.1 in [9]) a tighter upper bound bound 5 They 4 6 + 8 32 logg R γc on α. However, their proof of Theorem 3.1 in [9] contains a critical error, which has no apparent fix. An explanation of this error is included in the appendix of this paper. Thus, the improved approximation bound based on the above bound of α in [9] becomes baseless. In this paper, we first derive an improved upper bound on the number of independent nodes in the neighborhood of any node. For any R ≥ 1, let R∗ = 5 + 8 logg R . We show that the number of independent nodes in the neighborhood of any node is at most R∗ . Based on this upper bound, we then prove a tighter upper bound (R∗ − 1) γc + 1 on α. Thus, the approximation bounds of the approximation algorithms presented in [6] and [9] can be improved accordingly. We will adapt the two-phased greedy approximation algorithm presented in [8] to multihop wireless networks with disparate communication ranges, and show that its approximation ratio is at most R∗ + ln (R∗ − 2) + 1. The remaining of this paper is organized as follows. In Section 2, we present an improved upper bound on the independence number α in terms of the connected domination number γc . In Section 3, we analyze the approximation bound of a two-phased greedy approximation algorithm for MCDS adapted from an algorithm originally proposed in [8] for computing MCDS with uniform communication radii. In Section 4, we summarize the paper and discuss future studies for potential improvements. Throughout this paper, D(u, r) denotes the closed disk of radius r centered at u. The Euclidean distance between two nodes u and v is denoted by uv. The cardinality of a finite set S is denoted by |S|.
Minimum CDS in Multihop Wireless Networks
2
49
Independence Number vs. Connected Domination Number
In this section, we present an improved upper bound on the independence number α in terms of the connected domination number γc . Theorem 1. α ≤ (R∗ − 1) γc + 1. Theorem 1 follows from the lemma below by using the same argument as in [7]. Lemma 1. Suppose that I is an independent set of nodes adjacent to a node u. Then |I| ≤ R∗ . The rest of this section is devoted to the proof of Lemma 1. Consider an arbitrary node u ∈ V and an independent set I of nodes adjacent to a node u. Let I1 be the set of nodes in I lying in the closed disk of radius g centered at u, and for each j ≥ 2 let Ij = v ∈ I : g j−1 < uv ≤ g j . From [4] we have |I1 | ≤ 12. The following lemma on |Ij | for j ≥ 2 was proved in [9]. Lemma 2. For any j ≥ 2, |Ij | ≤ 9. We shall further prove the following lemma on |Ij ∪ Ij+1 | for j ≥ 2. Lemma 3. For any j ≥ 2, |Ij ∪ Ij+1 | ≤ 16.
These two lemmas together imply Lemma 1 immediately. If logg R is odd, then R −1)/2
(logg
logg R
|I| = j=1 Ij ≤ |I1 | + |I2i ∪ I2i+1 | i=1 ≤ 12 + 16 · logg R − 1 /2 = 8 logg R + 4 < R∗ .
If logg R is even, then
R /2−1
logg
logg R
|I| = j=1 Ij ≤ |I1 | + |I2 | + |I2i−1 ∪ I2i | i=2 ≤ 12 + 9 + 16 logg R /2 − 1 = 8 logg R + 5 = R∗ .
So, Lemma 1 holds in either case. Next, we prove Lemma 3 by using a subtle angular arguement. Fix a j ≥ 2. We begin with the following two simple geometric lemmas, whose proofs are omitted due to the space limitation. Lemma 4. Suppose that v and w are two distinct nodes in Ij satisfying that uv ≥ uw. Then, ∠wuv > 36 ◦ . In addition, for any acute angle α, 1. if uv ≤ 2g j−1 cos α, then ∠wuv > α; g 2. if uw ≥ 2g j−1 cos α, then ∠wuv > arccos 4 cos α.
50
L. Wang, P.-J. Wan, and F. Yao
Lemma 5. Suppose that w ∈ Ij and v ∈ Ij+1 . For any acute angle α, 2
g 1. if uw ≥ 2g j−1 cos α, then ∠wuv > arccos 4 cos α; j 2. if uv ≤ 2g cos α, then ∠wuv > arccos (g cos α).
By Lemma 2, |Ij | ≤ 9. We present some necessary conditions for |Ij | = 9 in the lemma below. Lemma 6. Suppose that Ij consists of nine nodes v1 , v2 , · · · , v9 sorted in the increasing order of the distances from u. Then 1. uv9 ≥ 2g j−1 cos 39 ◦ and uv1 ≤ 2g j−1 cos 58.6 ◦ ; 2. uv8 ≥ 2g j−1 cos 39.8 ◦ and uv2 ≤ 2g j−1 cos 58.2 ◦; 3. uv7 ≥ 2g j−1 cos 43.2 ◦ and uv3 ≤ 2g j−1 cos 56.29 ◦. Proof. We will use the following fact multiple times in this proof: Suppose that I is a subset of five nodes in Ij . Then, among five consective sectors centered at u formed by the five nodes in I , at least one of them does not contain any other node in Ij . This is because |Ij \ I | = 4 < 5 and hence at least one of those five sectors does not contain any node in Ij \ I . (1) We prove the first part of lemma by contradiction. Assume to the contrary that either uv9 < 2g j−1 cos 39 ◦ or uv1 > 2g j−1 cos 58.6 ◦. Then either uvi < 2g j−1 cos 39 ◦ for all 1 ≤ i ≤ 9 or uvi > 2g j−1 cos 58.6 ◦ for all 1 ≤ i ≤ 9. In either case, the angle separation of any two nodes in Ij at u is greater than 39 ◦ by Lemma 4. If uv5 < 2g j−1 cos 50 ◦ , let vi and vk be the two nodes in {v1 , v2 , · · · , v5 } such that the sector vi uvk centered at u does not contain any other node in Ij . Then by Lemma 4, ∠vi uvk > 50 ◦ . So, the total of the nine consecutive angles at u formed by the nodes in Ij is greater than 8 · 39 ◦ +50 ◦ = 362 ◦ > 360 ◦, which is a contradiction. Next we assume uv5 ≥ 2g j−1 cos 50 ◦ . Let vi and vk be the two nodes in {v5 , v6 , · · · , v9 } such that the sector vi uvk centered at u does not contain any other node in Ij . Then by Lemma 4, ∠vi uvk > 51 ◦ . So, the total of the nine consecutive angles at u formed by the nodes in Ij is greater than 8 · 39 ◦ +51 ◦ = 363 ◦ > 360 ◦, which is also a contradiction. Therefore, the first part of the lemma holds. (2) We prove the second part of the lemma by contradiction. Assume to the contrary that either uv8 < 2g j−1 cos 39.8 ◦ or uv2 > 2g j−1 cos 58.2 ◦. We first claim that there exists a node va ∈ Ij such that the angle separation of any two nodes in Ij \ {va } at u is greater than 39.8 ◦. Indeed, if uv8 < 2g j−1 cos 39.8 ◦ , then uvi < 2g j−1 cos 39.8 ◦ for all 1 ≤ i ≤ 8 and hence the claim holds for a = 9 by Lemma 4. If uv2 > 2g j−1 cos 58.2 ◦, then uvi > 2g j−1 cos 58.2 ◦ for all 2 ≤ i ≤ 9 and hence the claim holds for a = 1 by Lemma 4. So, our claim is true. Note that the angle separation between any two nodes in Ij is greater than 36 ◦ . If uv5 < 2g j−1 cos 50 ◦ , let vi and vk be the two nodes in {v1 , v2 , · · · , v5 } such that the sector vi uvk centered at u does not contain any other node in Ij . Then by Lemma 4, ∠vi uvk > 50 ◦ . So, the total of the nine consecutive angles at u formed by the nodes in Ij is greater than
Minimum CDS in Multihop Wireless Networks
51
2 · 36 ◦ +6 · 39.8 ◦ +50 ◦ = 360. 8 ◦ > 360 ◦, which is a contradiction. Next we assume uv5 ≥ 2g j−1 cos 50 ◦ . Let vi and vk be the two nodes in {v5 , v6 , · · · , v9 } such that the sector vi uvk centered at u does not contain any other node in Ij . Then by Lemma 4, ∠vi uvk > 51 ◦ , which similarly leads to a contradiction. So, the second part of the lemma holds. (3) We prove the third part of the lemma by contradiction. Assume to the contrary that either uv7 < 2g j−1 cos 43.2 ◦ or uv3 > 2g j−1 cos 56.29 ◦ . We claim that there exist two nodes va , vb ∈ Ij such that ∠va uvb > 58.2 ◦ and the angle separation at u of any two nodes in I = Ij \ {va , vb } is greater than 43.2 ◦ . Indeed, if uv7 < 2g j−1 cos 43.2 ◦ , then uvi < 2g j−1 cos 43.2 ◦ for all 1 ≤ i ≤ 7 and hence the angle separation at u of any two nodes in Ij \ {v8 , v9 } is greater than 43.2 ◦ by Lemma 4. By part (2), we have uv8 ≥ 2g j−1 cos 39.8 ◦, which implies that ∠v8 uv9 > 58.2 ◦ by Lemma 4. Thus the claim holds with a = 8 and b = 9. Similarly, if uv3 > 2g j−1 cos 56.29 ◦, then uvi > 2g j−1 cos 56.29 ◦ for all 3 ≤ i ≤ 9 and hence the angle separation at u of any two nodes in Ij \ {v1 , v2 } is greater than 43.2 ◦ by Lemma 4. By part (2), we have uv2 ≤ 2g j−1 cos 58.2 ◦ , which implies ∠v1 uv2 > 58.2 ◦ by Lemma 4. Thus the claim holds with a = 1 and b = 2. Therefore, the claim holds in either case. Note that the angle separation between any two nodes in Ij is greater than 36 ◦ . If the sector va uvb centered at u does not contain any node in I , then the total of the nine consecutive angles at u formed by the nodes in Ij is greater than 2 · 36 ◦ +6 · 43.2 ◦ +58.2 ◦ = 389. 4 ◦ > 360 ◦ , which is a contradiction. So, we assume that the sector va uvb centered at u contains at least one node in I . Then, the total of the nine consecutive angles at u formed by the nodes in Ij is greater than 4 · 36 ◦ +5 · 43.2 ◦ = 360.0 ◦, which is also a contradiction. So, the third part of the lemma follows.
Now are ready to prove Lemma 3. Assume to the contrary that |Ij ∪ Ij+1 | = l ≥ 17. Let Ij ∪ Ij+1 = {vi : 1 ≤ i ≤ l} where v1 , v2 , · · · , vl are sorted in the increasing order of the distances from the node u. By Lemma 2, we have max {|Ij | , |Ij+1 |} ≤ 9. Thus, max {|Ij | , |Ij+1 |} = 9 and min {|Ij | , |Ij+1 |} ≥ 8 as l ≥ 17. We consider two cases: Case 1: |Ij | = 9. Then |Ij+1 | ≥ 8. By Lemma 6, we have uv7 ≥ 2g j−1 cos 43.2 ◦ . Let J = {v7 , v8 , v9 }. Then the angle separation between any two nodes in J at u is greater than 56.29 ◦. We further consider two subcases: Subcase 1.1: There exist two nodes va , vb ∈ J such that the sector va uvb centered at u does not contain any node in Ij (see Fig. 1(a)). Let vi and vk be the two nodes in Ij+1 such that the sector vi uvk contains va and vb but does not contain any other node in Ij+1 , and vi , va , vb and vk are in the clockwise direction with respect to u. Then min{∠vk uvb , ∠va uvi } > 26 ◦ by Lemma 5(1). Thus, ∠vk uvb + ∠vb uva + ∠va uvi > 2 · 26 ◦ +56.29 ◦ = 108.29 ◦ .
52
L. Wang, P.-J. Wan, and F. Yao
vi
v’7 v’8 v7
va
v8
u
v’’ 7
u
vb v’’ 8 v9 v’9
vk v’’ 9 (a)
(b)
Fig. 1. Figure for Case 1: (a) a sector va uvb for a, b ∈ {7, 8, 9} does not contain any node in Ij+1 ; (b) every sector for va uvb for each a = 7, 8 and 9 contains a node in Ij+1 .
Hence, the total of the |Ij+1 | consecutive angles at u formed by the nodes in Ij+1 is greater than 7 · 36 ◦ +108.29 ◦ = 360. 29 ◦ > 360.0 ◦ , which is a contradiction. Subcase 1.2: For any two nodes va , vb ∈ J, the sector va uvb centered at u contains at least one node in Ij+1 (see Fig. 1(b)). For each a = 7, 8 and 9, let va , va ∈ Ij+1 satisfying that va is the only node contained in the sector va uva centered at u among all the nodes in Ij+1 ∪ J. Then by Lemma 5(1) and Lemma 6, we have ∠v7 uv7 + ∠v8 uv8 + ∠v9 uv9 > 2 · (26 ◦ +31.5 ◦ +32.5 ◦) = 180 ◦ . Hence, the total of the |Ij+1 | consecutive angles at u formed by the nodes in Ij+1 is greater than 5 · 36 ◦ +180 ◦ = 360.0 ◦, which is a contradiction. Case 2: |Ij | = 8. Then |Ij+1 | = 9. By Lemma 6, we have uv11 ≤ 2g j cos 56.29 ◦. Let J = {v9 , v10 , v11 }. By Lemma 4, the angle separation between any two nodes in J at u is greater than 56.29 ◦ . We further consider two subcases: Subcase 2.1: There exist two nodes va , vb ∈ J such that the sector va uvb centered at u does not contain any node in Ij (see Fig.2(a)). Let vi and vk be the two nodes in Ij such that the sector vi uvk contains va and vb but does not contain any other node in Ij , and vi , va , vb and vk are in the clockwise direction with respect to u. Then min{∠vk uvb , ∠va uvi } > 26 ◦ by Lemma 5(2). Thus, ∠vk uvb + ∠vb uva + ∠va uvi > 2 · 26 ◦ +56.29 ◦ = 108.29 ◦ .
Minimum CDS in Multihop Wireless Networks
vi
v11
u
v’10
v’11
va
53
v10
u
v’’ 10
v’’ 11 vk
vb
v’9 v’’ 9 v9
(a)
(b)
Fig. 2. Figure for Case 2: (a) a sector va uvb for a, b ∈ {9, 10, 11} does not contain any node in Ij ; (b) every sector for va uvb for each a = 9, 10 and 11 contains a node in Ij .
Hence, the total of the 8 consecutive angles at u formed by the nodes in Ij is greater than 7 · 36 ◦ +108.29 ◦ = 360. 29 ◦ > 360.0 ◦ , which is a contradiction. Subcase 2.2: For any two nodes va , vb ∈ J, the sector va uvb centered at u contains at least one node in Ij (see Fig.2(b)). For each a = 9, 10 and 11, let va , va ∈ Ij satisfying that va is the only node contained in the sector va uva centered at u among all the nodes in Ij ∪ J. Then by Lemma 5(2) and Lemma 6, we have ∠v9 uv9 + ∠v10 uv10 + ∠v11 uv11 > 2 · (26 ◦ +31.5 ◦ +32.5 ◦) = 180 ◦ .
Hence, the total of the 8 consecutive angles at u formed by the nodes in Ij is greater than 5 · 36 ◦ +180 ◦ = 360.0 ◦, which is a contradiction. Thus, in every case we have reached a contradiction. So, we must have |Ij ∪ Ij+1 | ≤ 16. This completes the proof of Lemma 3.
3
Greedy Approximation Algorithm for MCDS
In this section, we present a greedy algorithm adapted from the two-phased greedy approximation algorithm originally proposed in [8] for computing a CDS in a multihop wireless network with uniform communication ranges to multihop wireless networks with disparate communication ranges. The greedy algorithm consists of two phases. The first phase selects a maximal independent set (MIS) I of G. Specifically, we construct an arbitrary rooted spanning tree T of G, and select an MIS I of G in the first-fit manner in the breadth-first-search ordering in T . The second phase selects a set C of connectors to interconnect I . For
54
L. Wang, P.-J. Wan, and F. Yao
any subset U ⊆ V \ I, f (U ) denotes the number of connected components in G [I ∪ U ]. For any U ⊆ V \ I and any w ∈ V \ I, the gain of w with respect to U is defined to be f (U ) − f (U ∪ {w}). The second phase greedily selects C iteratively as follows. Initially C is empty. While f (C) > 1, choose a node w ∈ V \ (I ∪ C) with maximum gain with respect to C and add w to C. When f (C) = 1, then I ∪ C is a CDS. Let C be the output of the second phase. We have the following bound on |C|. Lemma 7. |C| ≤ (ln (R∗ − 2) + 2) γc . The proof of the above lemma is similar to that in [8] and is omitted due to the space limitation. From Theorem 1 and Lemma 7, we obtain the following bound on the size of the CDS output by the greedy algorithm. Theorem 2. |I ∪ C| ≤ (R∗ + ln (R∗ − 2) + 1) γc + 1.
4
Discussion
The relation between the independence number α and the connected domination number γc plays a key role in deriving the approximation bounds of various twophased greedy approximation algorithms adapted for MCDS of multihop wireless networks with disparate communication ranges [6] [8] [9]. In this paper, we first proved that α ≤ (R∗ − 1) γc + 1, where R∗ = 5 + 8 logg R for any R ≥ 1. From this relation, we then derived an approximation bound R∗ + ln (R∗ − 2) + 1 of the two-phased greedy approximation algorithm adapted from [8]. This approximation bound is better than the known ones obtained in [6] and [9]. Tighter relation between α and γc may be derived with more sophisticated analyses. A possible approach of obtaining tighter relation between α and γc is to develop a tighter bound on the number of independent nodes that can be packed in the neighborhood of a pair of adjacent nodes. An attempt along this approach has been made in [9], but the argument in [9] contains a critical error. However, we do believe that this approach is very promising to achieve tighter relation between α and γc .
References 1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In: ACM Mobihoc (2002) 2. Blum, J., Ding, M., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329–369. Kluwer Academic Publisher, Dordrecht (2004) 3. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discrete Mathematics 86, 165–177 (1990) 4. Fodor, F.: The densest packing of 13 congruent circles in a circle. Beitrage Algebra Geom. 44(2), 431–440 (2003)
Minimum CDS in Multihop Wireless Networks
55
5. Li, Y.S., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On Greedy Construction of Connected Dominating Sets in Wireless Networks. Wiley Journal on Wireless Communications and Mobile Computing 5(8), 927–932 (2005) 6. Thai, M.T., Wang, F., Liu, D., Zhu, S., Du, D.-Z.: Connected dominating sets in wireless networks with different communication ranges. IEEE Transactions on Mobile Computing 6(7), 721–730 (2007) 7. Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. ACM/Springer Mobile Networks and Applications 9(2), 141–149 (2004); A preliminary version of this paper appeared in IEEE INFOCOM 2002 (2002) 8. Wan, P.-J., Wang, L., Yao, F.: Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks. In: IEEE ICDCS 2008, pp. 337–344 (2008) 9. Xing, K., Cheng, W., Park, E.K., Rotenstreich, S.: Distributed Connected Dominating Set Construction in Geometric k-Disk Graphs. In: IEEE ICDCS 2008, pp. 673–680 (2008)
Appendix In this appendix, we explainthe error in the proof of Theorem 3.1 in [9] which claimed that α ≤ 4 65 + 8 32 logg R γc , where α is the independence number and γc is the connected domination number. Let S be any maximum independent set of G and OP T be any MCDS of G. Then |I| = α and |OP T | = γc . In the proof of this theorem in [9], the γc nodes u1 , u2 , · · · , uγc in OP T are sorted in radius-decreasing order. Let 1 denote the number of nodes that are adjacent to u1 . For any 2 ≤ j ≤ γc , let j denote the number of nodes that are adjacent to uj but none of nodes u1 , u2 , · · · , uj−1 . Consider a spanning tree T of G[OP T ], the subgraph of G induced by OP T . The nodes in OP T are classified into two types. A node ui ∈ OP T is of the first type if and only if ui has the smallest index among itself and all of its neighbors in T . Then, Lemma 3.2 in [9] claimed that if a node ui ∈ OP T is of the second type, then i ≤ 4 + 7 logg R . The proof of Lemma 3.2 in [9] contains a critical error in bounding the number of independent nodes that can be packed in the neighborhood of two adjacent nodes. For each node v and each j ≥ 2, Aj (v) denotes the annulus centered at v of inner radius g j−1 and outer radius g j . Suppose that u and v are a pair of adjacent nodes with ru ≥ rv = uv. Let j ≥ 2 and Ij (v) ⊂ Aj (v) be an independent set of nodes adjacent to v but not adjacent to u. Then Lemma 3.2 in [9] claimed that |Ij (v)| ≤ 7. This claim is incorrect. An instance illustrated in Fig. 3 shows a packing of nine independent nodes adjacent to the node v but not adjacent to the node u in an annulus Aj (v) with j ≥ 2. In this instance, the five nodes v1 , v2 , v3 , v4 and v5 lie on the circle ∂D(v, g j−1 +ε) in the counterclockwise direction satisfying that u, v and v3 are on the same line and ∠vi vvi+1 = 74 ◦ for each 1 ≤ i ≤ 4 and ∠v5 vv1 = 64 ◦ , where ε > 0 is sufficiently small and will be chosed later. These five nodes lie inside Aj (v) but very close to its inner circle. For each i = 6, 7, 8 and 9, the node vi lies on the circle ∂D(v, g j − ε) satisfying that vvi is the angle bisectors of ∠vi−5 vvi−4 . These four nodes lie inside Aj (v) but very close to its outer circle. The communication radius of vi
56
L. Wang, P.-J. Wan, and F. Yao
is vvi for each 1 ≤ i ≤ 9. We further assume that j ≥ 2 is small enough such that uv ≥ 2g j−1 . The first five nodes are independent as their mutual angle separations at v are all greater than 60 ◦ . Similarly, the last four nodes are also independent as their angle separations at v are also all greater than 60 ◦ . In addition, choose ε sufficiently small such that each of the first five nodes and each of the last four nodes are independent as their angle separation at v is strictly greater than 36 ◦ . Therefore, all the nine nodes are independent with each other for sufficiently small ε. Since uv ≥ 2g j−1 and the five nodes v1 , v2 , v3 , v4 and v5 lie close to the inner circle of Aj (v), we choose ε sufficiently small such that uvi > vvi = rvi for all 1 ≤ i ≤ 5. Note that uv is the angle bisector of ∠v5 vv1 . Then ∠uvv1 = 32 ◦ and ∠uvv6 = 69 ◦ . Thus, v6 is on the left-hand side of the vertical line v1 v5 since vv6 cos ∠uvv6 < g j cos 69 ◦ < g j−1 cos 32 ◦ < vv1 cos ∠uvv1 . Similarly, v9 is on the left-hand side of the vertical line v1 v5 . Therefore, uvi > vvi = rvi for all 6 ≤ i ≤ 9. Thus none of these nine neighbors of v is adjacent to the node u. Hence, we have |Ij (v)| = 9 in this example. Therefore, the claim |Ij (v)| ≤ 7 in Lemma 3.2 in [9] is incorrect. This error further propagates to the proof of Theorem 3.1 in [9].
v6
v2
v7
v1 v3
u
v v5
v8
v4
v9
Fig. 3. A packing of nine independent nodes adjacent to the node v but not adjacent to the node u in an annulus Aj (v) with j ≥ 2
Minimum Edge Interference in Wireless Sensor Networks Trac N. Nguyen, Nhat X. Lam, D.T. Huynh, and Jason Bolla University of Texas at Dallas, Richardson TX 75080, USA {nguyentn,nxl081000,huynh,jab018600}@utdallas.edu http://www.utdallas.edu
Abstract. The approach of using topology control to reduce interference in wireless sensor networks has attracted attention of many researchers. There are several definitions of interference in the literature. In a wireless sensor network, the interference at a node may be caused by an edge that is transmitting data, or it occurs because the node itself is within the transmission range of another. The interference load of an edge is the number of nodes that are in the disks defined by the end nodes of this edge with a radius which is either the Euclidean distance or the power level of the end nodes. In this paper we show that the problem of assigning power level to a set of nodes in the plane to yield a connected geometric graph whose edges have bounded interference is NP-complete under both edge interference definitions. We also study the performance of a number of heuristics through simulation. Keywords: wireless sensor networks, interference, NP-completeness, geometric graphs, heuristic.
1
Introduction
One well known approach to minimize interference in Wireless sensor networks is to use topology control. This approach was first discussed by a number of researchers including Burkhart et al. [4] and Rickenbach, et al. [11]. The authors in [4] defined the notion of interference load of an edge in a network, and showed an interesting result that certain sparse networks may not have low interference. Following the work in [4], the authors in [11] introduced a notion of node interference that is caused by surrounding nodes whose transmission range includes the given node. They analysed the special case of the exponential 1-dimensional node chain which √is also called the highway model. They showed that this sparse network has Ω( n) node interference, where n is the number of nodes in the √ network. The authors described an algorithm that provides an O( 4 δ) approximation of the optimal connectivity preserving topology in the highway model where δ is the maximum node degree. Similarly, Moaveni-Nejad and Li [9], and Johansson and Carr-Motyckovaa [7] focused on the notion of interference that is based on edges of the network. [7] gave a distributed algorithm called Average Path Interference that tries to preserve the spanner property of the original graph while reducing the interference in the network at the same time. [9] showed G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 57–67, 2010. c Springer-Verlag Berlin Heidelberg 2010
58
T.N. Nguyen et al.
that the relative neighborhood graph and local spanning tree algorithms have a constant bounded average interferences ratio. The NP completeness of both types of node interference were discussed by Wu and Liao [14], Bilo and Proietti [2] and Buchin [3]. [14] extended the work of [4] with an NP-completeness proof for minimizing edge-based interference for general graphs along with a couple of heuristics, and [3] provided an NP-completeness proof for finding a spanning tree with minimum node interference for grid graphs. For the receiver-based interference model, in [2] the authors showed among other results that the problem of minimizing the maximum node interference is hard to approximate. On the √ other hand, [6] showed that for a set of n points in the plane a network with O( Δ) interference can be constructed using computational geometric tools (Δ is the maximum interference in the uniform-radius network). They left open the question whether this problem is NP-hard including the 1-dimensional case. [10] was able to provide an answer to some of the questions raised in [6] by showing that minimizing receiver-based node interference is NP-complete for the 2-dimensional case. However, for the sender-based model minimizing node interference is solvable in polynomial time as shown in [2]. In this paper, we are concerned with edge interference. We study the problem of assigning power to nodes in the plane to form a connected graph with bounded edge interference. Specifically, we prove that the problem of assigning power to a set of nodes in the plane to yield a connected geometric graph whose edges have bounded interference is NP-complete. Our result is significant as it provides an NP completeness result for geometric graphs for some of the issues discussed in [4] and [7]. In fact, for this interference model there are no NP completeness results to date. Moreover, this result is surprising since edge interference is quite similar to sender-based node interference which was shown to be solvable in polynomial time by [2]. Note that in our work as well as most of the works in wireless sensor networks, two nodes are connected by an edge if they are within the transmission range of one another. This definition is not strictly followed in a number of papers including Benkert et al. [1] and Sharma et al. [12]. We also study the performance of a number of heuristics through simulation. The rest of this paper is organized as follows. Section II provides the definitions and explanations used in this paper. Section III is devoted to the NP completeness result, and Section IV discusses the performance of some heuristics. Section IV contains some concluding remarks.
2
Preliminaries
Consider a set V of transceivers (nodes) in the plane. Each node u is assigned a power level denoted by p(u). The signal transmitted by node u can only received by a node v if the distance between u and v, denoted by d(u, v), is ≤ p(u). We only consider the bidirectional case in which a communication edge exists between two nodes u and v, (u, v) if and only if both power levels p(u) ≥ d(u, v) and p(v) ≥ d(u, v). Thus, the set V of nodes in the plane together with the power levels assigned to the nodes define a geometric (also known as intersection) graph G = (V, E). A geometric graph is said to be planar if no edge crosses another.
Minimum Edge Interference in Wireless Sensor Networks
59
In this paper we are concerned with two definitions of edge interference described in [4] and [7]. Assuming that there is no obstacle blocking the broadcasting range of a node, the two definitions of the edge interference load are as follows. Let D(u, r) be the broadcasting disk of node u with radius r. The (Euclidean) distance-based edge interference (DEI) is defined in [7] as follow: DEI(u, v) := |{w ∈ V |w ∈ / {u, v} and w ∈ D(u, d(u, v)) or w ∈ D(v, d(v, u))}| and for a geometric graph G = (V, E) DEI(G(V, E)) := max(u,v)∈E {DEI(u, v)
(1)
Similarly, the power level-based edge interference (PEI) is in [4] as follows: P EI(u, v) := |{w ∈ V )|w ∈ / {u, v} and w ∈ D(u, p(u)) or w ∈ D(v, p(v))}| and for a geometric graph G = (V, E) P EI(G = (V, E)) := max(u,v)∈E {P EI(u, v)}
(2)
Intuitively, the interference load of an edge is the total number of nodes that are in the area covered by the disks created by the two end nodes of that edge. The radius of a disk is equal the Euclidian length of the edge (DEI case) or the power level usage (PEI case).
3
The NP-Completeness of Minimum Edge Interference in Geometric Graphs
In this section, we first prove the NP-completeness of the problem of assigning power levels to nodes in the plane to produce a connected geometric graph G with bounded edge interference load DEI(G) (MDEICG). As a corollary, the problem of assigning power to nodes to produce a geometric graph G with bounded P EI(G) (MPEICG) is also NP-complete. Problem MDEICG: Given a set of N nodes V = {v1 , v2 , ..., vN } in the plane, a set of M power levels P = {p1 , p2 , .., pM } at which a node can transmit, and a positive number R. Is there a power assignment to all nodes so that it induces a connected geometric graph G(V,E) such that DEI(G) is ≤ R? The problem MPEICG is defined similarly. In the following we show that MDEICG is NP-complete. Theorem 1. MDEICG is NP-complete. Proof. It is straightforward to show that MDEICG is in NP. To prove its NPhardness, we construct a polynomial time reduction from the planar 3-SAT problem (P3SAT) which was proven NP-complete in D. Lichtenstein [8]. Consider an instance φ of P3SAT, and the planar instance graph G of φ, where G = (X ∪ C, E ∪ E ) with edge sets E = {{x, c}|x ∈ C ∨ ¬x ∈ C} and E = {{xi , xi+1 }|1 ≤ i ≤ n − 1}.
60
T.N. Nguyen et al.
(a) Gadgets used in representing a variable x in a P3SAT instance.
(b) A series of gadgets representing a variable x of a P3SAT instance. Fig. 1. Gadgets
To construct an instance < V , P, R > of MDEICG, we first create two gadgets for each variable of φ. As shown in Figure 1(a), each gadget for variable x contains 4 nodes, which are 2 pairs of x and ¬x. These nodes are connected through straight and curved edges. The left gadget has 2 curved edges and 4 straight edges that form a square, whereas the right gadget has 3 straight edges and two curved edges. To have sufficient nodes for x so that we can connect x to some clause nodes, we replace a variable node x in G by a chain of these two gadgets in such a way that two gadgets at the ends of the chain have four straight edges, whereas every in-between gadget has three straight edges. This way, every node in the chain of gadgets has a degree of at least 3. Moreover, every second gadget has its nodes and edges rearranged as depicted in Figure 1(b). Note that consecutive gadgets are connected by two parallel straight edges. If the degree of node x is d, then the number of x s gadgets in this chain is 3 ∗ d. From each chain of gadgets representing a variable node in G, we only use the nodes with degree 3, to connect to a clause node. Furthermore, the variable link that connects all variables should enter each chain of gadgets via a degree 3 node at one end and exit via another degree 3 node at the other end. Thus, the new graph (also denoted G for convenience) obtained from the original graph has a maximum degree of 4 while the planarity of the graph is preserved. Next, we use Valiant’s result [13] to embed the graph G with maximum degree 4 into the Euclidean plane: A planar graph with maximum degree 4 can be embedded in the plane using O(|V |) area in such a way that its vertices are at integer coordinates and its edges are drawn so that they are made up of line segments of form x = i or y = j, for integers i and j. Moreover, this embedding process can easily be designed to satisfy the additional requirement that each line segment drawn to connect two original vertices of the graph G must be of length at least 6, and any two parallel line segments in the embedded graph are at least 6 units apart. Let us call the units of the embedded graph G original units. Each original unit is divided further into 12 smaller “pieces” of equal length. Let the original unit be δ. We define the radii ri , 1 ≤ i ≤ 8 as follows: ri := (i/12) ∗ δ. For the sake of convenience let us call the variable and clause nodes of G embedded in
Minimum Edge Interference in Wireless Sensor Networks
(a) Nodes added on the line segments replacing a straight edge (x,¬x) of G(V, E) at variable node x with degree 3.
61
(b) Nodes added on the line segments replacing a straight edge (x,¬x) of G(V, E) on a variable link connecting y and x.
Fig. 2. Nodes added on the line segments in cases
the plane the variable and clause nodes, respectively. First, we have to make a change in the line segments representing a straight edge connecting x to ¬x in the embedded graph G as follows. 1. If these segments are strictly either horizontal or vertical segments, we create a U shape from these original segments. Starting from either node x or ¬x, we move 2 segments, say the third and the fourth segments, 2 units apart from their current location. We then connect both ends of these segments using additional 2-unit segments that form a U shape. 2. For the corners created by perpendicular unit segments, pick one corner and let this corner be the marked corner. Note that from the previous step, every line segments representing a straight edge in G connecting x to ¬x must have one marked corner. At the marked corner, replace the two perpendicular unit segments by a segment connecting two grid nodes (see Figure 4.) This segment is called a slanted segment. We now further modify each line segment by placing additional nodes to create the instance < V , P, R > of MDEICG as follows: 1. On every line segments, add one node at every grid point. Lets call these nodes grid nodes (e.g. nodes g s in Figure 2, 3 and 4.) 2. On the line segments representing the variable link connecting different variable gadgets chains, add 2 nodes to each unit to divide it into 3 equal pieces of length r4 each (see Figure 2(b)). 3. On the line segments representing the connection from a variable node to a clause node, add the first node (node o in Figure 3(b)) at distance r8 from the variable node, and successively add nodes at distance r4 from the previous one until the clause node is reached.
62
T.N. Nguyen et al.
(a) Nodes added on the line segments replacing a straight edge (x,¬x) of G(V, E) at variable node x with degree 4.
(b) Nodes added on the line segments replacing a straight edge (x,¬x) of G(V, E) on a connection to a clause node C.
Fig. 3. Node added on the line segments in cases
4. For a variable node with degree 3, add two nodes at distance r4 to the unit that does not correspond to any segment. (See nodes d and t in Figure 2(a).) 5. On the line segments representing a curved edge in G, add two nodes at distance r8 from the variable nodes. Then successively add nodes at distance r4 between these two new nodes (e.g. node i in Figures 2(a), 2(b), 3(a), 3(b) is at distance r8 from the variable node x, and the subsequent nodes are at distance r4 from the preceding ones.) 6. On the line segments representing a straight edge connecting a variable node x and its negated node ¬x of G, add new nodes on every unit line segment by the following steps: – On every unit segment add a node at distance r4 from the grid node. Let us call these nodes support nodes. (See nodes s’s in Fig. 2, 3 and 4) – Between the support node and the grid node on each unit segment, add one node (away from the segment), called auxiliary node, so that its distance to the support node or the grid node is exactly r8 . Moreover, these auxiliary nodes are added in such a way that they are not close to the other auxiliary nodes added on other unit segments (see nodes a s in Figures 2, 3 and 4.) – Between the support node and the variable node on every unit segment incident with a variable, add a node at distance r4 from the variable node and the support node. – In the middle of each slanted segment, add two nodes called middle nodes at distance r8 from the end (grid) nodes of the segment. Note that the distance between the two middle nodes is about 0.97. (See nodes k and w in Figure 4.) On both sides of the middle nodes, two more nodes are added such that one node is at distance r2 from the grid node and the other is at distance r2 from the closest middle node. (See Figure 4.) The
Minimum Edge Interference in Wireless Sensor Networks
63
Fig. 4. Nodes added on the line segments replacing a straight edge (x,¬x) of G(V, E). These line segments contain a slanted segment and segments that form a U shape.
distance between these two nodes is r4 . Between the two middle nodes and away from the line segment add an auxiliary node that is at distance r8 from each of the middle nodes. – Consider two perpendicular adjacent unit segments. On one of the unit segment add two nodes between the support node and the grid node so that the distance between these two nodes is r4 . These two nodes are at distance r2 to the grid node and the support node. On the remaining unit segments, add 2 pairs of nodes between the support node and the grid node. The distance of nodes in each pair is r1 . The distance between two adjacent pairs of nodes is r4 , and each of them is at distance r2 to the grid node or to the support node. These two pairs of nodes form a group of 4 nodes. (See Figures 2, 3 and 4.) Let P := {0, r1 , r2 , ..., r8 } and R := 8. The correctness of the above polynomialtime reduction follows from the following claim: Claim. The instance φ of P3SAT is satisfiable if and only if the MDEICG instance < V , P, R > has a power assignment that yields a connected geometric graph G (V , E ) such that DEI(u, v) of each edge (u, v) ∈ E is ≤ R. Intuitively, some node on a straight edge connecting a variable node and its negated node must be assigned a high power level for the resulting graph to be connected. Moreover, if a variable node is assigned a high power level, then its negated node must be assigned a low power level due to the interference bound; or vice versa. The proof of the Claim is omitted due to space limitation. From the Claim, Theorem 1 follows.
64
T.N. Nguyen et al.
Then the NP completeness of MPEICG follows as a corollary. Theorem 2: MPEICG is NP-complete. Proof. The proof of Theorem 2 is similar to the proof of Theorem 1, and is omitted.
4 4.1
Heuristics and Their Performance Heuristics
Node interference approach. Our first approach is built on the sender-based node interference problem, where the interference load of a node v is the number of nodes within the broadcasting disk of v and the problem is to minimize the maximum node interference. This problem has been shown to be solved in polynomial time in [2] through a simple greedy heuristic called OPT-MINMAXSIP. Based on this result, we propose the Node Power Level Search heuristic (NPLS) which first computes the minimum sender-based node interference, and then reduce the power level for each node while preserving connectivity. Although this step does not necessarily decrease the maximum node interference of the graph, it may improve the interference load of other nodes, and hence the interference load of the edges. The pseudo code of this algorithm is reported in Figure 5. Input: a set V of nodes in the plane Output: A power assignment P that yields a connected geometric graph whose edge interference is minimized 1 Using the greedy technique, find a power assignment P that yields a minimum node interference graph // Reduce power levels of nodes while maintaining connectivity 2 for each node v ∈ V 3 Using binary search find the smallest power level for P [v] while P yields a connected graph 4 return the power assignment P Fig. 5. Node-Power-Level-Search
Minimum spanning tree approach. The basic idea of this approach is to find a minimum spanning tree for a given complete graph. We use this approach in two different algorithms, the distance-based minimum spanning tree (DMST) algorithm and the interference-based minimum spanning tree (IMST) algorithm. The main difference between these two algorithms is the definition of the edge weight. The former uses the Euclidean distance as edge weight while the latter uses the DEI edge interference load. In implementing these two algorithms, we use Kruskals algorithm [5] to find the minimum spanning tree. This algorithm uses two well-known subroutines find-set and union. find-set(u) is to find the root of tree-based connected component containing node u whereas union(u, v) is to connect two connected components of u and v. The details of these two subroutines can be found in [5].
Minimum Edge Interference in Wireless Sensor Networks
65
Figure 6 contains the pseudo code of the DMST algorithm. Observe that adding an edge may increase the power levels assigned to the two end nodes, thereby creating new edges (adjacent to the newly added edge). This is taken into account in lines 8-9 in Figure 6. Input: a set V of nodes in the plane Output: A power assignment P that yields a connected geometric graph whose edge interference is minimized 1 E = set of edges between all nodes in V 2 A=∅ 3 w(e) = length of e for all e ∈ E 4 Sort E in non-decreasing order according to weights w 5 for each edge (u, v) ∈ E 6 if find-set(u) = find-set(v) 7 add edge (u, v) to A and union(u, v) 8 B = edges created by adding (u, v) 9 A = A B and E = E \ B 10 Compute the power assignment P from A 11 return P Fig. 6. Distance-based-Minimum-Spanning-Tree
Regarding IMST algorithm, a possible improvement is to modify the definition of edge weight. As pointed out above, adding an edge may create some higher interference edges. So the weight of an unprocessed edge e is not its interference load, but the maximum interference load of those edges, which would be created if e were chosen to be added to A, including e itself. At every step, after A is updated, we recalculate the weights of unprocessed edges and sort them in non-decreasing order. 4.2
Experimental Results
In our experiments, we only consider geometric graphs. We randomly generate 100 nodes on an area of size of 10000x10000. For each graph, we run all three algorithms. We use the percentage difference as a metric to evaluate their performance. We compare IMST against the other two, namely DMST and NPLS. The results for the DEI as well as the PEI models in the table below demonstrate that the IMST algorithm performs significantly better. With regard to the DEI model, DMST and NPLS are always worse than IMST. However, for the PEI model, the DMST algorithm in some cases performs better as the negative value in Table I shows. By analysing the data concerning these cases, we are able to generate a simple example where DMST works better than IMST. In this case, IMST gives a graph whose maximum edge interference is 5 with the maximum interference edge (5, 6) (Figure 7(a)), while the maximum interference found by DMST is 4 (Figure 7(b)). Remark. Note that we have not provided a formal analysis of the running time of the above heuristics as the techniques used are well known. For efficient implementation of the algorithms using computational-geometric techniques, the
66
T.N. Nguyen et al. Table 1. Experimental Results
Min Max Average Better Worse Equal
Distance based DMST NPLS 0.00% 0.00% 200.00% 83.33% 23.57% 28.41% 0 0 136 163 64 37
Power Level based DMST NPLS -36.36% 14.29% 200.00% 114.29% 19.85% 61.32% 9 0 125 200 66 0
y 15
y 15
2
2 10
10
5
5 6
5 4
0
1
3
0
6
5 0 10
(a) IMST algorithm
4
0 20 x
0
1
3
0 10
20 x
(b) DMST algorithm
Fig. 7. An Example Showing The Better Result of DMST
reader is referred to [1]. We also note that the improvement described in Lines 9-12 in the IMST algorithm does not show any concrete result in our simulation as the connected geometric graphs appear to have minimum edge interference even without this improvement. It would be interesting to formally investigate how well IMST performs.
5
Conclusions
In this paper we have shown that the problems of minimizing DEI or PEI interference are both NP-complete for (planar) connected geometric graphs. This is the first NP completeness result concerning the edge interference model for geometric graphs. We also compare the performance of some heuristics through simulation. These results provide new insight on some of the issues discussed in [4] and [7].
References 1. Benkert, M., Gudmundsson, J., Haverkort, H., Wolff, A.: Introduction to Algoˇ rithms. In: Wiedermann, J., Tel, G., Pokorn´ y, J., Bielikov´ a, M., Stuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 166–176. Springer, Heidelberg (2006) 2. Bil` o, D., Proietti, G.: On the Complexity of Minimizing Interference in Ad-Hoc and Sensor Networks. Theorectical Computer Science 402, 43–55 (2008)
Minimum Edge Interference in Wireless Sensor Networks
67
3. Buchin, K.: Minimizing the Maximum Interference is Hard (2008), http://arxiv.org/abs/0802.2134 4. Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does Topology Control Reduce Interference? In: MOBIHOC 2004, pp. 9–19 (2004) 5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Constructing InterferenceMinimal Networks. Section 23.2: The Algorithms of Kruskal and Prim, pp. 567–574. McGraw-Hill, New York (2001) ISBN 0-262-03293-7 6. Halld´ orsson, M.M., Tokuyama, T.: Minimizing Interference of a Wireless Ad-Hoc Network in a Plane. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2006. LNCS, vol. 4240, pp. 71–82. Springer, Heidelberg (2006) 7. Johansson, T., Carr-Motyckova´ a, L.: Reducing Interference in Ad Hoc Networks Through Topology Control. In: DIALM-POMC 2005, pp. 17–23 (2005) 8. Lichtenstein, D.: Planar Formulae And Their Uses. SIAM J. of Compt. 11(23) (1982) 9. Moaveni-Nejad, K., Li, X.-Y.: Low-Interference Topology Control for Wireless Ad Hoc Networks. Ad Hoc and Wireless Sensor Networks 1, 41–64 (2005) 10. Nguyen, T.N., Huynh, D.T.: Minimum Interference Planar Geometric Topology in Wireless Sensor Networks. In: Liu, B., Bestavros, A., Du, D.-Z., Wang, J. (eds.) WASA 2009. LNCS, vol. 5682, pp. 149–158. Springer, Heidelberg (2009) 11. Rickenbach, P.V., Schmid, S., Wattenhofer, R., Zollinger, A.: A Roburst Interference Model for Wireless Ad-Hoc Networks. In: Proc. 19th IEEE Int. Par. and Dist. (2005) 12. Sharma, A., Thakral, N., Udgata, S., Pujari, A.: Heuristics for Minimizing Interference in Sensor Networks. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol. 5408, pp. 49–54. Springer, Heidelberg (2009) 13. Valiant, L.: Universality Considerations in VLSI Circuits. IEEE Trans. on Compupters C-30, 135–140 (1981) 14. Wu, K.-D., Liao, W.: On Constructing Low Interference Topology in Multihop Wireless Networks. Int. J. of Sensor Networks 2, 321–330 (2007)
Maximum Weighted Independent Set of Links under Physical Interference Model Xiaohua Xu, Shaojie Tang, and Peng-Jun Wan Illinois Institute of Technology, Chicago IL 60616, USA
Abstract. Interference-aware scheduling for wireless communications is crucial to improve the network throughput. In this paper, we study the problem of Maximum Weighted Independent Set of Links (MWISL) under the physical interference model in wireless networks. Given a set of communication links distributed in a two-dimensional Euclidean plane, assume each link is associated with a positive weight which represents the benefit of transmitting along the link, the objective is to seek an independent set of links subject to the physical interference constraints with maximum weighted sum. To the best of our knowledge, no algorithm for MWISL under physical interference model has been proposed. We focus on MWISL in the oblivious power assignment setting.
1 Introduction Link scheduling in wireless networks plays a critical role for wireless networking performances, especially when the network has stringent quality of service restrictions. One challenge for link scheduling lies in interferences among concurrent transmissions. Unlike the wired networks, the signal interference casts significant effect on the fundamental limit on the data throughput that any scheduling protocols (centralized or distributed) can achieve. It is well-known that a number of scheduling problems (e.g., maximum throughput scheduling) become NP-hard to solve when considering wireless interference, while their counter-parts are solvable in polynomial time for wired networks. Thus, the scheduling protocols for wireless networks (even the benchmark performances obtained by centralized scheduling approaches) often rely on heuristics that approximately optimize the throughput. We address a fundamental problem for scheduling in wireless communications: Maximum Weighted Independent Set of Links (MWISL): given an input set of links, a subset of links is an independent set of links iff they can transmit concurrently. Assume each link is associated with a positive weight (representing the benefit of transmitting along the link), the objective is to seek an independent set of links with maximum weighted sum under given interference model. We focus on MWISL under physical interference model, where a signal is received successfully if the Signal to Interferenceplus-Noise Ratio is above a threshold depending on hardware and coding method. In this practical model, the definition of a successful transmission accounts also interference generated by transmitters located far away. Thus, traditional methods in graphbased interference models (e.g., protocol interference model, RTS/CTS model et al.)
This work was supported in part by NSF of USA under grant CNS-0831831.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 68–74, 2010. c Springer-Verlag Berlin Heidelberg 2010
Maximum Weighted Independent Set of Links under Physical Interference Model
69
cannot be directly applied here. The MWISL problem has several variations: such as different power assignments and different weight distributions. Even for the special case where every link has unit weight, MWISL is proved to be NP-hard [6, 7]. Our main contribution is the algorithm design for MWISL problem under the oblivious power assignment setting where each link l (or its corresponding sender) is assigned a transmission power c · lβ , here c is a constant and 0 < β ≤ κ is a constant. We can prove that our solution satisfies the interference constraints and achieves constant approximation ratio of the optimum when β = κ. Our main idea is like this: by using partition and shifting strategies, we find multiple sets of well-separated links and then select the one with the largest weight. The rest of the paper is organized as follows. Section 2 formulates our problems. Section 3 presents our algorithm design for the MWISL problem. Section 4 outlines the related work. Finally, Section 5 concludes the paper.
2 Network Model All the networking nodes V lie in plane and have a maximum transmission power P . The Euclidean distance between any pair of nodes is denoted by uv. Let r be the distance between a closest pair of nodes in V . The path-loss over a distance l is ηl−κ , where κ is path-loss exponent (a constant greater than 2 and 5 depending on the wireless environment), and η is the reference loss factor. Since the path-loss factor over the distance r is less than one, we have η < rκ . In an oblivious power assignment, a β node u transmits to another node v always at the power c uv for some constants c > 0 and 0 < β ≤ κ. This assumption implicitly imposes an upper bound on the distance between a pair of nodes which directly communicate with each other: For u to be able to directly communicate with v, we must have c uvβ ≤ P and hence 1/β uv ≤ (P/c) . Let ξ be the noise power, and σ be the signal to interference and noise ratio (SINR) threshold for successful reception. Then, in the absence of interference, the transmission by a node u can be successfully received by another node v if β −κ cη ≥ σ which is equivalent to uvκ−β ≤ σξ . Note that when and only if cuv ·ηuv ξ κ−β
cη uv = σξ , link uv can only transmit alone since any other link will conflict with uv. Thus we can disregard these links in A and assume that κ−β
uv
<
cη σξ
Therefore, the set A of communication links consists of all pairs (u, v) of distinct nodes cη satisfying that uvβ ≤ P/c and uvκ−β < σξ . Let R be the maximum length of the links in A. Then, Rκ = Rβ · Rκ−β < Hence, R < r
Pη P κ P cη · = < r . c σξ σξ σξ
P σξ
1/κ .
70
X. Xu, S. Tang, and P.-J. Wan
A set I of links in A is said to be independent if and only if all links in I can transmit successfully at the same time under the oblivious power assignment, i.e., the SINR of each link in I is above σ. We denote by I the collection of independent sets of links in A. Given a link weight function d ∈ RA + , the problem Maximum Weighted Independent Set of Links (MWISL) seeks a set I ∈ I with maximum total weight d (I) = a∈I d (a).
3 Algorithm Design In this section, we present our algorithm design for MWISL in the oblivious power assignment setting under physical interference model.
K
Fig. 1. Grid partition of the plane
√ We employ a grid partition of the plane (Fig. 1). Let = R/ 2. The vertical lines x = i · for i ∈ Z and horizontal lines y = j · for j ∈ Z partition the planes into half-open and half-closed grides of side (here Z represents the integer set): {[i, (i + 1) ) × [j, (j + 1) ) : i, j ∈ Z} . For all i, j ∈ Z, we denote Aij to be the set of links in A whose senders lie in the grid [i, (i + 1) ) × [j, (j + 1) ). We first give a sufficient condition for a set I of links to be independent. Let −1/κ √ √ −1 −1 K = 2 (4τ ) σ −1 − ξ(cη) Rκ−β + 2 Generally, K’s value depends on R, we can see that when β = κ, −1/κ √ √ K = 2 (4τ )−1 σ −1 − ξ(cη)−1 + 2 which is a constant independent of R. Lemma 1. Consider any two nonnegative integers k1 and k2 which are at most K. Suppose I is a set of links satisfying that for each i, j ∈ Z, |I ∩ Aij | ≤ 1 if i mod (K + 1) = k1 and j mod (K + 1) = k2 and |I ∩ Aij | = 0 otherwise. Then, I is independent.
Maximum Weighted Independent Set of Links under Physical Interference Model
71
Proof. Consider any link a = (u, v). The wanted signal strength is β
−κ
c a · η a
β−κ
= cη a
≥ cηRβ−κ .
Consider any link a = (u , v ) in I other than a. We have u u ≥ K. Therefore, √ u v ≥ u u − uv ≥ K − R = K/ 2 − 1 R. The total interference to a from all other links in I is at most √ −κ cRβ · η x2 + y 2 · K/ 2 − 1 R (x,y)∈Z2 \{(0,0)}
−κ √ = cηRβ−κ K/ 2 − 1
−κ x2 + y 2
(x,y)∈Z2 \{(0,0)}
≤ 4cηR ≤ 4cηR
β−κ
β−κ
−κ √ K/ 2 − 1 −κ √ K/ 2 − 1
√ −κ = 4τ cηRβ−κ K/ 2 − 1 , where
∞
i
−κ
+
∞ ∞
x2 + y 2
x=1 y=1
i=1 κ
κ(1 + 2− 2 ) π2−κ/2 + κ−1 2(κ − 2)
−κ
κ
τ=
π2−κ/2 κ(1 + 2− 2 ) + . κ−1 2(κ − 2)
Thus the SINR at the receiver of the link is at least cηRβ−κ √ −κ ≥ σ ξ + 4τ cηRβ−κ K/ 2 − 1 since
−1/κ √ K/ 2 − 1 ≥ (4τ )−1 σ −1 − ξ(cη)−1 Rκ−β
Next, we give a necessary condition for a set I of links to be independent. Let
κ 2 P + 1 . ω= σ2 ξ Lemma 2. For any I ∈ I and any i, j ∈ Z, |I ∩ Aij | ≤ ω. Proof. Let Iij = I ∩ Aij . Assume a = (u, v) be the shortest link in Iij , consider any link a = (u , v ) in Iij other than a, the distance between the sender u and v satisfies √ u v ≤ u u + uv ≤ 2 + uv ≤ 2R,
72
X. Xu, S. Tang, and P.-J. Wan
The SINR at a from all other links in Iij is at most β
c a · η a
a ∈Iij \{a}
Since
β
−κ
c a · η u v
r −κ (|Iij |−1)(2R)−κ
−κ
≤
−κ
a
a ∈Iij \{a}
≥ σ, we have |Iij | ≤
2κ Rκ σ rκ
u v−κ
+1<
≤
2κ P σ σξ
r−κ (|Iij | − 1) (2R)−κ
+1=
2κ P σ2 ξ
+ 1.
Input: A set of links L = {l1 , l2 , · · · , ln } dmax ← 0 ; for k1 = 0, · · · , K and k2 = 0, · · · , K do for i, j ∈ Z and the grid gi,j contains links from L do if i ≡ k1 mod (K + 1) and j ≡ k2 mod (K + 1) then select one link with the maximal weight whose sender lies within gi,j All the selected links form a set Ik1 k2 ; if d(Ik1 k2 ) > dmax then S ← Ik1 k2 ; dmax ← d(Ik1 k2 ); return A schedule S containing a subset of links in L.
Algorithm 1. Scheduling for MWISL Our partition-based scheduling method for input L is shown in Algorithm 1. The correctness of the algorithm follows from Lemma 1. Next, we derive its approximation bound. Theorem 1. The approximation ratio of our algorithm for MWISL is at most (K + 1)2 ω. Proof. Let I ∗ be a maximum-weighted independent set of links. For any pair of nonnegative integers k1 and k2 , let Ik∗1 k2 denote the set of links in I ∗ which lie in the grids [i, (i + 1) ) × [j, (j + 1) ) for all i, j ∈ Z satisfying that i mod (K + 1) = k1 and j mod (K + 1) = k2 . By Lemma 2, the set Ik∗1 k2 contains at most ω links from each grid [i, (i + 1) ) × [j, (j + 1) ) with i mod (K + 1) = k1 and j mod (K + 1) = k2 . Hence, d Ik∗1 k2 ≤ ωd (Ik1 k2 ) ≤ ω max d (Ik1 k2 ) . 0≤k1 ,k2 ≤K
Therefore, d (I ∗ ) =
0≤k1 ,k2 ≤K d
So, the theorem holds.
∗ Ik1 k2 ≤ (K + 1)2 ω
max
0≤k1 ,k2 ≤K
d (Ik1 k2 ) .
Maximum Weighted Independent Set of Links under Physical Interference Model
73
4 Literature Review For general graph-based interference model, the maximum throughput link scheduling problem is NP-complete [5]. Both probabilistic scheduling protocols [5, 10, 11] and distributed link scheduling protocols [13, 14] are proposed to maximize the throughput. For physical interference model, the problem of joint scheduling and power control has been well studied in [3, 4]. In [12], a power-assignment algorithm which schedules a strongly connected set of links in poly-logarithmic time is presented. [6] shows that the scheduling problem without power control under physical interference model, where nodes are arbitrarily distributed is NP-complete. A greedy scheduling algorithm with approximation ratio of O(n1−2/(Ψ (α)+ ) (log n)2 ), where Ψ (α) is a constant that depends on the path-loss exponent α, is proposed in [1]. Notice that this result can only hold when the nodes are distributed uniformly at random in a square of unit area. In [6], an algorithm with a factor O(g(L)) approximation guarantee in arbitrary topologies, where g(L) = log ϑ(L) is the diversity of the network, is proposed. In [2], an algorithm with approximation guarantee of O(log Δ) was proposed, where Δ is the ratio between the maximum and the minimum distances between nodes. Obviously, it can be arbitrarily larger than ϑ(L). Recently, Goussevskaia et al. [7] proposed a method for MWISL in the unweighted case which was claimed to have constant approximation bound. Unfortunately, as observed in Xu and Tang [16], their method [7] works correctly in absence of the background noise. Wan et al. [15] resolved this issue by developing the first correct constantapproximation algorithm. Most Recently, Halldorsson et al. [9] presented a robustness result, showing that constant parameter and model changes will modify the min-length link scheduling result only by a constant. They [8] also studied the scheduling problem under power control.
5 Conclusions We studied MWISL problem under the physical interference model with oblivious power assignment. Some interesting questions are left for future research. The first is to extend our algorithm to deal with a more general path loss model. The second is to develop constant approximation algorithms for MWISL under uniform power and adjustable power assignment settings.
References 1. Brar, G., Blough, D., Santi, P.: Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In: ACM MobiCom (2006) 2. Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., Srinivasan, A.: Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints. In: IEEE INFOCOM, pp. 1166–1174 (2008) 3. Cruz, R., Santhanam, A.: Optimal routing, link scheduling and power control in multihop wireless networks. In: IEEE INFOCOM, vol. 1 (2003)
74
X. Xu, S. Tang, and P.-J. Wan
4. ElBatt, T., Ephremides, A.: Joint scheduling and power control for wireless ad hoc networks. IEEE Transactions on Wireless Communications 1, 74–85 (2004) 5. Sharma, G., Joo, C., Shroff, N.: Distributed scheduling schemes for throughput guarantees in wireless networks. In: Allerton 2006 (2006) 6. Goussevskaia, O., Oswald, Y., Wattenhofer, R.: Complexity in geometric SINR. In: Proceedings of ACM MobiHoc, pp. 100–109 (2007) 7. Goussevskaia, O., Wattenhofer, R., Halld´orsson, M.M., Welzl, E.: Capacity of Arbitrary Wireless Networks. In: IEEE INFOCOM 2009 (2009) 8. Halld´orsson, M.: Wireless scheduling with power control. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 361–372. Springer, Heidelberg (2009) 9. Halldorsson, M., Wattenhofer, R.: Wireless Communication is in APX. In: Automata, Languages and Programming, pp. 525–536 10. Joo, C., Shroff, N.: Performance of random access scheduling schemes in multi-hop wireless networks. In: IEEE INFOCOM (2007) 11. Lin, X., Rasool, S.: Constant-time distributed scheduling policies for ad hoc wireless networks. In: IEEE CDC (2006) 12. Moscibroda, T., Wattenhofer, R.: The Complexity of Connectivity in Wireless Networks. In: IEEE INFOCOM (2006) 13. Penttinen, A., Koutsopoulos, I., Tassiulas, L.: Low-complexity distributed fair scheduling for wireless multi-hop networks. In: WiOPT 2005: First Workshop on Resource Allocation in Wireless Networks, RAWNET (2005) 14. Sanghavi, S., Bui, L., Srikant, R.: Distributed link scheduling with constant overhead. In: ACM SIGMETRICS, pp. 313–324. ACM Press, New York (2007) 15. Wan, P., Jia, X., Yao, F.: Maximum Independent Set of Links under Physical Interference Model. In: Liu, B., Bestavros, A., Du, D.-Z., Wang, J. (eds.) WASA 2009. LNCS, vol. 5682, pp. 169–178. Springer, Heidelberg (2009) 16. Xu, X., Tang, S.: A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model. In: Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing, pp. 13–20. ACM, New York (2009)
A QoS-Guaranteed Energy-Efficient Packet Scheduling Algorithm for WiMax Mobile Devices Hung-Cheng Shih and Kuochen Wang Department of Computer Science, National Chiao Tung University {hcshih,kwang}@cs.nctu.edu.tw
Abstract. A mobile device may run energy consuming multimedia applications, such as video streaming. Thus, power management is an important issue in mobile devices. In this paper, we propose a QoS-guaranteed energy-efficient packet scheduling algorithm for IEEE 802.16-2009 (WiMax) network interfaces. The integration of packet scheduling and sleep mode operation can make IEEE 802.16-2009-enabled mobile devices more energy efficient. Simulation results show that the proposed packet scheduling algorithm has 14.37% less energy consumption than the naïve algorithm, and it does not sacrifice average packet delay. The contributions of our proposed algorithm are that our algorithm is suitable for wireless environments where connections come and go rapidly and the time complexity of our algorithm is low. Keywords: Energy-efficient, IEEE 802.16-2009, packet scheduling, sleep window, WiMax.
1 Introduction Power management is an important issue in mobile devices (called subscriber stations (SSs) in the IEEE 802.16-2009), which are powered by batteries. Because the capacity of a battery is limited, we have to reduce the energy consumption in every way, such as decreasing the working time of a mobile device. In a mobile device with the capability of wireless communications, the energy consumed by active transmissions is high because the transmitter and the receiver have to be turned on during the transmission. If the network interface is not active, the mobile device can turn off the transmitter and/or the receiver to save energy. In order to use the energy efficiently, the transmission time has to be shortened as much as possible, so that the transmitter and the receiver can be shutdown most of the time. The IEEE 802.16-2009 [3] is to provide a high speed, wireless last mile to benefit the rural area lack of wire-line infrastructure [1][2]. It can serve as a backbone of IEEE 802.11 networks so that the cost of deploying the wireless networks can be decreased [1][2]. Users can connect their notebooks or PDAs directly to the IEEE 802.16 network without using the IEEE 802.11 network to get higher transmission rates and better QoS [2]. The communication range of the IEEE 802.16-2009 standard is up to 31 miles and the transmission rate is up to 100 Mbps [2]. G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 75–79, 2010. © Springer-Verlag Berlin Heidelberg 2010
76
H.-C. Shih and K. Wang
To reduce the energy consumption of SSs, the sleep mode was introduced in the IEEE 802.16-2009 to achieve energy saving. The sleep mode is a state for an SS to be temporarily absent from the serving base station (BS) air interface [3]. Note that in the IEEE 802.16-2009, normal transmission periods, which are called normal mode, and sleeping periods, which are called sleep mode, are interleaved with each other.
2 Existing Approaches The characteristics of wireless networks are high error rate, high channel variation, and high transmission delay, and we must consider these characteristics when we design a packet scheduling algorithm [4]. In [5], the authors proposed a Deficit Fair Priority Queue (DFPQ) algorithm, which uses two-tier architecture. The first tier ensures that low priority data streams will have the opportunity to transmit packets. The second tier uses a multiple queue mechanism and applies a different packet scheduling algorithm according to each queue’s characteristic. The drawback of this algorithm is that the transmission of low priority data streams may interrupt the transmission of high priority data streams. In [6], the authors proposed an algorithm called Preemptive DFPQ to fix the problem mentioned above. However, these two algorithms did not consider the wireless network channel condition. In [7], the authors proposed an algorithm that considers network traffic patterns and SS mobility to maximize energy efficiency. The authors suggested several calculation methods of the length of a sleep window to avoid the problem of serious transmission delay caused by a long sleep window. The disadvantage of this algorithm is that the total sleep time will be shortened. In [8], the authors proposed another way to adjust the parameters of sleep mode for the traffic patterns of constant bit rate (CBR) and FTP. However, they set the round trip time (RTT) to a constant in their experiment, which is not realistic in real network environments. In [9], the authors proposed an algorithm to determine the lengths of sleep window and listening window based on the QoS constraints of real-time communications. Packets are scheduled by the EDF algorithm. The disadvantages of this algorithm are that it uses linear integer programming to find an optimum solution, which results in high time and space complexities. In [10], the authors proposed a packet scheduling algorithm not only considering the delay constraint, but also the delay jitter constraint. Packets are also scheduled by the EDF algorithm. The disadvantage of this algorithm is that it is applied to PSC type 3, which will be deactivated when the sleep period is expired. As a result, the calculation of PSC parameters and the negotiation of PSC creation must be performed repeatedly, which are not energy-efficient.
3 Design Approach In the IEEE 802.16-2009, we must combine packet scheduling and power saving modes altogether to achieve low power consumption, while maintaining the QoS requirement. Therefore, we propose a QoS-guaranteed and energy-aware packet scheduling algorithm. The proposed algorithm is divided into two steps: power saving class generation and packet scheduling, which involve simple computations so as to have low time complexity.
A QoS-Guaranteed Energy-Efficient Packet Scheduling Algorithm
77
3.1 Power Saving Class Generation Because the connections in PSC type 2 have strict QoS constraints, we describe the proposed power saving class generation of PSC type 2 first. In PSC type 2, we define the length of listen windows tl as follows: C
tl = ∑ i =1
pi R j × TF
(1)
where pi is the average packet length of connection i, Rj is the raw data rate under burst profile j, TF is the frame duration and C is the number of connections. The length of sleep window ts is the minimum delay constraint in all connections. In PSC type 1, the suitable data delivery services are NRT-VR and BE services. In our design, the connections which belong to PSC type 1 can use the remaining bandwidth of the PSC type 2 listen window after PSC type 2 connections have been served. PSC type 3 was designed for connections that carry management operations as well as multicast connections. According to the specification of PSC type 3, when the periodic ranging is active, the maximum sleep window length tmax must be set to the value indicated by the Next Periodic Ranging TLV, which is carried in the RNG-RSP or MOB_SLP-RSP messages [3]. The start frame number of sleep window nsf must be set to the frame number next to the transmission of RNG-RSP or MOB_SLP-RSP messages. 3.2 Packet Scheduling Because the connections using UGS scheduling services have strict QoS requirements, the UGS connections have the highest priority. The connections of the ertPS and rtPS scheduling services have the second and third priority, respectively. We use the EDF algorithm in UGS, ertPS, and rtPS scheduling services. Packets that miss their transmission deadline will be discarded. The nrtPS and BE scheduling services are not delay sensitive. Therefore, the packet scheduling algorithm for nrtPS connections is WFQ, and the packet scheduling algorithm for BE connections is RR.
4 Experimental Results We evaluate the proposed algorithm using the ns-2 simulator and NIST WiMAX modules for ns-2. Table 1 shows the experiment parameters we used, which are defined in the IEEE 802.16-2009 [3]. We compared average packet delay under various numbers of connections. In UGS and ertPS connections, we used G.711, G.723.1, G.726, and G.729a as the network flow model. In rtPS, we used H.264/MPEG-4 AVC as the network flow model. As to the nrtPS and BE connections, we used the Poison process as the network flow model. Fig. 1 shows that the average packet delay of our algorithm is almost identical (0.000677% higher) to that of the naïve algorithm. Fig. 2 illustrates the relationship between energy consumption and number of connections. When the number of connections increases, the total number of packets transmitted increases; thus it causes the increase of energy consumption. Simulation results show that the energy consumption of our algorithm is 14.37% less than that of the naïve algorithm.
78
H.-C. Shih and K. Wang Table 1. Experiment parameters Symbol
Description
BW
Nominal channel bandwidth
Value 10MHz
NFFT
Number of subcarriers
256
Nd
Data subcarriers
192
G
Guard fraction
1/4
TF
Frame duration
5 ms
Average packet delay (msec)
5.69650 5.69640
5.69633494 5.696296025
5.69630 5.69620 5.69610 5.69600 Naïve
Proposed Algorithm
Fig. 1. Average packet delay under different numbers of connections Naïve
Proposed Algorithm
Energy Consumption (joule)
5 4.5 4 3.5 3 2.5 2 1
2
3
4
5
6
7
8
9
10
Number of Connections
Fig. 2. Energy consumption under various numbers of connections
5 Conclusion As mobile computing is getting more popular, the demand of efficient power source usage will become even greater. In this paper, we have presented a QoS-guaranteed, energy-efficient packet scheduling algorithm. Simulation results show that our proposed algorithm has 14.37% less energy consumption than the naïve algorithm. In addition, our algorithm does not sacrifice the average packet delay. Currently, we are working on comparing with some representative related work. The contributions of our proposed algorithm are that our algorithm is suitable for wireless environments where connections come and go rapidly and the time complexity of our algorithm is low.
A QoS-Guaranteed Energy-Efficient Packet Scheduling Algorithm
79
Acknowledgments This work was supported in part by the National Science Council, Taiwan, under Grants NSC96-2628-E-009-140-MY3 and NSC98-22218-E-009-008.
References 1. Vaughan-Nichols, S.J.: Achieving wireless broadband with WiMax. IEEE Computer 37(6), 10–13 (2004) 2. Abichar, Z., Peng, Y., Chang, J.M.: WiMax: the emergence of wireless broadband. IEEE IT Prof. 8(4), 44–48 (2006) 3. IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std 802.16-2009 (2009) 4. Tsai, T.Y., Tsai, Z.: Design of a Packet Scheduling Scheme for Downlink Channel in IEEE 802.16 BWA Systems. In: IEEE Wireless Communications and Networking Conference, pp. 1453–1458 (2008) 5. Chen, J., Jiao, W., Wang, H.: A service flow management strategy for IEEE 802.16 broadband wireless access systems in TDD mode. In: IEEE International Conference on Communications, vol. 5, pp. 3422–3426 (2005) 6. Safa, H., Artail, H., Karam, M., Soudah, R., Khayat, S.: New scheduling architecture for IEEE 802.16 wireless metropolitan area networks. In: IEEE/ACS International Conference on Computer Systems and Applications, pp. 201–210 (2007) 7. Lee, N.H., Bahk, S.: MAC sleep mode control considering downlink traffic pattern and mobility. In: IEEE 61st Vehicular Technology Conference, vol. 3, pp. 2076–2080 (2005) 8. Jang, J., Han, K., Choi, S.: Adaptive power saving strategies for IEEE 802.16e mobile broadband wireless access. In: Asia-Pacific Conference on Communications, pp. 1–5 (2006) 9. Tsao, S.L., Chen, Y.L.: Energy-efficient packet scheduling algorithms for real-time communications in a mobile WiMAX system. Computer Communications 31(10), 2350–2359 (2008) 10. Liao, W.H., Yen, W.M.: Power-saving scheduling with a QoS guarantee in a mobile WiMAX system. Journal of Network and Computer Applications 32(6), 1144–1152 (2009)
Minimum Energy Cost k -barrier Coverage in Wireless Sensor Networks Huiqiang Yang, Deying Li , Qinghua Zhu, Wenping Chen, and Yi Hong Key Laboratory of Data Engineering and Knowledge Engineering, MOE School of Information, Renmin University of China, P.R. China
[email protected]
Abstract. Barrier coverage problem is one of important issues in wireless sensor networks. In this paper we study the minimum energy cost k-barrier coverage problem in wireless sensor network in which each sensor has l + 1 sensing power levels. First, we transform the minimum energy cost k-barrier coverage problem into a minimum cost flow problem with side constraints. Then we use Lagrangian relaxation technique to solve this minimum cost flow problem. Moreover, we propose two efficient heuristics for the minimum energy cost k-barrier coverage problem. Simulations evaluate that our algorithms are efficient. Keywords: k-barrier coverage, sensing power level, minimum energy cost, sensor networks.
1
Introduction
Wireless sensor networks [1] provide an efficient way to guard the boundaries of critical infrastructures or assets. By deploying a number of wireless sensors along the boundaries, intruders could be detected once they enter into the areas covered by the sensors, where the union of the covered areas of sensors forms a barrier. Fig.1 shows a typical example of barrier coverage. Every path crossing the belt barrier region will be detected by at least one sensor. Compared with full coverage which requires every point in the deployment region to be covered, barrier coverage requires much fewer sensors. If the width of the deployment region is three times the sensing range, full coverage requires more than twice the density of barrier coverage. Saving in sensors grows linearly with width [2]. In recent years, with the requirement of protecting sensitive military facilities and national borders increasing, barrier coverage attracted more and more interest of researchers. In some literatures about barrier coverage, barriers are constructed as rectangular regions, which have been pre-selected as moats around the protected area. The barrier can also be annulus [2]. In practice, a certain degree of redundancy is required in barrier coverage because some sensors may fail due to draining of energy, malfunction or malicious damage and so on. k barrier coverage which every path crossing barrier region can be detected by at
Corresponding author.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 80–89, 2010. c Springer-Verlag Berlin Heidelberg 2010
Minimum Energy Cost k-barrier Coverage in Wireless Sensor Networks
81
Fig. 1. An example of barrier coverage
least k sensors is proposed to address this situation. The authors [2] proposed efficient algorithms to quickly determine whether a region is k -barrier covered. In [8], the authors proposed LBCP algorithm to achieve local barrier coverage by limiting the cross path. A distributed algorithm in [9] is proposed to construct strong sensor barriers without any constraint on crossing paths. In all the above works, the sensing ranges of sensors are not adjustable. Since sensors are battery powered and it is difficult to replace the batteries, sensors may be designed to adjust sensing range adaptively to save energy consumption. In this paper, we study the problem of minimizing the energy consumption in k -barrier coverage. Each sensor has several sensing power levels and each sensing power level corresponds to a sensing range. We need to assign a sensing power level to each sensor and the result sensor network can form a k -barrier coverage. Our goal is finding such an assignment that the total sensing power is minimized. To solve the problem, we first transform our problem into minimum cost network flow problem with side constraints. Second, we use the Lagrangian relaxation technique [3] to get a lower bound of the problem. Then, we design two heuristic algorithms with different ways of constructing auxiliary graph to solve our problem. The rest of this paper is organized as follows. We discuss the related work in Section 2. Then, we give the network models and the problem statements in Section 3. In section 4, we first transform the problem to the minimum cost flow problem with side constraints, then use the Lagrangian Relaxation method to get a lower bound for our problem. In Section 5, we propose two efficient heuristic algorithms to solve our problem. Section 6 presents the performance evaluation results. Finally, Section 7 concludes the paper.
2
Related Work
The traditional coverage problems, including point coverage [4] which requires every target point to be covered by at least one or k sensors, and area coverage [5] which requires every point in the area to be covered by at least one or k sensors, have been studied intensively. The concept of barrier coverage was first introduced in the context of control schemes for multi-robot systems [6]. Kumar et al. [2] proposed efficient algorithms to quickly determine whether a region is k -barrier covered. Morever, they established an optimal deployment pattern to achieve k -barrier coverage when sensors were deployed deterministically. Different
82
H. Yang et al.
from omni-sensing model in [2], Kuo-Feng Ssu et al. [7] studied the k -barrier coverage problem in directional sensing model and developed a distributed algorithm to construct k -barrier coverage in randomly deployed directional sensor fields. Due to the observation that movements were likely to follow a shorter path when crossing a belt region, [8] introduced the concept of local barrier coverage which guaranteed to detect all movements whose trajectory were confined to a slice of the belt region of deployment and proposed LBCP algorithm to achieve local barrier coverage. Although local barrier coverage does not always guarantee global barrier coverage, the authors showed that for thin belt regions, local barrier coverage almost always provides global barrier coverage. In [9], a distributed algorithm were proposed to construct strong sensor barriers on long boundary areas of irregular shape without any constraint on crossing paths. The above works were based on the assumption that sensors were uniformly deployed in a large area at random. Saipulla, et al. [10] studied the barrier coverage when sensors were deployed along a line and established a tight lower-bound for the existence of barrier coverage in line-based deployments. All these works assumed that the sensing power of sensor were fixed. In this paper, based on multiple sensing power levels model, we study the problem of minimizing the total energy cost of k -barrier coverage in a sensor network.
3
Network Model and Problem Description
We assume that a set S of sensors are deployed randomly in a two-dimensional rectangular area where sensors do not move after they are deployed. We assume that each sensor knows the coordinates (x, y) of its own location. This may be detected through GPS or be obtained through a localization mechanism. Suppose each sensor node has l + 1 sensing power levels, 0 ≤ p1 ≤ p2 · · · ≤ pl , i.e., each sensor has l + 1 different corresponding sensing ranges {0, r1 , r2 , · · · , rl }. Every active sensor is assigned with one sensing power level in {p1 , p2 , · · · , pl }. For a given power assignment of the sensors, i.e., each sensor si is assigned with a sensing power level P L(si ),PL(si ) ∈ {0, p1 , p2 , · · · , pl }, we define the total P L(si ). energy cost of the network as si ∈S
We give some definitions as follows: Definition 1. Crossing path (or Incursive path): A path is said to be a crossing (or incursive) path in a belt region if it crosses the complete width of the region from one side to the other side. An example is illustrated in Fig.1. The red sketch path is an incursive path while the two blue paths are not crossing paths. Definition 2. A crossing path P is said to be k-covered if P intersects with at least k active sensor’s sensing disks. Definition 3. k-barrier coverage: A belt region is said to be k-barrier covered by a sensor network deployed over it if and only if all the crossing paths through the belt region are k-covered by this sensor network.
Minimum Energy Cost k-barrier Coverage in Wireless Sensor Networks
83
Definition 4. Minimum energy k-barrier coverage problem: Given a sensor network over the objective belt region and each sensor has l + 1 sensing power levels, find a sensing power level assignment such that the given belt region is k-barrier covered and the total energy cost is minimized. The goal of the paper is to find a sensing power level assignment for each sensor, i.e., the set of sensing power {P L(s1 ), P L(s2 ), · · · , P L(sn )} such that the sensor network can form a k-barrier coverage and the total energy cost is minimum among all the assignments.
4
Lagrangian Method for Minimum Energy Cost k-barrier Coverage Problem
Given a set of sensors S = {s1 , s2 , · · · , sn }, each sensor node si has l + 1 sensing power levels, 0 ≤ p1 ≤ p2 ≤ · · · ≤ pl . We consider the minimum energy cost k-barrier coverage problem in a long narrow region referred to as a belt, where sensors are deployed randomly over it. Before solving the minimum energy cost k-barrier coverage problem, we first restate the method for determine whether a belt region is k-barrier covered [2]. Corresponding to a sensor network deployed in a belt region, we derive a coverage graph CG = (V, E), where V is the set of all sensor nodes plus two virtual vertexes s and t (see Figure 2). The set of edges E is derived as follows: each pair of sensors whose sensing disks overlap is connected by an edge. Additionally, the sensors whose sensing disks intersect with the left boundary are connected to node s and the sensors whose sensing disks intersect with the right boundary are connected to node t. An example of constructed coverage graph is shown in Figure 2.
Fig. 2. A simple example of coverage graph
Lemma 1. [2] An open belt region is k-barrier covered if and only if s and t are k-connected in the corresponding coverage graph, CG. In order to solve the minimum energy cost k-barrier coverage problem, we construct an auxiliary weighted directed graph Ga = (Va , Ea , Ca , Ua ) as follows. In Ga , Va denotes the set of nodes, Ea denotes the set of edges, Ca denotes the set of edges’ cost and Ua denotes the set of edges’ capacity.
84
H. Yang et al.
t h t h t h First, we construct l node pairs {qi,1 , qi,1 }, {qi,2 , qi,2 }, · · · , {qi,l , qi,l } for each t h t sensor si in S. For each node pair {qi,k , qi,k }, we add a directional edge from qi,k h h t h to qi,k with cost pk . We add a directed edge (qi,k , qj,m ) with cost 0 from qi,k to t qj,m if and only if si ’s sensing range intersects with sj ’s sensing range while sensor si working at sensing power level pk and sensor sj working at sensing power level pm . In addition, we add a new virtual node s at the left side of the belt region and a new virtual node t at right side of the belt region. Then, there is a directed edge t with cost 0 if and only if si ’s sensing range intersects with the left from s to qi,k border of the belt region when si working at sensing power level pk . Last, there is h to t with cost 0 if and only if si ’s sensing range intersects a directed edge from qi,k with the right border of the belt region when si working at sensing power level pk . Each edge in Ea is associated with capacity 1. To formulate our problem rigorously, we use a binary variable xi,j to represent if there is an edge from i to j in Ga = (Va , Ea , Ca , Ua ). For the simplicity of the mathematical representation of the problem, we use e(si ) to denote the set of t h t h t h , qi,1 ), (qi,2 , qi,2 ), · · · , (qi,l , qi,l )} for each sensor si in S. Let X denote edges {(qi,1 the row vector of variables corresponding to each edge (i.e., X = {xi,j |(i, j) ∈ Ea }). Let C denote the row vector of the cost of edges in the same order with X (i.e., C = {ci,j |(i, j) ∈ Ea }). Let X be the transpose of vector X. Our problem can be formulated by an integer programming problem as follows:
min C · X subject to
(i,v)∈Ea
xi,v −
(1)
xu,i = 0, for each node i ∈ Va − {s, t}
(2)
xs,v = k
(3)
xu,t = k
(4)
xu,v = 1, for each edge set e(si )
(5)
xi,j = 0, 1
(6)
(u,i)∈Ea
(s,v)∈Ea
(u,t)∈Ea
(u,v)∈e(si )
From the formulation, it is easy to know that if there are not constraints (5), the problem is a classical minimum cost flow problem. Adding constraints (5), the problem becomes the minimum cost network flow problem with side constraints (5). From Lemma 1 and the structure of the auxiliary graph, we have the following result. Lemma 2. The minimum energy cost k-barrier coverage problem is equivalently transformed to the minimum cost k-flow problem with side constraints. We can use the Lagrangian relaxation algorithm in [3] to obtain a lower bound of our problem. Lagrangian relaxation has been used in various approaches to the solution of constrained capacitated network flow problems [11,12].
Minimum Energy Cost k-barrier Coverage in Wireless Sensor Networks
5
85
Two Heuristic Algorithms for Minimum Energy Cost k-barrier Coverage Problem
In this section, we propose two efficient heuristic algorithms (referred as Heuristic-1 and Heuristic-2) for the minimum energy cost k-barrier coverage problem. Every sensor si has its coordinates si (x, y) relative to the bottom-left corner of the belt region which is the original point. We use si .x to represent x-coordinate x of si . The main idea of two heuristic algorithms is that:(1) we construct an auxiliary graph according to CG; (2) use the minimum cost flow algorithm on the auxiliary graph to find k node-disjoint paths from s to t; (3) according to the construction of graph, we can adjust the sensing power levels of sensors in each path to make 1-barrier coverage. Thus we get k barrier coverage in our original sensor network. In order to make sure that a sensor node si is used only once in all paths , we split each sensor node in CG into two nodes qit and qih . This transformation replaces each original undirected edge (si , sj ) in CG by a directed edge (qih , qjt ). The main difference between Heuristic-1 and Heuristic-2 is the way of assigning cost for each edge. In Heuristic-1, we use the distance between si and sj as the cost of edges while in Heuristic-2 we use the maximum sensing power levels as the cost of edges. 5.1
Heuristic-1
In Heuristic-1, an auxiliary weighted directed graph Gb = (Vb , Eb , Cb , Ub ) where Vb denotes the set of nodes, Eb denotes the set of edges, Cb denotes the set of edges’ cost and Ub denotes the set of edges’ capacity, is constructed as follows: we construct one node pair {qit , qih } for each sensor si originally in S. For each node pair {qit , qih }, we add a directed edge from qit to qih with cost 0. We add a directed edge (qih , qjt ) with cost of dist(si , sj ) from qih to qjt if and only if the Euclidian distance between si and sj (i.e., dist(si , sj )) is less than 2 ∗ rl , where rl is the largest sensing range. In addition, we also add a new virtual node s at the left side of the belt region and a new virtual vertex t at right side of the belt region. Then, there is a directed edge from s to qit if and only if si ’s sensing range intersects with the left border of the belt region when works at its maximum sensing power level pl . The cost of this edge is si .x. There is a directed edge from qih to t if and only if si ’s sensing range intersects with the right border of the belt region when works at its maximum sensing power level pl . The cost of this edge is LEN − si .x, where LEN is the length of the belt region. Each edge in Eb is associated with capacity 1. Then we use the minimum cost flow algorithm on Gb to find k node-disjoint paths from s to t. And adjust the sensing power level of each sensor node in each path to make this path form 1-barrier coverage. According to Lemma 1, we know that the found paths form a k-barrier coverage in the sensor network. Note that we use R(pi ) to denote the sensing range corresponding to the sensing power level pi .
86
H. Yang et al.
Algorithm Heuristic-1 is formally represented as following: Algorithm 1. Heuristic-1 1: Construct an auxiliary graph Gb = (Vb , Eb , Cb , Ub ) as we have just illustrated above. 2: Using minimum cost flow algorithm in [3] to find k-minimum cost flow from s to t. 3: For each path found Pi = {s, qit1 , qih1 , · · · , qitm , qihm , t}, assign a power level for each sensor node as follows: P L(si1 ) = min{pk |rk ≥ max(si1 .x, dist(si1 , si2 ) − rl )} P L(sij ) = min{pk |rk ≥ max(dist(sij−1 , sij ) − R(P Lsij−1 ), dist(sij , sij+1 ) − rl )}, for 2 ≤ j ≤ m − 1 P L(sim ) = min{pk |rk ≥ max(dist(sim−1 , sim ) − R(P Lsim−1 ), LEN − sim .x)}
5.2
Heuristic-2
Now we will introduce another Heuristic algorithm for our problem. As in Heuristic-1, we first construct an auxiliary graph Gc = (Vc , Ec , Cc , Uc ), where Vc denotes the set of nodes, Ec denotes the set of edges, Cc denotes the set of edges’ cost and Uc denotes the set of edges’ capacity. We construct one node pair {qit , qih } for each sensor si originally in S. For each node pair {qit , qih }, we add a directed edge (qit , qih ) from qit to qih with cost pl . We add a directed edge ( qih , qjt ) with cost 0 from qih to qjt if and only if the Euclidian distance between si and sj (i.e., dist(si , sj )) is less than 2 ∗ rl , where rl is the largest sensing range. We also add a new node s at the left side of the belt region and a new node t at right side of the belt region. There is a directed edge from s to node qit with cost 0 if and only if the sensor si ’s sensing range intersects with the left border of the belt region when si working at the maximum sensing power level pl . And there is a directed edge from qih to t with cost 0 if and only if si ’s sensing range intersects with the right border of the belt region when si working at the maximum sensing power level pl . Each edge in Ec is associated with capacity 1. Then we use the minimum cost flow algorithm on Gc to find k node-disjoint paths from s to t. And adjust the sensing power level of each sensor node in each path to make this path feasible. Heuristic-2 is formally represented as follows: Algorithm 2. Heuristic-2 1: Construct an auxiliary graph Gc = (Vc , Ec , Cc , Uc ) as we have just illustrated. 2: Using minimum cost flow algorithm in [3] to find k-minimum cost flow from s to t. 3: For each found path Pi = {s, qit1 , qih1 , · · · , qitm , qihm , t}, assign a power level for each sensor node as follows: P L(si1 ) = min{pk |rk ≥ max(si1 .x, dist(si1 , si2 ) − rl )} P L(sij ) = min{pk |rk ≥ max(dist(sij−1 , sij ) − R(P Lsij−1 ), dist(sij , sij+1 ) − rl )}, for 2 ≤ j ≤ m − 1 P L(sim ) = min{pk |rk ≥ max(dist(sim−1 , sim ) − R(P Lsim−1 ), LEN − sim .x)}
Minimum Energy Cost k-barrier Coverage in Wireless Sensor Networks
87
Both in Heuristic-1 and Heuristic-2, the step 1 takes time complexity O(n). In step 2, using the minimum cost flow algorithm takes time O(n3.5 ). Step 3 takes time O(n · k). Because k is always less than n, step 3 takes time at most O(n2 ). Thus, the whole algorithm takes time O(n3.5 ).
6
Performance Evaluation
We develop a custom simulator and use it to evaluate the performance of our proposed algorithms. In the simulation, we randomly deploy sensors in a rectangular barrier with 100 units long and 5 units wide. Each sensor has 4 different sensing power levels {0, 16.0, 36.0, 64.0}. Without loss of generality, the sensing ranges are the square root of the power levels in the simulation, i.e., each sensor has 4 different sensing ranges {0, 4.0, 6.0, 8.0}. In Lagrangian Relaxation algorithm, we set the = 0.0001. Due to time cost for converging to a feasible solution is very high, we terminate the algorithm after 100 iterations and get a lower bound of an instance. In experiment, we will consider the effect of factors such as belt length, sensor density and number of required barrier coverage. The performance of the barrier construction schemes was evaluated by the total energy cost of the formed k-barrier coverage. 6.1
Total Energy Cost vs. Number of Sensors
5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0
Heuristic-1 Heuristic-2 Lagrangian
100
120
Total Energy Cost
Total Energy Cost
To study the effect of number of sensors on total energy cost, we set up the networks with the number of sensors increasing from 100 to 220 with an increment of 20. The length of belt region is set to 100. Fig.3 presents the performance of the algorithms with respect to the number of sensors. We can see that Heuristic2 has better performance than Heuristic-1. The total energy cost consumed by Heuristic-1 has at most two times of the lower bound of the optimal solution. This showed our heuristic algorithms are efficient.
140
160
180
Number of sensors
(a) k = 5
200
220
8000 7000 6000 5000 4000 3000 2000 1000 0
Heuristic-1 Heuristic-2 Lagrangian
100
120
140
160
180
Number of sensors
(b) k = 8
Fig. 3. Total energy cost vs. Number of sensors
200
220
H. Yang et al.
5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0
Heuristic-1 Heuristic-2 Lagrangian
100
120
Total Energy Cost
Total Energy Cost
88
140
160
180
200
8000 7000 6000 5000 4000 3000 2000 1000 0
Heuristic-1 Heuristic-2 Lagrangian
100
120
140
160
Length of Belt Region
Length of Belt Region
(a) k = 5
(b) k = 8
180
200
Fig. 4. Total energy cost vs. Length of Belt region
6.2
Total Energy Cost vs. Lenght of Belt Region
To study the effect of the length of belt region, we vary the length of belt region from 100 to 200 with an increment of 20. The number of sensors is set to 250. As shown in the Fig.4, the total energy cost increases when the length increases. This is because every path has to cover longer length. As shown in Fig.4, Heuristic-2 has better performance than Heuristic-1. The total energy cost consumed by Heuristic-1 has at most two times of the lower bound of the optimal solution. Above simulation results show that our proposed heuristic are efficient.
7
Conlusions
In this paper, we study the minimum energy cost of k-barrier coverage problem and formulate the problem into a minimum cost flow problem with side constraints. We use the classical Lagrangian algorithm to find a lower bound of the total energy cost. Then we propose two heuristic algorithms for this problem. At last, we implement all three algorithms and compare their performances. The two heuristic algorithms consume the total energy cost at most two times of the lower bound of the optimal solution. These experiments show the proposed algorithms’ efficient.
Acknowledgment This paper was supported in part by Renmin University of China under Grants 10XNJ032 and 10XNG037 and 863 high-tech project under Grant 2008AA01Z120.
References 1. Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: A survey on sensor networks. IEEE Communications Magazine, 102–114 (2002) 2. Kumar, S., Lai, T.H., Arora, A.: Barrier Coverage with Wireless Sensors. In: Proc. ACM MobiCom (2005)
Minimum Energy Cost k-barrier Coverage in Wireless Sensor Networks
89
3. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993) 4. Cardei, M., Thai, M.T., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: IEEE INFOCOM, pp. 1976–1984 (2005) 5. Zhou, Z., Das, S., Gupta, H.: Connected K-coverage problem in sensor networks. In: ICCCN (2004) 6. Gage, D.: Command control for many-robot systems. In: The Nineteenth Annual AUVS Technical Symposium (1992) 7. Ssu, K.-F., Wang, W.-T., Wu, F.-K., Wu, T.-T.: K-barrier coverage with a directional sensing model. International Journal on Smart Sensing and Intelligent Systems, 75–83 (2009) 8. Chen, A., Kumar, S., Lai, T.-H.: Designing localized algorithms for barrier coverage. IEEE Transactions on Mobile Computing, 491–504 (2010) 9. Liu, B., Dousse, O., Wang, J., Saipulla, A.: Strong Barrier Coverage of Wireless Sensor Networks. In: Proceeding of ACM Mobicom (2008) 10. Saipulla, A., Westphal, C., Liu, B., Wang, J.: Barrier Coverage of Line-Based Deployed Wireless Sensor Networks. In: IEEE INFOCOM, pp. 127–135 (2009) 11. Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Management Science, 1–18 (1981) 12. Held, M., Wolfe, P., Crowder, H.D.: Validation of subgradient optimization. Mathematical Programming, 62–88 (1974)
On the Performance of Distributed N-Cooperation Power Allocation via Differential Game in Cognitive Radio System Shunxi Gao1, Long Zhang2, Suqin Fan1, Wei Huang2, Qiwu Wu2, and Yu Deng3 1
Mechanical and Electrical Services Department, Handan Polytechnic College, Handan 056001, China 2 School of Information Engineering, University of Science and Technology Beijing, Beijing 100083, China 3 Communications Research Group, Department of Electronics, University of York, Heslington YO10 5DD, UK
[email protected]
Abstract. In this paper, we study the distributed cooperative power allocation problem in a single-cell cognitive radio system. We build up a dynamic power allocation model via differential game using two formulated cost functions. Moreover, we propose a distributed cooperative power allocation algorithm based on differential game (DCPADG) under the condition that the average power limits and QoS constraints of secondary users (SUs) are guaranteed. Numerical results demonstrate that the proposed DCPADG algorithm can effectively reduce the transmit power and improve the throughput of SUs. Keywords: Cognitive radio; cooperative power allocation; differential game.
1 Introduction Recently, with the increasing interest in cognitive radio (CR) [1], there has been significant attention in power allocation research for CR system. As a framework for modeling, game theory has gained more attention as an effective tool to analyze the distributed power allocation in CR system. In [2], L. Zhang, et al. proposed a distributed noncooperative power control algorithm based on differential game (DNPCDG), which achieves the distributed dynamic power control under the condition that the average power threshold and quality of service (QoS) of secondary users (SUs) are guaranteed. However, the DNPCDG algorithm applied the idea of noncooperative game to solve the problem of distributed power allocation. In this paper, we take into account the problem of cooperative power allocation in CR system. We build up a dynamic power allocation model via differential game using two formulated cost functions. Moreover, we present a distributed cooperative power allocation algorithm based on differential game (DCPADG) under the same condition with the DNPCDG algorithm. Numerical results demonstrate that the proposed DCPADG algorithm can effectively reduce the transmit power and improve the throughput of SUs by comparison with the DNPCDG algorithm. G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 90–94, 2010. © Springer-Verlag Berlin Heidelberg 2010
On the Performance of Distributed N-Cooperation Power Allocation via Differential Game
91
2 System Model Consider a cellular primary user (PU) radio system consisting of a finite number of cells and base stations. Assume that n SUs are randomly distributed in a single cell over the time interval [t0,T] and SUs are either fixed or slowly moving in that cell. The SUs constitute a spread spectrum CR system centered around the fixed CR base station over the total available authorized spectrum in an ad hoc mode to share the corresponding spectrum holes (SH). Let N = {1,2,", n} denote the set of SUs. At time instant s ∈ [t0 , T ] , the signal-to-interference ratio (SIR) of SU i, for i ∈ N , is equal to ⎛ γi ( s ) = (W R ) ⋅ ⎜⎜ hi pi ( s) ⎝
⎞ h j p j ( s ) + v 2 ⎟⎟ , where pi(s) is the transmit power of SU i, hi j ∈N \ i ⎠
∑
is the channel gain from SU i to the base station of CR system, v2 is the constant background noise power of the base station of CR system, W is the system bandwidth, and R is the transmission rate of SUs. Let pi and d r denote the maximum transmit power of SU i and the cell radius of CR system, respectively. Therefore, the transmit power of SU i should satisfy pi ( s) ∈ [0, pi ] . Assume that pi is a monotone increasing function of Euclidean distance di ( 0 ≤ d i ≤ d r ) from SU i to the base station of CR system, i.e., pi = μ d i5 , where μ > 0 is the power regulation factor. Moreover, assume that di can be acquired through sensing the surrounding environment by SU i. The channel gain hi is given by hi = A diθ , where A > 0 is the constant factor and θ ∈ [3,6] is the path loss factor. To guarantee a QoS requirement, the SIR of SU i should exceed the desired target SIR γitar to recover the transmitted data correctly, i.e., γi ( s ) ≥ γitar . Furthermore, to protect PUs from the harmful interference, it is clearly required that the total transmit power of SUs should not exceed the constraint of the average power limit pth , i.e., ∑ pi ( s ) ≤ pth . Assume that the transmission paths in CR system are valid i∈N
in AWGN channels. According to [3], the throughput of SU i at time instant s ∈ [t0 , T ] , for i ∈ N , can be written as ti ( s ) = log 2 (1 + k ⋅ γ i ( s )) , where k > 0 is the constant factor.
3 Distributed N-Cooperative Power Allocation Definition 1. The N-cooperation is defined as a scenario that all of SUs in a single cell within CR system agree to cooperate, i.e., full cooperation. For N-cooperation power allocation, assume that SUs agree to constitute grand coalition N through full cooperation for their common interests. We introduce two cost functions of SU i to formulate the payoff function, i.e., the power reduction (PR) cost function Ci ( pi ( s )) and the power radiation damage (PRD) cost function Di ( x( s )) . The PR cost function of SU i at time instant s ∈ [t0 , T ] is defined as
92
S. Gao et al.
Ci ( pi ( s )) =
λ 2
⋅ ( pi ( s ) − pi )
2
(1)
where λ > 0 is the power regulation factor. To describe the negative effect caused by interference from SUs, we define the PRD cost function of SU i as Di ( x( s )) = π ⋅ x( s)
(2)
where π > 0 is power radiation damage factor and x( s ) is the stock of the accumulated power radiation at time instant s ∈ [t0 , T ] . Combining with differential game theory [4], x( s ) in (2) can be regarded as state variable in differential game. At time instant s ∈ [t0 , T ] , the instant payoff function of SU i can be written as the sum of two cost functions, i.e., gi =
λ 2
⋅ ( pi ( s ) − pi ) + π ⋅ x( s ) 2
(3)
where pi(s) can be regarded as the control variable of SU i in differential game. Therefore, the payoff function of SU i can be given by T 2 ⎡λ ⎤ min ∫ exp(− rs ) ⎢ ⋅ ( pi − pi ) + π ⋅ x ⎥ ds t0 pi ⎣2 ⎦
(4)
where r ∈ [0,1] is the discount rate. According to [4], x( s ) is assumed to satisfy the following differential equation, i.e., x ( s ) = ∑ pi ( s) − δ ⋅ x( s ), i∈ N
x (t0 ) = x0
(5)
where δ > 0 is the power radiation absorption factor. For the convenience of derivation, we relax the time interval of the game and discuss the infinite-horizon differential game [4], i.e., T → ∞ and t0=0 in (4). Let { p1Ν , p2Ν ,", pnΝ } be the transmit power of n SUs under the condition of grand coalition N and assume that there exists continuously differentiable function W ( N , x) , which satisfies Bellman equation in [4], i.e., ⎧ ⎡λ ⎞⎫ 2 ⎤ ∂W ( N , x ) ⎛ rW ( N , x) = min ⎨ ∑ ⎢ ⋅ ( pi − pi ) + π ⋅ x ⎥ + ⎜ ∑ pi − δ ⋅ x ⎟ ⎬ pi ∂x ⎦ ⎝ i∈N ⎠⎭ ⎩i∈N ⎣ 2
(6)
Performing the indicated minimization in (6) yields piN = pi −
1 ∂W ( N , x) ⋅ ∂x
λ
(7)
Substituting piN in (7) into (6), we obtain ∂W ( N , x) ⎡ ⎛ 1 ∂W ( N , x) ⎞ ⎤ ⎪⎫ 2 ⎪⎧ λ rW ( N , x) = min ⎨ ⋅ ( pi − pi ) + π ⋅ x + ⎟ − δ ⋅ x⎥ ⎬ ⎢ ∑ ⎜ pi − λ ⋅ pi ⎪ 2 ∂ x ∂ x ⎠ ⎣ i∈ N ⎝ ⎦ ⎭⎪ ⎩
(8)
On the Performance of Distributed N-Cooperation Power Allocation via Differential Game
93
Solving the differential equations in equation (8), we obtain W ( N , x) =
⎫⎪ nπ ⎧⎪ ⎡ n 2π ⎤ ⎨ ⎢ ∑ pi − ⎥ + rx ⎬ , r (r + δ ) ⎪⎩ ⎣i∈N 2λ (r + δ ) ⎦ ⎪⎭
piN = pi −
nπ
λ (r + δ )
(9)
Compared with the transmit power of SU i in DNPCDG algorithm [2], the transmit power of SU i of the N-cooperation power allocation is theoretically reduced. The DCPADG algorithm is given as follows. Step 1. SUs obtain SH by sensing spectrum. Step 2. Initialization at time instant t0=0: parameters of CR system and dynamic power allocation model, pth , pi (t0 ) ( pi (0) ∈ [0, pi ] , ∑ pi (0) ≤ pth ), and γitar . i∈N
Step 3. Update pi over time within time interval [t0 , T ] . Step 4. Regulate pi ( s) at time instant s ∈ [t0 , T ] through (10). If
∑ pi (s) > pth , go to
i∈N
Step 2. If γi ( s ) < γitar , go to Step 2. If PUs use the SH, go to Step 1. Or go to Step 3. Table 1. Parameters used in simulations Symbol Average power limit Pth Background noise power v2 System bandwidth W Transmission rate R Initialized transmit power Desired target SIR Path gain factor A Path loss factor θ Power regulation factor μ Constant factor for throughput of single SU k Power reduction factor λ Power radiation damage factor π Discount rate r Power radiation absorption factor δ
Default Value 2.5W 2×10-15mW 106Hz 104bits/s 2.22×10-16mW 8 0.097 4 2×10-14 0.2 1.25×10-6 5×10-3 0.05 0.03
4 Numerical Results and Conclusions In the simulations, we evaluate the performance of DCPADG algorithm by comparing it with the DNPCDG algorithm [2] and the conventional SIR-balancing algorithm [5]. The iterative function of power regulation of SU i in SIR-balancing algorithm [5] is given by pi(l +1) = ( γitar γi(l ) ) ⋅ pi(l ) , l = 0,1, 2," The feedback Nash equilibrium of the transmit power of SU i in DNPCDG algorithm [2] is given by pi∗ = pi − π λ (r + δ ) . We consider a single-cell CR system with n = 10 randomly distributed SUs and dr=500m. The distance from SUs to the base station of CR system is set to the same values as that in [2]. The other parameters used in simulations are given in Table 1. Fig. 2 compares the transmit power of the DCPADG algorithm, the DNPCDG algorithm and the SIR-balancing algorithm. We observe from Fig. 2 that the transmit power of the proposed DCPADG algorithm is lower than those of the DNPCDG
94
S. Gao et al.
Fig. 1. Comparison of transmit power of the proposed DCPADG algorithm, the DNPCDG algorithm and the SIR-balancing algorithm.
Fig. 2. Comparison of throughput of the proposed DCPADG algorithm, the DNPCDG algorithm and the SIR-balancing algorithm.
algorithm and the SIR-balancing algorithm in the range of distance from SU to base station between 200m and 500m, which indicates that the DCPADG algorithm is more suitable for the SUs with the farther distance to the base station of CR system. Fig. 3 shows that the comparison of throughput of the DCPADG algorithm, the DNPCDG algorithm and the SIR-balancing algorithm. It can be easily seen that the throughput of the DCPADG algorithm, the DNPCDG algorithm and the SIRbalancing algorithm is shown as a gradual increasing trend with the growth of the distance from SU to base station. It is obvious that the throughput of the DCPADG algorithm is higher than those of the DNPCDG algorithm and the SIR-balancing algorithm in the range of distance from SU to base station between 45m and 430m. In this paper, we study the distributed cooperative power allocation problem in a single-cell CR system and further propose the DCPADG algorithm. Numerical results demonstrate that the proposed algorithm can effectively reduce the transmit power and improve the throughput of SUs. Acknowledgments. This work is funded in part by the NSFC under Grant No. 60903004.
References 1. Mitola III, J., Maguire, G.: Cognitive radio: making software radios more personal. IEEE Personal Communications 6(4), 13–18 (1999) 2. Zhang, L., Zhou, X., Wang, J., Huang, W., Ma, Z.: Power Control Algorithm Based on Differential Game for CR System. Journal of Electronics & Information Technology 32(1), 141–145 (2010) 3. Qiu, X., Chawla, K.: On the performance of adaptive modulation in cellular systems. IEEE Transactions on Communications 47(6), 884–895 (1999) 4. Yeung, D.W.K., Petrosyan, L.A.: Cooperative Stochastic Differential Games. Springer, Heidelberg (2005) 5. Koskie, S., Gajic, Z.: A Nash game algorithm for SIR-based power control in 3G wireless CDMA networks. IEEE/ACM Transactions on Networking 13(5), 1017–1026 (2005)
Energy-Efficient Restricted Greedy Routing for Three Dimensional Random Wireless Networks Minsu Huang1, Fan Li2, , and Yu Wang1, 1
University of North Carolina at Charlotte, USA {mhuang4,yu.wang}@uncc.edu 2 Beijing Institute of Technology, China
[email protected]
Abstract. In this paper, we investigate how to design energy-efficient localized routing in a large-scale three-dimensional (3D) wireless network. Several 3D localized routing protocols were proposed to seek either energy efficiency or delivery guarantee in 3D wireless networks. However, recent results [1, 2] showed that there is no deterministic localized routing algorithm that guarantees either delivery of packets or energy efficiency of its routes in 3D networks. In this paper, we focus on design of a simple localized routing method which can provide energy efficiency with high probability in a randomly deployed 3D network. In particular, we extend our previous routing method designed for 2D networks [3] to 3D networks. The proposed 3D routing method is a simple variation of 3D greedy routing and can guarantee energy efficiency of its paths with high probability in random 3D networks. We also study its asymptotic critical transmission radius to ensure the packet delivery with high probability in random 3D networks. Simulation results confirm our theoretical results.
1 Introduction Recently, three-dimensional (3D) wireless network has received significant attention [4, 5, 6, 7, 8], due to its wide range of potential applications (such as underwater sensor networks [9]). However, the design of networking protocols for 3D wireless networks is surprisingly more difficult than that for 2D networks. In this paper, we focus on one particular problem in 3D networks: energy efficient localized geographic routing. In localized geographic routing, the forwarding decision is made by the intermediate node based solely on its local information. Without the route discovery phase and maintenance of routing tables, it enjoys the advantages of lower overhead and higher scalability than other traditional routing protocols. This makes it very suitable for 3D networks. Greedy routing is one of the most popular localized routing methods, in which a packet is greedily forwarded to the closest node to the destination in order to minimize the average hop count. Greedy routing can be easily extended to 3D case. Actually, several under-water routing protocols [6, 10] are just variations of 3D greedy routing.
The work of F. Li is supported in part by the National Natural Science Foundation of China under Grant No. 60903151, the Beijing Key Discipline Program, and funds provided by Beijing Institute of Technology. The work of M. Huang and Y. Wang is supported in part by the US National Science Foundation (NSF) under Grant No. CNS-0721666 and No. CNS-0915331. G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 95–104, 2010. c Springer-Verlag Berlin Heidelberg 2010
96
M. Huang, F. Li, and Y. Wang
However, to guarantee packet delivery or energy efficiency of 3D routing is not straightforward and very challenging. Simple greedy routing may fail to reach the destination when falls into a local minimum (a node without any “better” neighbors). Face routing [11] can be used on planar topology to recovery from local minimum and guarantee the delivery in 2D networks, but there is no planar topology concept any more in 3D networks. In fact, Durocher et al. [1] recently proved that there is no deterministic localized routing algorithm for 3D networks that guarantees the delivery of packets. On the other hand, even a localized routing method can find the route to deliver the packet, it may not guarantee the energy efficiency of the path, i.e., the total power consumed compared with the optimal could be very large in the worst case. Several energy-aware localized 2D routing protocols [12, 13, 14] already took the energy concern into consideration, but none of them can theoretically guarantee the energy-efficiency of their routes. This is true for all existing 3D localized routing methods too. Recently, Flury and Wattenhofer [2] showed an example of a 3D network (Figure 1 of [2]) where the path found by any localized routing protocol to connect two nodes s and t has energy consumption asymptotically at least Θ(d3 ) in the worst case. Here d is the optimal energy consumption to connect s and t. Therefore, in this paper, we focus on the design of a simple localized routing method which can provide energy efficiency with high probability in a randomly deployed 3D network. In particular, we extend our previous routing method designed for 2D networks [3] to 3D networks. The proposed 3D routing method is a simple variation of 3D greedy routing and can guarantee energy efficiency of its path with high probability if it finds one in random 3D networks. To ensure that our routing method can find paths with high probability, we also study its asymptotic critical transmission radius (CTR) in random 3D networks. We prove that for a 3D network formed by nodes, that are generated by a Poisson point process of density n over a convex compact region of unit volume, the CTR for our proposed 3D routing is asymptotic almost sure (a.a.s.) at most ln n 2 for any β > β0 and at least 3 3β4πn for any β < β0 . Here, β0 = 1−cosα where α is an parameter used by our routing method. The rest of the paper is organized as follows. Section 2 presents our network model and a formal definition of CTR. Section 3 gives our proposed 3D localized routing protocol and derived bounds on its CTR. Section 4 shows our simulation results and Section 5 summarizes the paper. 3
3β ln n 4πn
2 Preliminaries Network Model and Assumptions: We consider a set V of n wireless devices (called nodes hereafter) uniformly distributed in a compact and convex 3D region D with unitvolume in R3 . By proper scaling, we assume the nodes are represented by a Poisson point process Pn of density n over a unit-volume cube D. Each node knows its position information and has a uniform transmission radius r (or rn ). Then the communication network is modeled by a unit disk graph G(V, r), where two nodes u and v are connected if and only if their Euclidean distance is at most r. Hereafter, we use u − v to denote the Euclidean distance between u and v. For a link uv ∈ G(V, r), we use uv
Energy-Efficient Restricted Greedy Routing
97
to denote its length. We further assume that the energy needed to support the transmission of a unit amount of data over a link uv is e(uv), where e(x) is a non-decreasing function on x. |A| is shorthand for the volume of a measurable set A ⊂ R3 . An event is said to be asymptotic almost sure if it occurs with a probability converges to one as n → ∞. To avoid trivialities, we assume n to be sufficiently large if necessary. Critical Transmission Radius for Greedy-based Routing: In any greedy-based routing, the packet may be dropped by an intermediate node when it could not find any of its neighbors that is “better” than itself. One way to ensure that the routing is successful for every source-destination pair is during the topology control phase each node is set with a sufficiently large transmission radius such that every intermediate node will always find a better neighbor. Critical transmission radius for routing algorithm is first studied by [15]. A routing method A is successful over a network G if the routing method A can find a path for any pair of source and destination nodes. Then we can define the critical transmission radius (CTR) of A as follows: Definition 1. Given a routing method A and a set of wireless nodes V , the critical transmission radius, denoted as ρA (V ), for successful routing of A over V is the minimum transmission radius r such that method A over the network G(V, r) is successful. The subscript A will be omitted from ρA (V ) if it is clear from the context. In [15], Wan et al. derived the CTR of 2D greedy routing in random networks. Recently, Wang et al. [8] also derived the CTR of 3D greedy routing in random 3D networks. In this paper, we will use similar techniques from [15, 8] to study the CTR of our 3D routing.
3 Energy-Efficient Restricted 3D Greedy Routing In this section, we present details of our energy-efficient localized 3D routing method and theoretical analysis on its critical transmission radius in 3D random networks. 3.1 Routing Method Our energy-efficient localized 3D routing method is a variation of classical 3D greedy routing and an extension of a localized routing method [3] we designed for 2D networks. In 3D greedy routing, current node u selects its next hop neighbor based purely on its distance to the destination, i.e., it sends the packet to its neighbor who is closest to the destination. However, such choice might not be the most energy-efficient link locally, and the overall route might not be globally energy-efficient too. Therefore, our routing method use two concepts energy mileage and restricted region to refine the choices of forwarding nodes in 3D greedy routing. Energy Mileage: Given a energy model e(x), energy mileage is the ratio between x . the transmission distance and the energy consumption of such transmission, i.e., e(x) r0 x Let r0 be the value such that e(r0 ) = maxx e(x) . We call r0 as the maximum energy x mileage distance1 under energy model e(x). We assume that the energy mileage e(x) is an increasing function when x < r0 and a decreasing function when x > r0 . 1
Here, we assume that d( e(x) )/dx is monotone increasing, thus, r0 is unique. x
98
M. Huang, F. Li, and Y. Wang
This assumption is true for most of commonly used energy models. For example, if 2 e(uv) = uv + c is the energy √ used by sending message from u to v, the maximum energy mileage distance r0 = c. Our 3D localized routing greedily selects the neighbor who can maximize the energy mileage as the forwarding node. Restricted Region: Instead of selecting the forwarding node from all neighbors of current node u (a unit ball in 3D as shown in Figure 1(a)), our 3D routing method prefers the forwarding node v inside a smaller restricted region. The region is defined inside a 3D cone with an angle parameter α < π/3, such that angle ∠vut ≤ α, as shown in Figure 1(b). The use of α (restricting the forwarding direction) is to bound the total distance of the routing path. Then the restricted region is a region inside this 3D cone and near the maximum energy mileage distance r0 , such that every node v inside this area satisfies η1 r0 ≤ uv ≤ η2 r0 , as shown in Figure 1(b). Here, η1 and η2 are two constant parameters. This can help us to prove the energy-efficiency of the route. Notice that both these ideas are not completely new. Restricted region with an angle has been used in some localized routing methods, such as nearest/farthest neighbor routing [16], while concepts similar to energy mileage have been used in some energyaware localized routing methods [12,14]. However, combining both of these techniques to guarantee energy efficiency is first done in our previous work [3] for 2D networks. In this paper, we further adapt them into 3D routing. Our energy-efficient localized 3D routing protocol is given in Algorithm 1. There are four parameters used by our method. Three adjustable parameters 0 < α < π3 and η1 < 1 < η2 define the restricted region, while r0 is the best energy mileage distance based on the energy model. For example, the following setting √ of these parameters can be used for energy model e(x) = x2 + c: α = π4 , r0 = c, η1 = 1/2 and η2 = 2. Hereafter, we denote the routing algorithm, energy-efficient restricted greedy, as ERGrd if no greedy routing (Grd) is used when no node v satisfies that ∠vut ≤ α. If Grd is applied afterward, then the routing protocol is denoted ERGrd+Grd. Notice that if Grd fails to find a forwarding node, randomized scheme [2] could also be applied.
r
t
u
r0 u
t
α
v
(a) all possible forwarding neighbors (b) best energy mileage forwarding v u
α
t
u
α
t
v
(c) greedy forwarding inside 3D cone
(d) classical greedy forwarding
Fig. 1. Illustrations of our 3D routing: (a) energy-efficient forwarding in the restricted region, (b) greedy forwarding in the 3D cone, (c) greedy forwarding when the 3D cone is empty
Energy-Efficient Restricted Greedy Routing
99
Algorithm 1. Energy-Efficient Restricted 3D Greedy Routing 1: while node u receives a packet with destination t do 2: if t is a neighbor of u then 3: Node u forwards the packet to t directly. 4: else if there are neighbors inside the restricted region and r0 < r then uv is 5: Node u forwards the packet to the neighbor v such that its energy mileage e(uv) maximum among all neighbors w inside the restricted region, as shown in Figure 1(b). 6: else if there are neighbors inside the 3D cone then 7: Node u finds the node v inside the 3D cone (Figure 1(c)) with the minimum t − v. 8: else 9: Greedy routing (Figure 1(d)) is applied, or the packet is simply dropped. 10: end if 11: end while
The path efficiency of ERGrd is given by the following two theorems. The detail proofs of these two theorems are exactly the same with the proofs of Theorems 1-3 in [3] for 2D network, thus are ignored here. Theorem 1. When ERGrd routing indeed finds a path PERGrd (s, t) from the source s to the target t, the total Euclidean length of the found path is at most δt − s where δ = 1−2 1sin α , thus, a constant factor of the optimum. 2
Theorem 2. When ERGrd routing indeed finds a path PERGrd (s, t) from the source s to the target t, the total energy consumption of the found path is within a constant factor σ of the optimum. When r0 ≥ r, σ depends on α; otherwise, depends on η1 , η2 and α. 3.2 Critical Transmission Radius of 3D ERGrd Routing Notice that ERGrd routing may fail, as all other greedy-based methods do, when an intermediate node cannot find a better neighbor to forward the packet. We now study the critical transmission radius for ERGrd routing in random wireless networks. Given a set of nodes V distributed in a region D, the critical transmission radius ρ(V ) for successful routing by 3D ERGrd is max
min
u,v w: ∠wuv≤α
w − u.
(1)
By setting the r = ρ(V ), ERGrd can always find a forwarding node inside the 3D cone region, thus can guarantee its packet delivery. In this section, we prove a similar result as in [15, 3, 8] for our restricted 3D greedy routing method, 3D ERGrd. 2 Theorem 3. Let β0 = 1−cosα and n 43 πrn3 = β ln n for some β > 0. Then, 1. If β > β0 , then ρ (Pn ) ≤ rn is a.a.s.. 2. If β < β0 , then ρ (Pn ) > rn is a.a.s.. 4π/3 2 = 1−cosα is the ratio between the volume of a unit ball Here, β0 = 2π(1−cosα)/3 and the volume of a 3D cone (the forwarding region) inside the ball. Next, we present the detailed proofs for two parts of this theorem. To simplify the argument, we ignore boundary effects by assuming that there are nodes outside D with the same distribution. So, if necessary, packets can be routed through those nodes outside D.
100
M. Huang, F. Li, and Y. Wang
Upper Bound of Theorem 3: To prove the upper bound, it is sufficient to show that when each node has a transmission radius rn satisfying the above condition and β > β0 , for every pair of nodes u and v there is always a node w ∈ Pn such that ∠wuv ≤ α and w − u ≤ rn , i.e., any intermediate node u can find a “better” neighbor w towards the destination node v. Given a point distribution Pn , let S(Pn , rn ) be the minimum number of such neighboring nodes w that can be chosen by any intermediate node u for any possible destination v. As proved in [15], it suffices to prove that the cardinality |S(Pn , r)| > 0. Instead, we now prove a stronger result shown in the following lemma. Lemma 1. Suppose that n 43 πrn3 = β ln n for β > β0 . Then for any constant some β1 β1 ∈ (β0 , β), it is a.a.s. that S (Pn , rn ) > L β0 ln n. Here L(x) = xφ−1 (1/x) for x > 0 and φ(x) = 1 + x ln x − x for x > 0.
Proof. Given a node u, the region that node u can choose its neighbor to forward data is a 3D cone with angle 2α, as shown in Figure 1(c). Let Y denote this 3D cone and d denote its diameter (i.e., the largest distance between any two points inside √ it). Clearly d = rn when α ≤ π6 , and d = 2 sin α · rn when π6 ≤ α < π3 . Thus, d < 3rn . Assume that the space is partitioned into 3D grids (equal-size cubes) of side length η, which we call it η-tessellation of space. Here, we consider an εd-tessellation, where 4 ε = 27β (1 − ββ2 ). A polycube is defined as the set of cubes that intersect with a 0 convex and compact region, e.g., Y. Notice that when the grid-partition shifts, we will have different polycubes for the fixed region Y. A polycube in a η-tessellation is said to have a span s if it can be contained in a cube of side-length s · η. We are only interested in polycube that has span at most 1ε and volume at least a certain fraction of 4π 3 3 rn . Assume that, given Y, there are In different such polycubes that are completely β2 ln n 3 contained inside, with span at most 1ε and volume at least ββ02β 4π 3 rn = ( β0 ) n . For ith such polycubes, let Xi denote the number of nodes of V contained inside. Then Xi is a Poisson RV with rate at least ββ20 ln n. Since the number of cubes in D is 1 3 O εd = O lnnn , by Lemma 3 of [8], In = O lnnn . By Lemma 6 of [15], it is In mini=1 Xi β2 β1 a.a.s. that ≥ L > L . ln n β0 β0 n To prove the lemma, it is sufficient to show that S(Pn , r) ≥ minIi=1 Xi . In other words, we only need to show that for any Y, it contains a polycube P has span at r3 . For a 3D cone Y, let P denote the polycube inmost 1ε and volume at least ββ02β 4π 3 n duced by Y−√3εd . Here Y−x denotes the region of Y whose points are of distance at x from the boundary of Y. Then, P ⊆ Y, and the span of P is at most least √ d−2 3εd 4 + 1 < 1ε . By Lemma 2 in [8] and the fact that |Y| = 43 πrn3 β10 > 9√ πd3 β10 , εd 3 √ √ 0 we have |P | ≥ Y−√3εd ≥ |Y| − πd2 3εd = |Y| − 3επd3 > |Y| − 27β 4 ε |Y| = β2 β2 4 3 1 0 |Y| 1 − 27β 4 ε = β |Y| = β0 3 πrn β . This completes the proof of the lemma. ln n Lower Bound of Theorem 3: We now show that, if rn = 3 3β4πn for any β < β0 , a.a.s., there are two nodes u and v such that we cannot find a node w for forwarding by node u, i.e., there does not exist node w inside the 3D cone. Again we partition the space using equal-size cubes (called cells) with side-length ηrn for a constant 0 < η to
Energy-Efficient Restricted Greedy Routing
101
(1+δ)rn
δrn+ rn
u u
w rn
v
η rn
(a) selection of u
(b) no forwarding node
Fig. 2. Illustrations of the proof of lower bound: (a) a cubic cell and the region where we select a node u; (b) the event that node u cannot find a forwarding node w to reach a node v
be specified later. Thus the number of cells, denoted by In here, that are fully contained inside the compact and convex region D with unit volume, is Θ( η31r3 ) = Θ( lnnn ). Let n Eu,v denote the event that no forwarding node w (in the 3D cone) exists for node u to reach node v. Then to prove our claim, it is equivalent to prove that the probability of at least one of the event Eu,v happens a.a.s., i.e., 1 − Pr(none of event Eu,v happens). Since the events Eu,v are not independent for all pairs u and v, we will only consider a special subset of events that are independent. Consider any cell produced by the 3D grid partition that are contained inside D. For each cell, we draw a shaded cube with side-length (η − 2(1 + δ))rn and it is of distance (1 + δ)r to the boundary of the cell, as shown in Figure 2 (a). We only consider the case when node u is located in this shaded cube. We also restrict the node v to satisfy that rn < u − v ≤ (1 + δ)rn , i.e., in the torus region in Figure 2 (b). Clearly, node v will also be inside this cell, and the shaded 3D cone where the possible forwarding node could locate is also inside this cell. Thus, events Eu1 ,v1 and Eu2 ,v2 are independent if u1 and u2 are selected as above from different cells. For each cell i, we compute the probability that event Eui ,vi happens, where ui is selected from the shaded cube of cell i and vi is selected such that rn < vi − ui ≤ (1 + δ)rn . Recall that for any region A, the probability that it is empty of any nodes is e−n|A| . 3 3 Clearly, the probability that node ui exists is 1 − e−n(η−2−2δ) rn since the shared cube 3 3 4 has volume (η −2−2δ)3 rn3 ; the probability that node vi exists is 1−e−n 3 π((1+δ) −1)rn 4 since the torus has volume 3 π((1+δ)3 −1)rn3 . Given node ui and vi , the probability that 3 2 event Eui ,vi happens is e−n 3 π(1−cosα)rn = e−β/β0 ln n = n−β/β0 . Consequently, event 3 3 Eu,v happens for some node pairs ui and vi is Pr(Eui ,vi ) ≥ (1 − e−n(η−2−2δ) rn )(1 − 3 3 3 3 4 e−n 3 π((1+δ) −1)rn )n−β/β0 = (1 − n−β(η−2−2δ) 3/4π )(1 − n−β((1+δ) −1) )n−β/β0 . Thus, the probability that ERGrd routing fails to find a path for some source/destination pairs is Pr(at least one of events Eu,v happens) ≥ Pr(at least one of Eui ,vi happens)= 1 − Pr(none of Eui ,vi happens) = 1 − (1 − Pr(Eui ,vi ))In = 1 − eIn ·ln (1−Pr(Eui ,vi )) ≥ 3 1 − e−In ·Pr(Eui ,vi ) . Notice that In · Pr(Eui ,vi ) = Θ( lnnn )(1 − n−β(η−2−2δ) 3/4π )(1 − 3
1−β/β0
n−β((1+δ) −1) )n−β/β0 n ln n , which goes to ∞ as n → ∞ when β < β0 , η − 2 − 2δ > 0, and δ > 0. This can be easily satisfied, e.g., δ = 1, η = 5. Thus, limn→∞ 1 − e−In ·Pr(Eui ,vi ) = 1. This completes the proof.
102
M. Huang, F. Li, and Y. Wang
4 Simulation In this section, we study performance of our ERGrd routing in random 3D networks via extensive simulation. Critical Transmission Radius of ERGrd Routing: To confirm our theoretical analysis, we conduct simulations to study the real values of CTR of ERGrd routing method in random 3D networks. We randomly generate 1000 networks with n nodes in a 100 × 100 × 100 cubic region, where n is from 50 to 500. For each network V , we compute the CTR ρ(V ) of ERGrd by using Equation (1). Figure 3 show the probability distribution function of ρ(V ) when α = π/6 and α = π/4. It is clear that the CTR satisfies a transition phenomena, i.e., there is a radius r0 such that ERGrd can successfully deliver all packets when r > r0 and can not deliver some packets when r < r0 . Notice that the transition becomes faster when the number of nodes increases. This confirms our theoretical analysis on the existence of CTR. In addition, from the figures, we can find that larger node density always leads to smaller value of CTR. The practical value of ρ(V ) is larger than the theoretical bound in our analysis, since the theoretical bound is standing for n → ∞. Compared the two cases with α = π/6 and π/4, larger CTR is required if smaller restricted region (i.e. smaller α) is applied. Probability of r>ρ(V)
1
1
0.8
0.8
Probability
Probability
Probability of r>ρ(V)
0.6
0.4
n=50 n=100 n=200 n=300 n=400 n=500
0.2
0 30
40
50
60
70
80
Transmission Radius, r
(a) PDF of ERGrd-30
90
0.6
0.4
n=50 n=100 n=200 n=300 n=400 n=500
0.2
100
0 20
30
40
50
60
70
80
Transmission Radius, r
(b) PDF of ERGrd-45
Fig. 3. PDF curves of 3D ERGrd routing when α = π/6 (30◦ ) and α = π/4 (45◦ )
Network Performance of ERGrd Routing: We implement the classic 3D greedy routing (Grd) and variations of our proposed restricted greedy routing (specifically, RGrd-30, ERGrd-45, ERGrd+Grd-30, and ERGrd+Grd-45, where 30 or 45 is the degree value of α.) in our simulator. We assume that the energy consumption of a link uv is 2 e(uv) = uv + c, where c = r2 /4. The values of η1 and η2 are 1/2 and 2. By setting various transmission radii, we generate 100 connected random networks with 100 wireless nodes again in a 100 × 100 × 100 cubic region. We randomly select 100 source-destination pairs for each network and test five greedy-based 3D routing. All results presented hereafter are average values over all routes and networks. Figure 4 illustrates the average delivery ratios of the five routing methods. Clearly, the delivery ratio increases when r increases. After r is larger than a certain value, it
Energy-Efficient Restricted Greedy Routing
103
1
Average Delivery Ratio
0.9 0.8 0.7
Grd ERGrd−30 ERGrd−45 ERGrd+Grd−30 ERGrd+Grd−45
0.6 0.5 0.4 0.3 0.2 0.1
25
30
35
40
45
50
55
Transmission Radius
Fig. 4. Average delivery ratios of 3D ERGrd routing methods in random networks
always guarantees the delivery. Notice that ERGrd methods without Grd backup have lower delivery ratio under the same circumstance, since they have smaller region to select the next hop node. With Grd backup, the delivery ratios of ERGrd+Grd methods are almost the same with those of Grd (simple 3D greedy). Figure 5(a) and (b) illustrate the average length stretch factors and energy stretch factors of all routing methods, respectively. Here, the length/energy stretch factor of a path from node s to node t is the ratio between the total length/energy of this path and the total length/energy of the optimal path connecting s and t. Smaller stretch factor of a routing method shows better path efficiency. For the length stretch factor, the ERGrd with α = π/6 has the best length efficiency. It is surprising that with α = π/4 the length of ERGrd path could be longer than simple greedy. However, when considering the energy efficiency, all ERGrd methods can achieve better path efficiency than simple greedy method. Notice that smaller restricted region leads to better path efficiency, however it also has lower delivery ratio. Therefore, it is a trade-off between path efficiency and packet delivery. It is also clear that when the network is dense (with large transmission radius), ERGrd and ERGrd+Grd are almost the same, since ERGrd can always find nodes inside the 3D cone. 1.2 Grd ERGrd−30 ERGrd−45 ERGrd+Grd−30 ERGrd+Grd−45
1.08 1.07 1.06 1.05 1.04 1.03 1.02 1.01 1
25
30
35
40
45
Transmission Radius
(a) Length Stretch Factor
50
55
Average Energy Stretch Factor
Average Length Stretch Factor
1.1 1.09
1.18 1.16 1.14
Grd ERGrd−30 ERGrd−45 ERGrd+Grd−30 ERGrd+Grd−45
1.12 1.1 1.08 1.06 1.04 1.02 1
25
30
35
40
45
50
55
Transmission Radius
(b) Energy Stretch Factor
Fig. 5. Path efficiency (length stretch factor and energy stretch factor) of 3D ERGrd routing methods in random networks
104
M. Huang, F. Li, and Y. Wang
5 Conclusion In this paper, we propose a simple localized routing protocol ERGrd for 3D networks. The proposed method achieves the energy efficiency by limiting its choice inside a restricted region and picking the node with best energy mileage. We then theoretically derive the critical transmission radius of our proposed 3D routing for random 3D networks. This provides the insight about how large the transmission radius should be set for our method to guarantee the delivery of packets between any two nodes. We also conduct extensive simulations to confirm our theoretical results.
References 1. Durocher, S., Kirkpatrick, D., Narayanan, L.: On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 546–557. Springer, Heidelberg (2008) 2. Flury, R., Wattenhofer, R.: Randomized 3D geographic routing. In: IEEE Infocom (2008) 3. Wang, Y., Song, W.-Z., Wang, W., Li, X.-Y., Dahlberg, T.: LEARN: localized energy aware restricted neighborhood routing for ad hoc networks. In: Proc. of IEEE SECON (2006) 4. Alam, S.M.N., Haas, Z.J.: Coverage and connectivity in three-dimensional networks. In: Proc. of ACM Mobicom (2006) 5. Kao, G., Fevens, T., Opatrny, J.: Position-based routing on 3D geometric graphs in mobile ad hoc networks. In: Proc. of CCCG 2005 (2005) 6. Pompili, D., Melodia, T.: Three-dimensional routing in underwater acoustic sensor networks. In: Proceedings of ACM PE-WASUN 2005, Montreal, Canada (October 2005) 7. Ravelomanana, V.: Extremal properties of three-dimensional sensor networks with applications. IEEE Transactions on Mobile Computing 3(3), 246–257 (2004) 8. Wang, Y., Yi, C.-W., Li, F.: Delivery guarantee of greedy routing in three dimensional wireless networks. In: Li, Y., Huynh, D.T., Das, S.K., Du, D.-Z. (eds.) WASA 2008. LNCS, vol. 5258, pp. 4–16. Springer, Heidelberg (2008) 9. Akyildiz, I.F., Pompili, D., Melodia, T.: Underwater acoustic sensor networks: research challenges. Ad Hoc Networks 3(3), 257–279 (2005) 10. Xie, P., Cui, J.-H., Lao, L.: VBF: Vector-based forwarding protocol for underwater sensor networks. In: Boavida, F., Plagemann, T., Stiller, B., Westphal, C., Monteiro, E. (eds.) NETWORKING 2006. LNCS, vol. 3976, pp. 1216–1221. Springer, Heidelberg (2006) 11. Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. ACM/Kluwer Wireless Networks 7(6) (2001) 12. Li, C.-P., Hsu, W.-J., Krishnamachari, B., Helmy, A.: A local metric for geographic routing with power control in wireless networks. In: Proc. of IEEE SECON (2005) 13. Melodia, T., Pompili, D., Akyildiz, I.F.: Optimal local topology knowledge for energy efficient geographical routing in sensor networks. In: Proc. of IEEE INFOCOM (2004) 14. Seada, K., Zuniga, M., Helmy, A., Krishnamachari, B.: Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks. In: Proc. ACM Sensys (2004) 15. Wan, P.-J., Yi, C.-W., Yao, F., Jia, X.: Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks. In: Proc. of ACM Mobihoc (2006) 16. Li, X.-Y., Calinescu, G., Wan, P.-J., Wang, Y.: Localized Delaunay triangulation with applications in wireless ad hoc networks. IEEE Trans. on Parallel and Distributed Systems 14(10), 1035–1047 (2003)
Adaptive Energy and Location Aware Routing in Wireless Sensor Network Hong Fu1,*, Xiaoming Wang1, and Yingshu Li2 1
Department of Computer Science, Shaanxi Normal University, Xi’an, China, 710062
[email protected],
[email protected] 2 Department of Computer Science, Georgia State University, Atlanta, USA, 30303
[email protected]
Abstract. This paper proposes a novel routing algorithm called AELAR for wireless sensor networks to meet QoS requirements: energy conservation and data delay reduction. Firstly, we propose a novel method of dividing routing request zone and construct a select equation which can enlarge the energy awareness as network time goes on. We make the routing request zone and factors in select equation changed automatically. Simulation results show that AELAR outperforms traditional algorithms in the performance of network lifetime, utilization and consumption balancing of energy and data delay. Keywords: Wireless sensor networks, Energy efficient routing, Distance level.
1 Introduction Sensor nodes in Wireless sensor networks (WSNs) have resource constraints which include limited energy, processing capacity, storage, communication range and bandwidth [1]. These unique features have raised special problems that must be solved while designing routing protocols. For instance, in some applications, routing algorithms must meet QoS requirements such as energy conservation and data delay reduction. Some routing algorithms (e.g., [2], [3], [4]) limit the routing search to request zones to reduce the cost of flooding. Geographical routings (e.g., [5], [6]) use greedy forwarding mechanisms to forward packets. GPSR [7] is such an efficient, classic algorithm. But GPSR is based on a single metric. GEAR [8] uses energy aware metric, together with geographical information, to make routing decisions. However, the energy balancing strategy in GEAR increases the average path length. With the progress on the semiconductor technology, wireless sensors’ capabilities of computation, storage may not be limitations in future. However, how to consume energy efficiently is still one of the most challenging problems in WSNs’ researches [9]. The main goals of the research presented in this paper are to: *
This work was supported by NSFC (60773224, 60970054), the Key project of Chinese Ministry of Education under Grant (107106) and the Scientific Research Foundation of State Education Ministry for the Returned Overseas Chinese Scholars.
G. Pandurangan et al. (Eds.): WASA 2010, LNCS 6221, pp. 105–109, 2010. © Springer-Verlag Berlin Heidelberg 2010
106
H. Fu, X. Wang, and Y. Li z z z
Prolong the network lifetime of WSN to deliver more packets; Balance the energy consumption of nodes and achieve energy conservation; Find the routing path as short as possible to reduce data delay.
The rest of the paper is organized as follows: Section 2 describes the network system. Section 3 presents our proposed algorithm. Section 4 demonstrates the effectiveness of AELAR via simulations. Finally, section 5 gives concluding remarks.
2 The Network System Model To simple the question, we assume that all sensors are homogeneous. They have the same ability of communication and the radius of communication is r. They know their neighbors’ and their own location information by location services, e.g., Ad hoc Positioning System with Angle of Arrival [10]. We also assume that there is only one sink in the WSN. Besides, we give the follow definition for our research: Distance level. For a given sensor node ni, let did is the distance from node ni to the sink, the distance level of node ni, dl, is defined as
d l = ⎣d id / m ⎦ .
(1)
Where, m is the distance level dividing standard. It can be determined by special applications. The distance level can indirectly indicate the distance from the sink.
3 Adaptive Energy and Location Aware Routing In this section, we present a novel method of dividing routing request zone and construct a select equation which can be adjusted according to nodes’ distance levels. 3.1 Ellipse-Shape Routing Request Zone and Density Self-adaptation We employ the virtual coordinates [11] to identify the routing request zone. In Fig. 1(a), given the node I, letting O be the origin, the virtual coordinates of a neighboring node (e.g. J), (xj’, yj’), can be calculated by the following equations: ⎧⎪ x j ' = cos(θ ) × ( x j − xi ) + sin(θ ) × ( y j − yi ) ; y − yi . θ = arctan( j ) ⎨ x j − xi ⎪⎩ y j ' = cos(θ ) × ( y j − y i ) − sin(θ ) × ( x j − xi )
(2)
In AELAR, we define the routing request zone as the overlap area of an elliptic region and a disk. In fig.1 (b), the shallow area shows the proposed routing request zones. Letting dij be the distance form node I to node J, the node I can use (3) to learn whether a neighboring node locates in its routing request zone. ( x' − a)2 ( y')2 + ≤1 2 a b2
and
d ij ≤ r .
(3)
From Fig.1 (b), we can find that ellipse parameter a and b (especially, b) have great impact on the size of routing request zone. To simplify the discussion, we assign the
Adaptive Energy and Location Aware Routing in Wireless Sensor Network
(a) Virtual coordinate of node J
107
(b) Different value of b for different nodes
Fig. 1. Virtual coordinate and ellipse-shape routing request zone of a node
value of a as transmission radius r. However, we must take seriously the value of b because it has the most important effect on the size of routing request zone. According to geometric knowledge, the value of y’ of the neighboring nodes which are closer from the sink than the node I is limited by the inequality: y'≤
(4)
2 rd id − r 2 .
Where, did is the distance from the node I to the sink. We hope that the nodes which have long distance from the sink can forward data packets as soon as possible and the nodes near the sink have more options to choose the next hop, so that the nodes near the sink can better balance the energy consumption. To make the node I can adjust the value of b according to its location, we make node I determine the value of b as: (5)
b = δ 2 r d id − r 2 .
Where, δ is determined by the distance level and the transmission radius of each node. Only the neighboring nodes that locate in the routing request zone are considered to be next-hop candidates in AELAR. 3.2 The Select Equation
To select an appropriate node as the next hop for forwarding data packets, AELAR strikes a balance between residual energy and distance metrics. We use the natural logarithm function for residual energy level to enlarge the residual energy difference among neighboring nodes. Letting er be the residual energy of a neighboring node J and ei be the initial energy of node I. Then, the node J’s select factor fj is defined as
{
f j = ln (er / ei ) (did / d jd ) α
β
}.
(6)
In above select equation, α and β are the weight factors of energy consumption ratio and distance ratio. In AELAR, we make the nodes adjust their weight factors automatically according to their distance levels. In WSNs, the nodes closer to the sink usually carry out more forward tasks. We hope these nodes consider more distance
108
H. Fu, X. Wang, and Y. Li
factor so that the total energy consumption is lower. AELAR selects the neighboring node that not only locates in the routing request zone but also has the greatest value of fj as the next hop. The energy effect on the above equation will drastically increase if the residual energy of the node is too low. So, nodes with too low residual energy will be difficult to be chosen as the next hop in the route discovery, which is helpful to balance the energy expenditure.
4 Simulation and Analysis We investigated the AELAR’s performance by comparing it with traditional GPSR and energy-aware GEAR. We also optimized our algorithm (AELAR-O) with the method in [12] to confirm that the paths discovered by AELAR are almost as short as possible. Fig.2(a) shows that number of packets delivered by AELAR is more than GPSR and GEAR during the network lifetime. From Fig.2(b) and Fig.2(c), we can learn that AELAR successfully achieves energy efficiency and has lower energy deviation because the nodes’ energy differences is exaggerated by logarithmic function. Fruthermore, owing to the use of the adaptive mechanism, we learn that AELAR almost has the same average path hop as GPSR from Fig.2(d), which is beneficial to the data delay reduction while considering energy conservation.
(a) Number of packets delivered to the sink
(c) The energy standard deviation
(b) Energy utilization radio of WSN
(d) Average hops of searched paths
Fig. 2. Simulation results for evaluating the performance of AELAR
Adaptive Energy and Location Aware Routing in Wireless Sensor Network
109
5 Conclusions This paper has proposed a new routing algorithm, AELAR, which is location-based, energy-aware, and scalable to discover the paths between the source node and the sink. We first present a novel method of dividing routing request zone and then construct a select equation for a node to choose its next hop. Both the routing request zone and the select equation can be adjusted by the node according to its own location. This adaptive mechanism makes sure that the paths found by AELAR are as short as possible while considering the energy conservation. The simulation results show that AELAR performs better in terms of network lifetime, energy utilization, energy consumption balancing and data delay reduction than traditional routing algorithms.
References 1. Yicka, J., Mukherjeea, B., Ghosal, D.: Wireless sensor network survey. Computer Networks 52(12), 2292–2330 (2008) 2. Woo, K., Yu, C., Lee, D., Youn, H.Y., Ben, L.: Non-blocking, localized routing algorithm for balanced energy consumption in mobile ad hoc networks. In: Proceedings of Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Cincinnati, OH, USA, pp. 117–124 (2001) 3. Ko, Y.B., Vaidya, N.H.: Location-aided routing in mobile ad hoc networks. Wireless Networks 6(4), 307–321 (2000) 4. Shih, T.F., Yen, H.C.: Location-aware routing protocol with dynamic adaptation of request zone for mobile ad hoc networks. Wireless Networks 14(3), 321–333 (2008) 5. Chen, M., Leung, V.C.M., Mao, S., Xiao, Y., Chlamtac, I.: Hybrid geographic routing for flexible energy-delay tradeoff. IEEE Transactions on Vehicular Technology 58(9), 4976–4988 (2009) 6. Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings 11th CCCG Vancouver, BC, Canada, August 1999, pp. 51–54 (1999) 7. Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of ACM Annual Conference on Mobile Computing and Networking, Boston, MA, USA, pp. 243–254 (August 2000) 8. Yu, Y., Govindan, R., Estrin, D.: Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks. In: UCLA Computer Science Department Technical Report, pp. 1–23 (2001) 9. Li, Y., Ai, C., Cai, Z., Raheem, B.: Sensor Scheduling for p-Percent Coverage in Wireless Sensor Networks. Journal of Cluster Computing (May 2009) 10. Kieb, W., Fubler, H., Widmer, J.: Hierarchical location service for mobile ad hoc networks. Mobile Computing and Communications Review 8(4), 47–58 (2003) 11. Chen, M.L., Victor, C.M., Mao, S., Yuan, Y.: Directional geographical routing for real-time video communications in wireless sensor networks. Computer Communications Concurrent Multipath Transport 30(17), 3368–3383 (2007) 12. Shu, L., Zhang, Y., Yang, L.T., Wang, Y., Hauswirth, M.: Geographic routing in wireless multimedia sensor networks. In: Proceedings of the 2nd International Conference on Future Generation Communication and Networking (FGCN 2008), Hainan, China (December 2008)
Utilizing Temporal Highway for Data Collection in Asynchronous Duty-Cycling Sensor Networks Tao Chen, Deke Guo, Honghui Chen, and Xueshan Luo Key Lab of C4 ISR, National University of Defense Technology, 410073 Changsha, China
Abstract. Duty cycling technique is widely used in sensor networks to save energy. Due to coverage and other requirements, sensor nodes may have asynchronous duty schedules, which bring additional challenges for data collection. Existing approaches suffer from different limitations such as requirement of time synchronization. This paper proposed a crosslayer design, which utilizes multihop information to find shortcuts and reduces the delay in data collection. Keywords: sensor networks, data collection, duty cycle.
1
Introduction
Wireless sensor network (WSN) is a key enabling issue for many applications, such as environment monitoring, battlefield surveillance and so on. While sensor nodes are expected to operate for a long periods of time in these applications, they are usually deployed in unattended area and equipped with limited battery. Idle listening is considered to be one of the most significant sources of energy consumption in sensor networks, which reduces the lifetime of network. Duty cycling mechanisms are proposed to reduce such energy consumption. Each node turns its radio off (sleep state) for most of the time, and turns the radio on (active state) periodically for a short period of time. When node is active, it is able to transmit or receive packets. But almost all the proposed duty-