Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features
Wireless Sensor Networks (WSNs) have acquired new features recently, i.e., both the sensor and the antenna of a node can be directional. This brings new challenges to the Connected Coverage (CoCo) problem, where a finite set of targets needs to be monitored by some active sensor nodes, and the conne...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/98263 http://hdl.handle.net/10220/12364 |
| _version_ | 1811690062112358400 |
|---|---|
| author | Liu, Yang Han, Kai. Xiang, Liu. Luo, Jun. |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Liu, Yang Han, Kai. Xiang, Liu. Luo, Jun. |
| author_sort | Liu, Yang |
| collection | NTU |
| description | Wireless Sensor Networks (WSNs) have acquired new features recently, i.e., both the sensor and the antenna of a node can be directional. This brings new challenges to the Connected Coverage (CoCo) problem, where a finite set of targets needs to be monitored by some active sensor nodes, and the connectivity of these active nodes with the sink must be retained at the same time. In this paper, we study the Minimum-Energy Connected Coverage (MeCoCo) problem in WSNs with Omni-directional (O) and Directional (D) features, aiming at minimizing the total energy cost of both sensing and connectivity. Considering different combinations of O and D features, we study the MeCoCo problem under four cases, namely: O-Antenna and O-Sensor (OAOS), O-Antenna and D-Sensor (OADS), D-Antenna and D-Sensor (DADS), as well as D-Antenna and O-Sensor (DAOS). We prove that the MeCoCo problem is NP-hard under all these cases, and present approximation algorithms with provable approximation ratios. In particular, we propose a constant-approximation for OAOS, and polylogarithmic approximations for all other cases. Finally, we conduct extensive simulations and the results strongly confirm the effectiveness of our approach. |
| first_indexed | 2024-10-01T05:58:01Z |
| format | Conference Paper |
| id | ntu-10356/98263 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:58:01Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/982632020-05-28T07:18:11Z Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features Liu, Yang Han, Kai. Xiang, Liu. Luo, Jun. School of Computer Engineering International symposium on Mobile Ad Hoc Networking and Computing (13th : 2012) DRNTU::Engineering::Computer science and engineering Wireless Sensor Networks (WSNs) have acquired new features recently, i.e., both the sensor and the antenna of a node can be directional. This brings new challenges to the Connected Coverage (CoCo) problem, where a finite set of targets needs to be monitored by some active sensor nodes, and the connectivity of these active nodes with the sink must be retained at the same time. In this paper, we study the Minimum-Energy Connected Coverage (MeCoCo) problem in WSNs with Omni-directional (O) and Directional (D) features, aiming at minimizing the total energy cost of both sensing and connectivity. Considering different combinations of O and D features, we study the MeCoCo problem under four cases, namely: O-Antenna and O-Sensor (OAOS), O-Antenna and D-Sensor (OADS), D-Antenna and D-Sensor (DADS), as well as D-Antenna and O-Sensor (DAOS). We prove that the MeCoCo problem is NP-hard under all these cases, and present approximation algorithms with provable approximation ratios. In particular, we propose a constant-approximation for OAOS, and polylogarithmic approximations for all other cases. Finally, we conduct extensive simulations and the results strongly confirm the effectiveness of our approach. 2013-07-26T03:49:34Z 2019-12-06T19:52:55Z 2013-07-26T03:49:34Z 2019-12-06T19:52:55Z 2012 2012 Conference Paper Han, K., Xiang, L., Luo, J., & Liu, Y. (2012). Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features. 2012 13th ACM international symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '12). https://hdl.handle.net/10356/98263 http://hdl.handle.net/10220/12364 10.1145/2248371.2248386 en © 2012 ACM. |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Liu, Yang Han, Kai. Xiang, Liu. Luo, Jun. Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title | Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title_full | Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title_fullStr | Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title_full_unstemmed | Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title_short | Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features |
| title_sort | minimum energy connected coverage in wireless sensor networks with omni directional and directional features |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/98263 http://hdl.handle.net/10220/12364 |
| work_keys_str_mv | AT liuyang minimumenergyconnectedcoverageinwirelesssensornetworkswithomnidirectionalanddirectionalfeatures AT hankai minimumenergyconnectedcoverageinwirelesssensornetworkswithomnidirectionalanddirectionalfeatures AT xiangliu minimumenergyconnectedcoverageinwirelesssensornetworkswithomnidirectionalanddirectionalfeatures AT luojun minimumenergyconnectedcoverageinwirelesssensornetworkswithomnidirectionalanddirectionalfeatures |