近幾年的網路通訊相關研究中，無線感測網路(Wireless Sensor Networks, WSNs)已成為相當熱門的研究領域。透過大量佈設具有低成本、低耗電、小體積、短距無線通訊等特性的無線感測器(Sensors)所建構的無線感測網路已經被廣泛地應用。感測任務的成功與否與感測區域的覆蓋範圍(Coverage)維護與網路鏈結(Connectivity)狀況息息相關。一個可傳輸感測資料至資料收集器之無線感測器的覆蓋範圍才可被視為是有效的覆蓋範圍。目前的研究較少考慮到在網路維護階段，網路連結性對於有效覆蓋範圍的影響，故本論文將分別討論在區域覆蓋與目標點覆蓋之需求下，如何使無線感測網路以最節省電量的方式完成感測任務，以延長網路存活時間。此外，本論文也分別針對上述覆蓋需求與網路特性，提出解決方案。
  如前所述，無線感測網路會因為Sensors失去功能而使得網路產生分割(Partition)，Partition 將嚴重影響Coverage的情況與Connectivity的品質。因此，本論文首先在使用移動性的感測裝置(Mobile Sensor)的網路中，提出一個有效避免Partition 產生的懶惰移動以避免網路分割之通訊協定(A Partition Avoidance Lazy Movement，PALM)。由於任意的移動會造成Mobile Sensors 快速的消耗本身的電量，因此本論文首先提出一懶惰移動策略(lazy movement policy)。此策略可使Mobile Sensors 判斷網路是否即將產生Partition，進而決定是否需要進行移動。接著，本論文也提出一有效移動原理（principles of an effective movement)。根據此原理，Mobile Sensors 可計算一個可以使有效網路覆蓋區域增加最多，但是所需移動距離最短的位置。PALM 擁有下列特色(1)為分散式的協定；(2)能有效維護網路的Connectivity；(3) Mobile Sensors 移動次數少。
  另一方面，本論文接著討論多重感測元件之異質型無線感測網路上的目標點覆蓋問題(Connected Target Coverage Problem)。本論文將無線感測器互相合作以涵蓋感測環境的問題轉換成連結集合涵蓋問題(Connected Set Cover Problem)，再以整數線性規劃(ILP)建構出本問題的模型，並求出最佳解。本論文接著提出剩餘電量優先考量式演算法(Remaining Energy First Scheme, REFS)，REFS 將使感測器以本身電量的多寡來決定是否開啟感測元件與通訊元件。為進一步提升感測器間能量消耗的平衡，本論文另外提出能源效率優先考量式演算法(Energy Efficient First Scheme, EEFS)。有別於REFS，EEFS 將同時考量本身與鄰居的電量、感測能力與通訊能力，使整個網路的能源消耗更有效率。就我們所知，本論文是第一篇解決多重感測元件之異質型無線感測網路上的目標點覆蓋問題的論文。
  整體而言，本論文分別針對區域覆蓋需求下之無線感測網路與目標點覆蓋需求下之異質型無線感測網路，分別提出可有效延長網路存活時間的低電量消耗演算法。實驗模擬的結果顯示出PALM 較其他相關文獻所提出之協定更能避免Partition 的產生，使所有能夠工作的Mobile Sensors 可以貢獻他們的能力，以增加無線感測網路的存活時間。另外，針對異質型無線感測網路上的目標點覆蓋問題，實驗模擬顯示，EEFS 比REFS 更能延長網路存活時間，且與ILP 運算出的最佳網路存活時間相近。

A wireless sensor network (WSN) consists of numbers of sensors deployed in a sensing field in an ad hoc or prearranged fashion for the purposes of sensing, monitoring, or tracking environmental events. Unlike ad hoc networks, a WSN is application-specific, data-centric, and energy-constrained in essence. With the limitation in battery energy, all sensors have to cooperatively work to cover the sensing field of the interest. Thus, to develop efficient schemes beneficial to coverage but less energy waste is very important in WSNs. Basically, the coverage preserving protocols nowadays are proposed for area or target coverage. The impacts of the network connectivity on coverage preserving are not carefully considered. Clearly, even though one scheme can obtain maximal sensing coverage, without ensuring the connectivity of sensors to the sink, it is also useless. Therefore, in this dissertation, the coverage preserving issues for area and target coverage in more complicated network condition are discussed. 
  Recently, mobile sensors have been widely used in a variety of applications in WSNs to achieve the requirement of network coverage. Based on the mobile capability of the sensor, the dissertation proposes a distributed partition avoidance lazy movement (PALM) protocol for mobile sensor networks (MSNs). As mentioned above, connectivity and coverage are two major factors to the success of a sensor network. Therefore, PALM takes both connectivity and coverage into account to avoid network partition and keep high sensing quality. Since sensor movement is the major source of energy consumption, thus, in order not to cause frequent movement, PALM triggers sensor movement only when the network has a risk of partition, but not when coverage holes appear. The dissertation proposes a sufficient condition of keeping a network connected. Based on the condition, PALM adopts the lazy movement policy for a sensor to determine when to move and uses the principles of an effective movement for a sensor to decide where to move. Accordingly, PALM can keep the network connected and can make the effective coverage as large as possible to maintain high sensing quality. 
  On the other hand, the connected target coverage (CTC) problem in wireless heterogeneous sensor networks (WHSNs) with multiple sensing units, termed MU-CTC problem is considered in the dissertation. MU-CTC problem is firstly reduced to a connected set cover problem and further formulated as integer linear programming (ILP) constraints. However, the ILP problem is an NP-complete problem. Therefore, two heuristic but distributed schemes, REFS (Remaining Energy First Scheme) and EEFS (Energy Efficient First Scheme,) are proposed. In REFS, each sensor considers its remaining energy and neighbors' decisions to enable its sensing units and communication unit such that all targets can be covered by required attributes, and the sensed data can be delivered to the sink. The advantages of REFS are its simplicity and less communication overhead incurred. However, to utilize sensors' energy efficiently, EEFS is proposed as well. A sensor in EEFS considers its contribution to the coverage and the connectivity to make a better decision. To our best knowledge, this dissertation is the first one to consider target coverage and connectivity jointly for WHSNs with multiple sensing units. 
  In general, the issues mentioned above are actually essential and important in both area and target coverage. Overall, the protocols to avoid network partition and to schedule sensor’s activity are respectively proposed for the mobile sensor network and the heterogeneous stationary sensor network with multiple sensing units. In comparison with the related work, PALM can reduce the energy consumption and further extend the network lifetime in mobile sensor network due to the lazy movement policy and the principles of an effective movement. Simulation results verify the advantages of the proposed protocol. For the MU-CTC problem, simulation results show that REFS and EEFS can prolong the network lifetime effectively. Furthermore, EEFS outperforms against REFS in network lifetime.

Content
List of Figures . . . . . . . . . . . . . . . . . . . . .  V
List of Tables . . . . . . . . . . . . . . . . . . . .  . IX
1 Introduction . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction to WSNs . . . . . . . . . . . . . . . . . 3
1.2 Coverage Preserving in Wireless Mobile Sensor Networks . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Coverage Preserving in Wireless Heterogeneous Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Research Overview and Contributions . . . . .. . . . . 6
1.5 Organization of the Dissertation . . . . . . . . . . . 6
2 Relate Work . . . . . . . . . . . . . . . . . . . . .. . 9
2.1 Area Coverage Preserving Protocols for MSNs .. . . . . 9
2.2 Target Coverage Preserving Protocols for WSNs . . . . 11
3 Partition Avoidance in Mobile WSNs for Area Coverage. . 15
3.1 Introduction . . . .. . . . . . . . . . . . . . . . . 16
3.2 PALM: The Protocol . .  . . . . . . . . . . . . . . . 17
3.2.1 Network Model and Assumptions . . . . . . . . . . . 17
3.2.2 Problem Statement . . . . . . . . . . . . . . . . . 19
3.2.3 Lazy Movement Policy (When to move?) . . . .  . . . 20
3.2.4 Principles of an Effective Movement (Where to move?) . . . . . . .. .. . .. .  . . .. . . . . . .. . . . . . . 25
3.2.4.1 Attached Sensors Discovery . . .  . . . . . . . . 26
3.2.4.2 Target Position Calculation . . . . . . . . . . . 31
3.3 Performance Evaluations . . . . . . . . . . . . . . . 43
3.3.1 Simulation Environment . . . . . .  . . . . . . . . 43
3.3.2 Simulation Results . . . . . . . .  . . . . . . . . 43
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . 48
4 Sensor Activity Scheduling in WSNs for Target Coverage .49
4.1 Introduction . . .. . . . . . . . . . . . . . . . . . 50
4.2 Problem Statements and Formulations . . . . . . . . . 53
4.2.1 Assumptions . . . . . . . . . . . . . . . . . . . . 53
4.2.2 The MU-CSC Problem .  . . . . . . . . . . . . . . . 54
4.2.3 ILP Constraints for the MU-CSC Problem .  . . . . . 57
4.3 Distributed Schemes for the MU-CTC Problem  . . . . . 59
4.3.1 A Generic Approach to MU-CTC Problem . .  . . . . . 61
4.3.2 Remaining Energy First Scheme (REFS) . .  . . . . . 62
4.3.2.1 Set Wn . . . . . . . . . . . . . . . . . . . .. . 62
4.3.2.2 Countdown Wn . . . . . . . . . . . . . . . . .. . 63
4.3.2.3 Remove Incapable Sensing Responsibilities . . . . 63
4.3.2.4 Select the Relay . . . . . . . . . . . . . . .  . 64
4.3.2.5 Broadcast My Decision . . . . . . . . . . . . . . 64
4.3.2.6 Summary . . . . . . . . . . . . . . . . . . . . . 64
4.3.3 Energy Efficient First Scheme (EEFS) . . . . . .  . 65
4.3.3.1 Set Wn . . . . . . . . . . . . . . . . . . . .  . 65
4.3.3.2 Countdown Wn . . . . . . . . . . . . . . .  . . . 70
4.3.3.3 Remove Incapable or Redundant Sensing Responsibil-
ities . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3.3.4 Select the Relay . . . . . . . . . . . . .  . . . 72
4.3.3.5 Broadcast My Decision . . . . . . . . . . . . . . 72
4.3.3.6 Summary . . . . . . . . . . . . . . . . . . . . . 72
4.4 Performance Evaluations . . . . . . . . . . . . . . . 73
4.4.1 The Impact of tho . . . . . . . . . . . . . . . . . 76
4.4.2 Performance Evaluations of the Proposed Schemes . . 77
4.4.2.1 Energy Consumption Taken from a Snapshot . . . .  77
4.4.2.2 Energy Consumption and Remaining Energy in a Run  78
4.4.2.3 The Impacts of the Numbers of Sensors, Targets, and
Attributes on Network Lifetime . . . . . . . . .. .  . .  81
4.4.2.4 Comprehensive Comparisons of REFS and EEFS . .  . 83
4.4.3 Simulation Summary . . . . . . . . . . . . . . .  . 85
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . 85
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . 87
5.1 Contributions . . . . . . . . . . . . . . . . . . . . 87
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . 88
Bibliography  . . . . . . . . . . . . . . . . . . . . . . 91

List of Figures
3.1 (a) The shadow area is the possible location of the promising upstream sensor of si. (b) The promising zone of si, Zp(si). . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Principles of an effective movement: (a) Attached Sensors Discovery (b) Target position calculation. . . .  27
3.3 The definition of Zd: (a) the length of Zd is 2×rc (b) the height of Zd is rc. . . . . . . . . . . . . . . . . . 30
3.4 popt is the best location for sR to attach to the attached sensors. . . . . . . . . . . . . . . . . . . . . 32
3.5 Cases of the angle of p1p0xp2: (a) p1pxp2 < 180_ (b) p1pxp2 _ 180_. . . . . . . . . . . . . . . . . . . . . .  34
3.6 The examples of (a) only one uncovered arc from p−d T,lp+A,r, (b) several uncovered arcs divided from p−d T,lp+A,r. . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 (a) the segment of si’s perimeter covered by sj [40] (b) determining the uncovered arc of si’s circumference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.8 Simulation results: number of effective sensors. . .  44
3.9 Simulation results: number of lived sensors. . .  . . 45
3.10 Simulation results: number of movements. . . . . . . 46
3.11 Simulation results: accumulated distance of movements47
3.12 Simulation results: effective network coverage. . . .47
3.13 Simulation results: remaining energy of the effective sensors. . . . . . . . . . . . . . . . . . . . . . . .  . 48
4.1 An illustrated example, where 5 sensors are scheduled to cover 2 targets. (a) The topology. (b) The coverage and connectivity relationships. (c) An illustration of a connected set cover. . . . . . . . . .. . . . . . . . . . 55
4.2 Time structure of sensors: time is divided into rounds of equal length. A round consists of an initial phase and a working phase. . . . . . . . . . . . . . . . . .  . . . . 60
4.3 (a) The forwarding zone of sn, F(sn). (b) The relaying zone of sn, R(sn).. . . . . . . . . . . . . . . . . . ..  68
4.4 The impact of _ on the network lifetime for (a) scenario 1 and (b) scenario 2. . . . . . . . . . . . .  . 77
4.5 The snapshots of the remaining energy of sensors by (a) REFS and (b) EEFS in scenario 1 and (c) REFS and (d) EEFS in scenario 2, where the snapshots are taken from the end of the 27th round in scenario 1 and are taken from the 3800th minute in scenario 2. . . . . . .. . . . . . . . . 79
4.6 Energy consumption and the remaining energy in each round for some run. (a) The energy consumption and (b) the remaining energy in each round for some run in scenario 1. (c) The energy consumption and (d) the remaining energy in each round for some run in scenario 2. . . .. . . . . .   80
4.7 The impacts of the numbers of (a) sensors, (b) targets, and (c) attributes in scenario 1 as well as (d) sensors, (e) targets, and (f) attributes in scenario 2 on the network lifetime. . . . . . . . . . . . . . . . . . . . . 82
4.8 Comprehensive comparisons of REFS and EEFS. The impact of the numbers of sensors and targets on the network lifetime in terms of (a) REFS and (b) EEFS in scenario 1 as well as (c) REFS and (d) EEFS in scenario 2. . . . . .  . 84

List of Tables
2.1 Summary of Related work employing the sensor movement to preserving effective coverage of WSNs. . . . . . . . . 11
2.2 Summary of Related work employing the sensor activity scheduling to preserving effective coverage of WSNs. . . .14
4.1 Simulation setting for MU-CTC problem . . . . . . . . 74
4.2 Energy consumption model for MU-CTC problem when control and computation overheads are considered. . . . . 75

[1] ILOG CPLEX. 
[2] N. Ahmed, S. S. Kanhere, and S. Jha. The holes problem in wireless sensor networks: A survey. ACM SIGMOBILE Mobile Computing and Communications Review, 9(2):4–18, April 2005. 
[3] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer Networks, 38(4):393–422, March 2002. 
[4] M. Cardei andJ. Wu, M. Lu, and M. O. Pervaiz. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), volume 3, pages 438–445, August 2005. 
[5] F. Aurenhammer. Voronoi diagrams–a survey of a fundamental geometric data structure. ACM Computing Survey, 23(3):345–405, September 1991. 
[6] C. Avin and C. Brito. Efficient and robust query processing in dynamic environments using random walk techniques. In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), pages 277– 286, 2004. 
[7] P. Bahl and V. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, pages 775– 784, March 2000. 
[8] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DialM’99), pages 48–55, 1999. 
[9] A. Boukerche, X. Cheng, and J. Linus. Energy-aware data-centric routing in micresensor networks. pages 42–49, 2003. 
[10] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine, 7(5):28–34, October 2000. 
[11] E. H. Callaway. Wireless Sensor Networks: Architectures and Protocols. Auerbach Publications, 2003. 
[12] Q. Cao, T. Abdelzaher, T. He, and J. Stankovic. Towards optimal sleep scheduling in sensor networks for rare-event detection. In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), April 2005. 
[13] B. Carbunar, A. Grama, J. Vitek, and O. Carbunar. Coverage preserving redundancy elimination in sensor networks. In Proceedings of the IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), pages 377–386, 2004. 
[14] I. Cardei. Energy-efficient target coverage in heterogeneous wireless sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), pages 397–406, October 2006. 
[15] M. Cardei and D.-Z. Du. Improving wireless sensor network lifetime through power aware organization. ACM Wireless Networks, 11(3):333–340, May 2005. 
[16] M. Cardei, M. T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1976–1984, March 2005. 
[17] M. Cardei, M. T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1976–1984, March 2005. 
[18] A. Caruso, A. Urpi, S. Clessa, and S. De. GPS free coordinate assignment and routing in wireless sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 150–160, March 2005. 
[19] A. Cerpa and D. Estrin. ASCENT: Adaptive self-configuring sensor networks topologies. IEEE Journal on Selected Areas in Communications, 17(8):1506– 1531, August 1999. 
[20] Crossbow. MPR/MIB Mote Hardware Users Manual. Crossbow website, 2003. 
[21] K. Dasgupta, K. Kalpakis, and P. Namjoshi. An efficient clustering-based heuristic for data gathering and aggregation in sensor networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pages 1948–1953, March 2003. 
[22] M. Ding, D. Chen, A. Thaeler, and X. Cheng. Fault-tolerant target detection in sensor networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), volume 4, pages 2362–2368, March 2005. 
[23] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next century challenges: Scalable coordination in sensor networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 263–270, August 1999. 
[24] Q. Fang, J. Gao, and L. J. Guibas. Locating and bypassing routing holes in sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2458– 2468, March 2004. 
[25] J. Ford. Telecommunications with MEMS devices: An overview. The 14th Annual Meeting of the IEEE lasers and Electro-Optics society, 2(12):415–416, November 2001. 
[26] S. Ganeriwal, A. Kansal, and M.B. Srivastava. Self aware actuation for fault repair in sensor networks. In Proceedings of the 2004 IEEE International Conference on Robotics and Automation(ICRA), volume 5, pages 5244–5249, May 2004. 
[27] D. Ganesan, A. Cerpa, W. Ye, Y. Yu, J. Zhao, and D. Estrin. Networking issues in wireless sensor networks. Journal of Parallel and Distributed Computing (JPDC), 64(7):799–814, 2004. 
[28] A. Ghosh and T. Givargis. LORD: A localized, reactive and distributed protocol for node scheduling in wireless sensor networks. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibitation (DATE), volume 1, pages 190–195, 2005. 
[29] C. Gui and P. Mohapatra. Virtual patrol: A new power conservation design for suveillance using sensor networks. In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), pages 246– 253, April 2005. 
[30] H. Gupta, S. R. Das, and Q. Gu. Connected sensor cover: Self-organization of sensor networks for efficient query execution. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 189–200, 2003. 
[31] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 81–95, 2003. 
[32] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of Hawaii Conference on System Sciences (HICSS), January 2000. 
[33] N. Heo and P. K. Varshney. A distributed self spreading algorithm for mobile wireless sensor networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), volume 3, pages 1597–1602, March 2003. 
[34] N. Heo and P. K. Varshney. An intelligent deployment and clustering algorithm for distributed mobile sensor networks. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, volume 5, pages 4576–4581, October 2003. 
[35] N. Heo and P. K. Varshney. Energy-efficient deployment of intelligent mobile sensor networks. IEEE Transactions on Systems, Man, and Cybernetics–Part A: Systems and Humans, 35(1):78–92, January 2005. 
[36] M. Hollick, I. Martinovic, T. Krop, and I. Rimac. A survey on dependable routing in sensor networks, ad hoc networks, and cellular networks. In Proceedings of the IEEE Euromicro Conference, pages 495–502, August 2004. 
[37] C. F. Hsin and M. Liu. Network coverage using low duty-cycled sensors: Random & coordinated sleep algorithms. In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), pages 433–442, April 2004. 
[38] C.-F. Huang, L.-C. Lo, Y.-C. Tseng, and W.-T. Chen. Decentralized energyconserving and coverage-preserving protocols for wireless sensor networks. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), 2005. 
[39] C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2003. 
[40] C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. ACM Mobile Networks and Applications (MONET), 10(4):519–528, August 2005. 
[41] Q. Huang, C. Lu, and G.-C. Roman. Reliable mobicast via face-aware routing. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 2108–2118, March 2004. 
[42] C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 56–67, 2000. 
[43] R. Iyengar and B. Sikdar. Scalable and distributed gps free positioning for sensor networks. In Proceedings of the IEEE International Conference on Communications (ICC), volume 1, pages 338–342, May 2003. 
[44] J. Jiang and W. Dou. A coverage-preserving node scheduling algorithm for self- organized wireless sensor networks. In Proceedings of the Grid and Cooperative Computing Workshops (GCC), pages 587–596, 2004. 
[45] J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: Mobile networking for smart dust. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 263–270,March 1999. 
[46] K. Kalpakis, K. Dasgupta, and P. Namjoshi. Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. The International Journal of Computer and Telecommunications Networking, 42:697–716, August 2003. 
[47] K. Kar and S. Banerjee. Node placement for connected coverage in sensor networks. In Proceedings of the First Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), March 2003. 
[48] B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 243–254, 2000. 
[49] B. Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 243–254, August 2000. 
[50] S. Kim, S. H. Son, J. A. Stankovic, S. Li, and Y. Choi. SAFE: A data dissemination protocol for periodic updates in sensor networks. In Proceedings of the IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW), pages 228–234, 2003. 
[51] Y. B. Ko and N. H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. Wireless Networks, 6(4):307–321, July 2000. 
[52] S. Kumar, T. H. Lai, and J. Balogh. On k-coverage in a mostly sleeping sensor network. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 144–158, 2004. 
[53] Q. Li, M. D. Rosa, and D. Rus. Distributed algorithms for guiding navigation across a sensor network. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 313–325, September 2003. 
[54] H. Liu, X. Jia, P. J. Wan, C. W. Yi, S. K. Makki, and N. Pissinou. Maximizing lifetime of sensor surveillance systems. IEEE/ACM Transactions on Networking, 15(2):334–345, April 2007. 
[55] H. Liu, P. Wan, and X. Jia. Maximal lifetime scheduling for sensor surveillance systems with k sensors to one target. IEEE Transactions on Parallel and Distributed Systems, 17(12):1–11, December 2006. 
[56] H. Liu, P. Wan, C.-W. Yi, X. Jia, S. Makki, and N. Pissinou. Maximal lifetime scheduling in sensor surveillance networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2482–2491, March 2005. 
[57] S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Worst and best-case coverage in sensor networks. IEEE Transactions on Mobile Computing, 4(1):84–92, Jan./Feb. 2005. 
[58] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1380–1387, April 2001. 
[59] Y. Mei, Y.-H Lu, Y. C. Hu, and C. S. G. Lee. Energy-efficient motion planning for mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), volume 5, pages 4344–4349, May 2004. 
[60] A. Nasipuri and K. Li. A directionality based location discovery scheme for wireless sensor networks. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), pages 105–111, September 2002. 
[61] J. Newsome and D. Song. GEM: Graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), pages 76–88, 2003. 
[62] J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen. Topology control for wireless sensor networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 286–299, September 2003. 
[63] G. J. Pottie and W. J. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):51–58, May 2000. 
[64] K. Premaratne, J. Zhang, and M. Dogruel. Localization information-aided task- oriented self-organization of ad-hoc sensor networks. IEEE Sensor Journal, 4(1):85–95, February 2004. 
[65] L. B. Ruiz, J. M. Nogueira, and A. A. F. Loureiro. MANNA: A management architecture for wireless sensor networks. IEEE Communications Magazine, 41(2):116–125, February 2003. 
[66] N. Sadagopan, B. Krishnamachari, and A. Helmy. The ACQUIRE mechanism for efficient querying in sensor networks. In Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications (SNPA), pages 149– 155, 2003. 
[67] H. O. Sanli, R. Poornachandran, and H. C¸ am. Collaborative two-level task scheduling for wireless sensor nodes with multiple sensing units. In Proceedings of the IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), pages 350–361, September 2005. 
[68] C. Schurgers, V. Tsiatsis, and M. B. Srivastava. STEM: Topology management for energy efficient sensor networks. In Proceedings of IEEE Aerospace Conference, pages 1099–1108, 2002. 
[69] Karim Seada, Ahmed Helmy, and Ramesh Govindan. Modeling and analyzing the correctness of geographic face routing under realistic conditions. Ad Hoc Networks, 5(6):855–871, 2007. 
[70] K. P. Shih, Y. D. Chen, C. W. Chiang, and B. J. Liu. A distributed active sensor selection scheme for wireless sensor networks. In Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), June 2006. 
[71] K. P. Shih, S. S. Wang, P. H. Yang, and C. C. Chang. CollECT: Collaborative event detection and tracking in wireless heterogeneous sensor networks. In Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), June 2006. 
[72] K. P. Shih, S. Y. Wang, H. C. Chen, and B. J. Liu. On target coverage in wireless heterogeneous sensor networks with multiple sensing units. In Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), July 2007. 
[73] A. Sinha and A. Chandrakasan. Dynamic power management in wireless sensor networks. IEEE Design and Test of Computers, 18(2):62–74, March 2001. 
[74] S. Tialk, N. Abu-Ghazaleh, and W. Heinzelman. A taxonomy of wireless microsensor network models. ACM SIGMOBILE Mobile Computing and Communications Review, 6(2):28–36, April 2002. 
[75] D. Tian and N. D. Georganas. A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), pages 32– 41, 2002. 
[76] M. A. M. Vieira, C. N. Coelho Jr., D. C. da Silva Jr., and J. M. da Mata. Survey on wireless sensor network devices. In Proceedings of the IEEE Conference on Emergy Technologies and Factory Automation (ETFA), pages 537–554, September 2003. 
[77] G. Wang, G. Cao, and T. L. Porta. Movement-assisted sensor deployment. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2469–2479, March 2004. 
[78] G.Wang, G. Cao, T. L. Porta, and W. Zhang. Sensor relocation in mobile sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2302– 2312, March 2005. 
[79] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivity configuration in wireless sensor networks. In Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), pages 28–39, 2003. 
[80] Y.-C. Wang, C.-C. Hu, and Y.-C. Tseng. Efficient placement and dispatch of sensors in a wireless sensor network. IEEE Transactions on Mobile Computing, to appear. 
[81] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides. On the construction of energy-efficeint broadcast and multicast trees in wireless networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, pages 585–594, June 2000. 
[82] J.Wu and S. Yang. SMART: A scan-based movement assisted sensor deployment method in wireless sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 18, pages 1108–1121, March 2005. 
[83] K. Xing, X. Cheng, and J. Li. Location-centric storage for sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), pages 492–501, November 2005. 
[84] Y. Xu and W.-C. Lee. On localized prediction for power efficient object tracking in sensor networks. In Proceedings of the IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW), pages 434–439, March 2003. 
[85] T. Yan, T. He, and J. A. Stankovic. Differentiated surveillance for sensor networks. In Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), pages 51–62, 2003. 
[86] H. Yang and B. Sikdar. A protocol for tracking mobile targets using sensor networks. In Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications(SNPA), pages 71–81, May 2003. 
[87] S. Yang, F Dai, M. Cardei, and J. Wu. On multiple point coverage in wireless sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), pages 757–764, November 2005. 
[88] C. K. Yap. An O(nlogn) algorithm for the voronoi diagram of a set of simple curve segments. Discrete and Computational Geometry, 2:365–393, 1987. 
[89] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. A two-tier data dissemination model for large scale wireless sensor networks. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 148–159, September 2002. 
[90] F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang. PEAS: A robust energy conserving protocol for long-lived sensor networks. In Proceedings of the 23th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 28– 37, May 2003. 
[91] W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1567–1576, 2002. 
[92] W. Ye, J. Heidemann, and D. Estrin. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM Transactions of Networking, 12(3):493–506, June 2004. 
[93] H. Zhang and J.C. Hou. Maintaining sensing coverage and connectivity in large sensor networks. In Proceedings of the NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004. 
[94] H. Zhang and J.C. Hou. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks, 1:89–124, March 2005. 
[95] Q. Zhao and M. Gurusamy. Maximizing network lifetime for connected target coverage in wireless sensor networks. In Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), pages 94–101, June 2006.