摘要
无线传感器网络通常是由一组小体积、低功率且具有无线通信能力的传感器设备所构成的无线多跳网络,有机地结合了分布式信息收集、计算处理及无线通信技术,具有数据中心、面向应用及资源约束等特征,拥有广阔的应用前景,同时也提出了许多挑战。由于无线传感器节点能源的苛刻限制,节能是无线传感器网络中最大的挑战之一,对无线传感器网络设计的各个方面都产生了直接的影响。本文围绕无线传感器网络的节能策略及算法进行了研究,主要研究了单点聚合、多点聚合与多点聚合多径路由策略下最大网络生命期优化路由问题以及空间剖分策略下最小网络总能耗基站位置优化选择问题。
针对数据聚合无线传感器网络,延长网络生命期的关键在于采用数据聚合减少网络负载的同时均衡节点能耗,依赖于数据聚合策略的选择。在第二章中研究了单点聚合路由策略。在该策略中,节点选择单个邻居进行数据聚合。提出了以最小能耗生成树为基础结构的数据聚合点优化选择算法,采用遗传算法与梯度下降联合优化的方法对节点能耗进行均衡,提高网络生命期。
第三章在第二章的基础上放松了对数据聚合点选择的单一性,考虑了多点聚合路由策略,允许节点将原始数据分发到各相邻节点进行数据聚合。提出了基于最小能耗生成森林的原始数据分配算法,采用线性规划的方法优化节点对原始数据流的分配。应用次梯度方法设计了相应的分布式算法,通过节点间的数据交换与计算实现原始数据流的优化分配。
第四章在第三章的基础上进一步放松对聚合数据传输路径的单径约束,考虑了多点聚合多径路由策略,允许聚合数据通过多条路径进行传输。设计了基于线性规划的路由算法获得最大网络生命期,对聚合数据流中的环路进行了消除。提出了聚合数据率约束下的网络生命期的优化路由算法,并对网络聚合数据率与网络生命期之间的权衡关系进行了讨论。
第五章研究无线传感器网络中以节能为目标的基站位置优化选择问题。依据网络总能耗目标函数的分段光滑性,提出了基于最短路径树的空间剖分策略对问题进行分治,将空间划分为若干剖分单元,节能路由在各剖分单元中具有不变性。讨论了剖分单元的结构及相邻剖分单元的搜索算法,给出了一维空间中的基站位置优选算法,并为二维空间的情形提出了三种启发式算法以获得性能优良的基站位置。
最后,第六章对全文进行总结,归纳了文本研究工作的重点,并对未来的研究方向与热点问题作出了展望。
Wireless sensor networks are multi-hop wireless networks, which usually consist of small-sized and low-power sensing devices with wireless communications capabilities. They efficiently combine the technologies in distributed information sensing, processing and wireless communications. Wireless sensor networks are characterised by data centric, application orientation and resource constraints, which lend themselves to countless applications and, at the same time, offer numerous challenges. Due to the stringent energy constraints to which the sensing nodes are subjected, energy efficiency is one the greatest challenges offered by wireless sensor networks, and poses direct impacts on their designs. This dissertation studies the energy reserving strategies and algorithms in wireless sensor networks, which focuses upon the design of the maximum network lifetime routing problems under single-point, multi-point and multi- point-multi-path aggregation routing strageties, and the optimal sink position selection problems under space tessellation strageties that aimed at minimizing the overall network energy consumption.
In data aggregated wireless sensor networks, the key to prolong network lifetime is to utilize data aggregation to reduce the network load while balance the energy consumption for the sensors, which depends on the selection of data aggregation strategies. In chapter 2, the single-point aggregation routing strategy is studied. In this strategy, each sensor selects a single aggregator for data aggregation. An optimal aggregator selection algorithm based on the minimum energy cost tree is proposed, which combines the optimization power of genetic algorithm and gradient hill-climbing method. The energy consumption of the sensors is balanced, and the network lifetime is improved.
Following chapter 2, chapter 3 relaxes the singularity on the selection of aggregators, and considers the multi-point aggregation routing strategy. In this strategy, sensors are allowed to distribute their raw data to every neighboring sensor for data aggregation. A raw data distribution algorithm based on minimum energy cost forest is presented, and linear programming method is used to optimize the allocation of raw data. Subgradient method is adopted to design the distributed algorithm, and the optimization of the raw data distribution is achieved by inter-node data exchange and computations.
Chapter 4 further relaxes the single path constraint for the transmission of aggregated data from chapter 3, and studies the multi-point aggregation multi-path routing strategy. In the strategy, aggregated data are forward via multiple paths. A routing algorithm is designed based on linear programming method, the maximum network lifetime is obtained, and the possible loops in aggregated data flow are eliminated. A routing algorithm is designed to optimize network lifetime under aggregated data rate constraint, and the tradeoffs between network aggregated data rate and network lifetime are discussed.
Chapter 5 studies the minimum energy sink position selection problems in wireless sensor networks. According to the piecewise smoothness of the overall network energy consumption objective function, a space tessellation strategy based on shortest path tree is proposed to divide and conquer the problem. In the strategy, the space is divided into tessellation cells, and each cell offers invariability for minimum energy routing. The structure of the tessellation cells and an algorithm for searching neighboring cells are discussed. An optimal sink selection algorithm for 1-D space is given; and three heuristic algorithms are presented for 2-D space, which are able to obtain sink positions with good performance.
Finally, chapter 6 summarizes the dissertation, concludes the highlights in the studies, and presents the outlooks of directions and hotspots for future work.
引文
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, et al. A Survey on Sensor Networks. IEEE Communications Magazine, Aug. 2002, 40(8): 102–114.
[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, et al. Wireless Sensor Networks: A Survey. Computer Networks, 2002, 38(4): 393–422.
[3] I. F. Akyildiz, I. H. Kasimoglu. Wireless Sensor and Actor Networks: Research Challenges. Ad Hoc Networks, 2004, 2(4): 351–367.
[4] M. Weiser. Hot Topics—Ubiquitous Computing. Computer, Oct. 1993, 26(10): 71–72.
[5] M. Weiser. The Computer for the 21st Century. IEEE Pervasive Computing, Jan. 2002, 99(1): 19–25.
[6] R. Szewczyk, A. Mainwaring, J. Polastre, et al. An analysis of A Large Scale Habitat Monitoring Application. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04), Baltimore, MD, USA, Nov. 2004: 214–226.
[7] P. Zhang, C. M. Sadler, S. A. Lyon, et al. Hardware Design Experiences in ZebraNet. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04), Baltimore, MD, USA, Nov. 2004: 227–238.
[8] C. Sharp, S. Schaffert, A. Woo, et al. Design and Implementation of A Sensor Network System for Vehicle Tracking and Autonomous Interception. Proceedings of the 2nd European Workshop on Wireless Sensor Networks (EWSN’05), Istanbul, Turkey, Jan. 2005: 93–107.
[9] P. Chen, S. Oh, M. Manzo, et al. Instrumenting Wireless Sensor Networks for Real-Time Surveillance. Proceedings of IEEE International Conference on Robotics and Automation (ICRA’06), Orlando, FL, USA, May 2006: 3128–3133.
[10] K. Selvarajah, A. Tully, P. T. Blythe. ZigBee for Intelligent Transport System Applications. Proceedings of IET Road Transport Information and Control (RTIC’08), Manchester, UK, May 2008: 1–7.
[11] R. Li, L. Jia. On The Layout of Fixed Urban Traffic Detectors: An Application Study. IEEEIntelligent Transportation Systems Magazine, 2009, 1(2): 6–12.
[12] O. Omeni, A. Wong, A. J. Burdett, et al. Energy Efficient Medium Access Protocol for Wireless Medical Body Area Sensor Networks. IEEE Transactions on Biomedical Circuits and Systems, Dec. 2008, 2(4): 251–259.
[13] S. L. Chen, H. Y. Lee, C. A. Chen, et al. Wireless Body Sensor Network With Adaptive Low-Power Design for Biometrics and Healthcare Applications. IEEE Systems Journal, Dec. 2009, 3(4): 398–409.
[14] V. C. Gungor, G. P. Hancke. Industrial Wireless Sensor Networks: Challenges, Design Principles, and Technical Approaches. IEEE Transactions on Industrial Electronics, Oct. 2009, 56(10): 4258–4265.
[15] F. Salvadori, M. de Campos, P. S. Sausen, et al. Monitoring in Industrial Systems Using Wireless Sensor Network with Dynamic Power Management. IEEE Transactions on Instrumentation and Measurement, Sep. 2009, 58(9): 3104–3111.
[16] C. E. Nishimura, D. M. Conlon. IUSS Dual Use: Monitoring Whales and Earthquakes Using SOSUS. Marine Technology Society Journal, 1994, 27(4): 13–21.
[17] C. J. Bryan, C. E. Nishimura. Monitoring Ocean Earthquakes with SOSUS: An Example from the Caribbean. The Oceanography Society Magazine, 1995, 8(1): 4–10.
[18] R. Lacoss, R. Walton. Strawman Design for A DSN to Detect and Track Low Flying Aircraft. Proceedings of Distributed Sensor Nets Workshop, Pittsburgh, PA, USA, Dec. 1978: 41–52.
[19] Y. C. Cheng, T. G. Robertazzi. Communication and Computation Tradeoffs for A Network of Intelligent Sensors. Proceedings of Computer Networking Symposium, Apr. 1988: 152–161.
[20] R. F. Rashid, G. G. Robertson. Accent: A Communication Oriented Network Operating System Kernel. Proceedings of 8th ACM Symposium on Operating Systems Principles (SOSP’81), Pacific Grove, CA, USA, Dec. 1981: 64–75.
[21] R. Rashid, D. Julin, D. Orr, et al. Mach: A System Software Kernel. Proceedings of 34th IEEE Computer Society International Conference (COMPCON’89 Spring), San Francisco, CA, USA, Mar. 1989: 176–178.
[22] C. Myers, A. Oppenheim, R. Davis, et al. Knowledge-Based Speech Analysis andEnhancement. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’84), San Diego, CA, USA, Mar. 1984: 162–165.
[23] Y. Bar-Shalom. Multitarget-Multisensor Tracking: Advanced Applications. Norwood, MA, USA: Artech House, Jan. 1990.
[24] K. Bult, A. Burstein, D. Chang, et al. Low Power Systems for Wireless Microsensors. Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED’96), Monterey, CA, USA, Aug. 1996: 17–21.
[25] G. J. Pottie, W. J. Kaiser. Wireless Integrated Network Sensors. Communications of the ACM, May. 2000, 43(5): 51–58.
[26] S. Kumar, D. Shepherd. SensIT: Sensor Information Technology for the Warfighter. In Proceedings of the 4th International Conference on Information Fusion, Montreal, Canada, Aug. 2001, 3–9.
[27] J. M. Kahn, R. H. Katz, K. S. J. Pister. Next Century Challenges: Mobile Networking for“Smart Dust”. Proceedings of 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM’99), Seattle, WA, USA, Aug. 1999: 271–278.
[28] B. Warneke, M. Last, B. Liebowitz, et al. Smart Dust: Communicating with A Cubic-Millimeter Computer. Computer, Jan. 2001, 34(1): 44–51.
[29] B. A. Warneke, M. D. Scott, B. S. Leibowitz, et al. An Autonomous 16 mm3 Solar-Powered Node for Distributed Wireless Sensor Networks. Proceedings of the 1st IEEE International Conference on Sensors, Orlando, FL, USA, Jun. 2002: 1510–1515.
[30] J. M. Rabaey, M. J. Ammer, J. L. da Silva, et al. PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking. Computer, Jul. 2000, 33(7): 42–48.
[31] J. Polastre, R. Szewczyk, C. Sharp, et al. The Mote Revolution: Low Power Wireless Sensor Network Devices. Proceedings of the Symposium on High Performance Chips (HotChips’04), Stanford, CA, USA, Aug. 2004.
[32] M. Sheets, B. Otis, F. Burghardt, et al. A (6x3) cm2 Self-Contained Energy-Scavenging Wireless Sensor Network Node. Proceedings of the 7th International Symposium on Wireless Personal Multimedia Communications (WPMC’04), Abano Terme, Italy, Sep. 2004.
[33] P. Levis, D. Culler. Maté: A Tiny Virtual Machine for Sensor Networks. Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X), San Jose, CA, USA, Oct. 2002: 85–95.
[34] P. Levis, N. Lee, M. Welsh, et al. TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys’03), Los Angeles, CA, USA, Nov. 2003: 126–137.
[35] P. Levis, S. Madden, D. Gay, et al. The Emergence of Networking Abstractions and Techniques in TinyOS. Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation (NSDI’04), San Francisco, CA, USA, Mar. 2004: 1–14.
[36] A. Woo, D. E. Culler. A Transmission Control Scheme for Media Access in Sensor Networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01), Rome, Italy, Jul. 2001: 221–235.
[37] A. Perrig, R. Szewczyk, V. Wen, et al. SPINS: Security Protocols for Sensor Networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01), Rome, Italy, Jul. 2001: 189–199.
[38] A. Perrig, R. Szewczyk, J. D. Tygar, et al. SPINS: Security Protocols for Sensor Networks. Wireless Networks, Sep. 2002, 8(5): 521–534.
[39] W. R. Heinzelman, A. Sinha, A. Wang, et al. Energy-Scalable Algorithms and Protocols for Wireless Microsensor Networks. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’00), 2000: 3722–3725.
[40] W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan. Energy Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS’00), Maui, Hawaii, USA, Jan. 2000: 3005–3014.
[41] W. B. Heinzelman, A. P. Chandrakasan, H. Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, Oct. 2002, 1(4): 660–670.
[42] A. Chandrakasan, R. Amirtharajah, S. Cho, et al. Design Considerations for Distributed Microsensor Systems. Proceedings of the IEEE 1999 Custom Integrated Circuits (CICC’99), San Diego, CA, USA, May 1999: 279–286.
[43] B. H. Calhoun, D. C. Daly, N. Verma, et al. Design Considerations for Ultra-Low Energy Wireless Microsensor Nodes. IEEE Transactions on Computers, Jun. 2005, 54(6): 727–740.
[44] E. Y. Song, K. Lee. Understanding IEEE 1451―Networked Smart Transducer Interface Standard. IEEE Instrumentation Measurement Magazine, Apr. 2008, 11(2): 11–17.
[45] T. M. Siep, I. C. Gifford, R. C. Braley, et al. Paving the Way for Personal Area Network Standards: An Overview of the IEEE P802.15 Working Group for Wireless Personal Area Networks. IEEE Personal Communications, Feb. 2000, 7(1): 37–43.
[46] J. Heo, J. Kim, J. Seo, et al. A Study on the Implementation of A Wireless Ad-Hoc Sensor Network Based on the IEEE 1451.5. Proceedings of the 9th International Conference on Advanced Communication Technology (ICACT’07), Phoenix Park, Republic of Korea, Feb. 2007: 419–422.
[47] P. Johansson, M. Kazantzidis, R. Kapoor, et al. Bluetooth: An Enabler for Personal Area Networking. IEEE Network, Sep. 2001, 15(5): 28–37.
[48] J. Karaoguz. High-Rate Wireless Personal Area Networks. IEEE Communications Magazine, Dec. 2001, 39(12): 96–102.
[49] S. Mahmud, S. Khan, Raweshidy. H. Al, et al. Meshed High Data Rate Personal Area Networks. IEEE Communications Surveys Tutorials, 2008, 10(1): 58–69.
[50] J. A. Gutierrez, M. Naeve, E. Callaway, et al. IEEE 802.15.4: A Developing Standard for Low-Power Low-Cost Wireless Personal Area Networks. IEEE Network, Sep. 2001, 15(5): 12–19.
[51] E. Callaway, P. Gorday, L. Hester, et al. Home networking with IEEE 802.15.4: A Developing Standard for Low-Rate Wireless Personal Area Networks. IEEE Communications Magazine, Aug. 2002, 40(8): 70–77.
[52] J. Gutierrez, E. Callaway, R. Barrett. Low-Rate Wireless Personal Area Networks: Enabling Wireless Sensors with IEEE 802.15.4. New York, NY, USA: IEEE Press, 2004.
[53] M. Kohvakka, M. Kuorilehto, M. H?nnik?inen, et al. Performance Analysis of IEEE 802.15.4 and ZigBee for Large-Scale Wireless Sensor Network Applications. Proceedings of the 3rd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor and Ubiquitous Networks (PE-WASUN’06), Terromolinos, Spain, Oct. 2006: 48–57.
[54] C. Evans-Pughe. Bzzzz zzz. IEE Review, Mar. 2003, 49(3): 28–31.
[55] A. Wheeler. Commercial Applications of Wireless Sensor Networks Using ZigBee. IEEE Communications Magazine, Apr. 2007, 45(4): 70–77.
[56] F. Reynolds. Whither Bluetooth?. IEEE Pervasive Computing, Jul. 2008, 7(3): 6–8.
[57] H. Cao, V. Leung, C. Chow, et al. Enabling Technologies for Wireless Body Area Networks: A Survey and Outlook. IEEE Communications Magazine, Dec. 2009, 47(12): 84–93.
[58] L. M. Ni, Y. Liu, Y. Zhu. China’s National Research Project on Wireless Sensor Networks. IEEE Wireless Communications, Dec. 2007, 14(6): 78–83.
[59] W. Jiang, Y. Chen, Y. Shi, et al. The Design and Implementation of the Cicada Wireless Sensor Network Indoor Localization System. Proceedings of the 16th International Conference on Artificial Reality and Telexistence (ICAT’06), Hangzhou, Zhejiang, China, Nov. 2006: 536–541.
[60] H. Gu, Y. Shi, Y. Chen, et al. Cicada: A Highly-Precise Easy-Embedded and Omni-Directional Indoor Location Sensing System. Proceedings of First International Conference on Grid and Pervasive Computing (GPC’06), Taichung, Taiwan, May 2006: 385–394.
[61] Z. Pei, Z. Deng, B. Yang, et al. Application-Oriented Wireless Sensor Network Communication Protocols and Hardware Platforms: A Survey. Proceedings of IEEE International Conference on Industrial Technology (ICIT’08), Apr. 2008: 1–6.
[62] V. Raghunathan, C. Schurgers, S. Park, et al. Energy-Aware Wireless Microsensor Networks. IEEE Signal Processing Magazine, Mar. 2002, 19(2): 40–50.
[63] M. Kohvakka, M. Hannikainen, T. D. Hamalainen. Wireless Sensor Prototype Platform. Proceedings of the 29th Annual Conference of the IEEE Industrial Electronics Society (IECON’03), Roanoke, VA, USA, Nov. 2003: 1499–1504.
[64] N. A. Pantazis, D. D. Vergados. A Survey on Power Control Issues in Wireless Sensor Networks. IEEE Communications Surveys Tutorials, 2007, 9(4): 86–107.
[65] J. Polastre, R. Szewczyk, D. Culler. Telos: Enabling Ultra-Low Power Wireless Research. Proceedings of the 4th International Symposium on Information Processing in SensorNetworks (IPSN’05), Piscataway, NJ, USA, 2005: 1–6.
[66] H. Dubois-Ferriere, R. Meier, L. Fabre, et al. TinyNode: A Comprehensive Platform for Wireless Sensor Network Applications. Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN’06), Nashville, TN, USA, Apr. 2006: 358–365.
[67] M. Wolf, D. Kress. Short-Range Wireless Infrared Transmission: the Link Buoget Compared to RF. IEEE Wireless Communications, Apr. 2003, 10(2): 8–14.
[68] J. M. Kahn, J. R. Barry. Wireless Infrared Communications. Proceedings of the IEEE, Feb. 1997, 85(2): 265–298.
[69] L. Doherty, B. A. Warneke, B. E. Boser, et al. Energy and Performance Considerations for Smart Dust. International Journal of Parallel and Distributed Systems and Networks, 2001, 4(3): 121–133.
[70] S. Park, A. Savvides, M. Srivastava. Battery Capacity Measurement and Analysis Using Lithium Coin Cell Battery. Proceedings of the 2001 International Symposium on Low Power Electronics and Design (ISLPED’01), Huntington Beach, CA, USA, Aug. 2001: 382–387.
[71] K. Lahiri, S. Dey, D. Panigrahi, et al. Battery-Driven System Design: A New Frontier in Low Power Design. Proceedings of the 2002 Asia and South Pacific Design Automation Conference (ASP-DAC’02), Washington, DC, USA, Jan. 2002.
[72] S. Roundy, D. Steingart, L. Frechette, et al. Power Sources for Wireless Sensor Networks. Proceedings of the 1st European Workshop on Wireless Sensor Networks (EWSN’04), Berlin, Germany, Jan. 2004: 1–17.
[73] K. R?mer, O. Kasten, F. Mattern. Middleware Challenges for Wireless Sensor Networks. ACM SIGMOBILE Mobile Computing and Communications Review, Oct. 2002, 6(4): 59–61.
[74] C. S. Raghavendra, K. M. Sivalingam, T. Znati. (Eds.). Wireless Sensor Networks. Norwell, MA, USA: Springer US, 2004.
[75] J. A. Stankovic, T. E. Abdelzaher, C. Lu, et al. Real-Time Communication and Coordination in Embedded Sensor Networks. Proceedings of the IEEE, Jul. 2003, 91(7): 1002–1022.
[76] H. Karl, A. Willig. Protocols and Architectures for Wireless Sensor Networks. Chichester,West Sussex, UK: Wiley, Jun. 2005.
[77] J. Hill, R. Szewczyk, A. Woo, et al. System Architecture Directions for Networked Sensors. Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), Cambridge, MA, United States, Nov. 2000: 93–104.
[78] C. C. Han, R. Kumar, R. Shea, et al. A Dynamic Operating System for Sensor Nodes. Proceedings of the 3rd International Conference on Mobile Systems, Applications, and Services (MobiSys’05), Seattle, WA, USA, Jun. 2005: 163–176.
[79] X. Wu, G. Chen, S. K. Das. Avoiding Energy Holes in Wireless Sensor Networks with Nonuniform Node Distribution. IEEE Transactions on Parallel and Distributed Systems, May 2008, 19(5): 710–720.
[80] H. M. Ammari, S. K. Das. Promoting Heterogeneity, Mobility, and Energy-Aware Voronoi Diagram in Wireless Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, Jul. 2008, 19(7): 995–1008.
[81] E. F. Nakamura, A. A. F. Loureiro, A. C. Frery. Information Fusion for Wireless Sensor Networks: Methods, Models, and Classifications. ACM Computing Surveys, Sep. 2007, 39(3): Article9/1–55.
[82] H. S. Carvalho, W. B. Heinzelman, A. L. Murphy, et al. A General Data Fusion Architecture. Proceedings of the 6th International Conference of Information Fusion (FUSION’03), Cairns, Queensland, Australia, Jul. 2003: 1465–1472.
[83] E. Fasolo, M. Rossi, J. Widmer, et al. In-Network Aggregation Techniques for Wireless Sensor Networks: A Survey. IEEE Wireless Communications, Apr. 2007, 14(2): 70–87.
[84] N. H. Cohen, A. Purakayastha, J. Turek, et al. Challenges in Flexible Aggregation of Pervasive Data. IBM Research Report RC 21942 (98646), IBM Research Division, Yorktown Heights, NY, USA, Jan. 2001.
[85] J. Heidemann, F. Silva, C. Intanagonwiwat, et al. Building Efficient Wireless Sensor Networks with Low-Level Naming. Proceedings of SOSP’01: Proceedings of the 18th ACM Symposium on Operating Systems Principles, Banff, Alberta, Canada, Oct. 2001: 146–159.
[86] K. Kalpakis, K. Dasgupta, P. Namjoshi. Efficient Algorithms for Maximum Lifetime DataGathering and Aggregation in Wireless Sensor Networks. Computer Networks, Aug. 2003, 42(6): 697–716.
[87] A. Boulis, S. Ganeriwal, M. B. Srivastava. Aggregation in Sensor Networks: An Energy-Accuracy Trade-Off. Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications (SNPA’03), Anchorage, AK, USA, May 2003: 128–138.
[88] W. Ye, J. Heidemann, D. Estrin. An Energy-Efficient MAC Protocol for Wireless Sensor Networks. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), New York, NY, USA, Jun. 2002: 1567–1576.
[89] M. Stemm, R. H. Katz, Y. H. Katz. Measuring and Reducing Energy Consumption of Network Interfaces in Hand-Held Devices. IEICE Transactions on Communications, Aug. 1997, E80-B(8): 1125–1131.
[90] P. Karn. MACA—A New Channel Access Method for Packet Radio. Proceedings of the 9th ARRL Computer Networking Conference, London, Ontario, Canada, Sep. 1990.
[91] V. Bharghavan, A. Demers, S. Shenker, et al. MACAW: A Media Access Protocol for Wireless LAN’s. Proceedings of the Conference on Communications Architectures, Protocols and Applications (SIGCOMM’94), London, UK, Aug. 1994: 212–225.
[92] L. Bao, J. J. Garcia-Luna-Aceves. A New Approach to Channel Access Scheduling for Ad Hoc Networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01), Rome, Italy, Jul. 2001: 210–221.
[93] V. Rajendran, K. Obraczka, J. J. Garcia-Luna-Aceves. Energy-Efficient Collision-Free Medium Access Control for Wireless Sensor Networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys’03), Los Angeles, CA, USA, Nov. 2003: 181–192.
[94] P. Jacquet, P. Muhlethaler, T. Clausen, et al. Optimized Link State Routing Protocol for Ad Hoc Networks. Proceedings of IEEE International Multi Topic Conference on Technology for the 21st Century (INMIC’01), Lahore, Pakistan, Dec. 2001: 62–68.
[95] B. Bellur, R. G. Ogier. A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks. Proceedings of the 18nth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’99), New York, NY, USA, Mar. 1999: 178–186.
[96] C. E. Perkins, E. M. Royer. Ad-Hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99), New Orleans, LA, USA, Feb. 1999: 90–100.
[97] D. B. Johnson, D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. Mobile Computing. Boston, MA, USA: Kluwer Academic Publishers, Jan. 1996: 153–181.
[98] H. Luo, G. J. Pottie. Designing Routes for Source Coding with Explicit Side Information in Sensor Networks. IEEE/ACM Transactions on Networking, Dec. 2007, 15(6): 1401–1413.
[99] P. von Rickenbach, R. Wattenhofer. Gathering Correlated Data in Sensor Networks. Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC’04), Philadelphia, PA, USA, Oct. 2004: 60–66.
[100] C. Buragohain, D. Agrawal, S. Suri. Power Aware Routing for Sensor Databases. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05), Miami, FL, USA, Mar. 2005: 1747–1757.
[101] C. Hua, T. S. Yum. Maximum Lifetime Routing and Data Aggregation for Wireless Sensor Networks. Proceedings of the 5th International IFIP-TC6 Networking Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems (Networking’06), Coimbra, Portugal, May 2006: 840–855.
[102] J. H. Chang, L. Tassiulas. Maximum Lifetime Routing in Wireless Sensor Networks. IEEE/ACM Transactions on Networking, Aug. 2004, 12(4): 609–619.
[103] C. Intanagonwiwat, D. Estrin, R. Govindan, et al. Impact of Network Density on Data Aggregation in Wireless Sensor Networks. Techinal Report 01-750, Computer Science Department, University of Southern California: Los Angeles, CA, USA, Nov. 2001.
[104] K. Akkaya, M. Younis, W. Youssef. Positioning of Base Stations in Wireless Sensor Networks. IEEE Communications Magazine, Apr. 2007, 45(4): 96–102.
[105] A. Efrat, S. Har-Peled, J. S. B. Mitchell. Approximation Algorithms for Two Optimal Location Problems in Sensor Networks. Proceedings of the 2nd International Conference on Broadband Networks (BroadNets’05), Boston, MA, USA, Oct. 2005: 714–723.
[106] A. Boukerche, H. A. B. Oliveira, E. F. Nakamura, et al. Localization Systems for WirelessSensor Networks. IEEE Wireless Communications, Dec. 2007, 14(6): 6–12.
[107] D. Niculescu, B. Nath. Ad Hoc Positioning System (APS) Using AOA. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’03), San Francisco, CA, USA, Mar. 2003: 1734–1743.
[108] J. Elson, K. Romer. Wireless Sensor Networks: A New Regime for Time Synchronization. Proceedings of the 1st Workshop on Hot Topics in Networks (HotNets-I), Princeton, NJ, USA, Oct. 2002.
[109] F. Sivrikaya, B. Yener. Time Synchronization in Sensor Networks: A Survey. IEEE Network, Jul. 2004, 18(4): 45–50.
[110] J. van Greunen, J. Rabaey. Lightweight Time Synchronization for Sensor Networks. Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA’03), San Diego, CA, USA, Sep. 2003: 11–19.
[111] E. Shi, A. Perrig. Designing Secure Sensor Networks. IEEE Wireless Communications, Dec. 2004, 11(6): 38–43.
[112] X. Du, H. H. Chen. Security in Wireless Sensor Networks. IEEE Wireless Communications, Aug. 2008, 15(4): 60–66.
[113] Y. Wang, G. Attebury, B. Ramamurthy. A Survey of Security Issues in Wireless Sensor Networks. IEEE Communications Surveys Tutorials, 2006, 8(2): 2–23.
[114] J. C. Lee, V. C. M. Leung, K. H. Wong, et al. Key Management Issues in Wireless Sensor Networks: Current Proposals and Future Developments. IEEE Wireless Communications, Oct. 2007, 14(5): 76–84.
[115] M. F. Younis, K. Ghumman, M. Eltoweissy. Location-Aware Combinatorial Key Management Scheme for Clustered Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, Aug. 2006, 17(8): 865–882.
[116] A. Boukerche, D. Turgut. Secure Time Synchronization Protocols for Wireless Sensor Networks. IEEE Wireless Communications, Oct. 2007, 14(5): 64–69.
[117] A. Boukerche, H. A. B. Oliveira, E. F. Nakamura, et al. Secure Localization Algorithms for Wireless Sensor Networks. IEEE Communications Magazine, Apr. 2008, 46(4): 96–101.
[118] J. Li, D. Cordes, J. Zhang. Power-Aware Routing Protocols in Ad Hoc Wireless Networks. IEEE Wireless Communications, Dec. 2005, 12(6): 69–81.
[119] C. Intanagonwiwat, R. Govindan, D. Estrin, et al. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, Feb. 2003, 11(1): 2–16.
[120] C. Intanagonwiwat, D. Estrin, R. Govindan, et al. Impact of Network Density on Data Aggregation in Wireless Sensor Networks. Proceedings of 22nd International Conference on Distributed Computing Systems (ICDCS’02), Vienna, Austria, Jul. 2002: 457–458.
[121] L. Krishnamachari, D. Estrin, S. Wicker. The Impact of Data Aggregation in Wireless Sensor Networks. Proceedings of 22nd International Conference on Distributed Computing Systems Workshops (ICDCSW’02), Vienna, Austria, Jul. 2002: 575–578.
[122] S. Olariu, I. Stojmenovic. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting. Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM’06), Barcelona, Spain, Apr. 2006: 1–12.
[123] Y. Shi, Y. T. Hou. Optimal Base Station Placement in Wireless Sensor Networks. ACM Transactions on Sensor Networks, 2009, 5(4): 1–24.
[124] H. M. Ammari, S. K. Das. Data Dissemination to Mobile Sinks in Wireless Sensor Networks: An Information Theoretic Approach. Proceedings of IEEE International Conference on Mobile Adhoc and Sensor Systems Conference (MASS’05), Washington, DC, USA, Nov. 2005: 314–321.
[125] H. Luo, Y. Liu, S. K. Das. Routing Correlated Data in Wireless Sensor Networks: A Survey. IEEE Network, Nov. 2007, 21(6): 40–47.
[126] D. Slepian, J. Wolf. Noiseless Coding of Correlated Information Sources. IEEE Transactions on Information Theory, Jul. 1973, 19(4): 471–480.
[127] R. Cristescu, B. Beferull-Lozano, M. Vetterli. Networked Slepian-Wolf: Theory and Algorithms. Proceedings of the 1st European Workshop on Wireless Sensor Networks (EWSN’04), Berlin, Germany, Jan. 2004: 44–59.
[128] R. Cristescu, B. Beferull-Lozano, M. Vetterli. Networked Slepian-Wolf: Theory, Algorithms, and Scaling Laws. IEEE Transactions on Information Theory, Dec. 2005, 51(12): 4057–4073.
[129] R. Cristescu, B. Beferull-Lozano. Lossy Network Correlated Data Gathering with High-Resolution Coding. IEEE Transactions on Information Theory, Jun. 2006, 52(6): 2817–2824.
[130] K. Yuen, B. Liang, L. Baochun. A Distributed Framework for Correlated Data Gathering in Sensor Networks. IEEE Transactions on Vehicular Technology, Jan. 2008, 57(1): 578–593.
[131] R. Cristescu, B. Beferull-Lozano, M. Vetterli, et al. Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms. IEEE/ACM Transactions on Networking, Feb. 2006, 14(1): 41–54.
[132] R. Rajagopalan, P. K. Varshney. Data-Aggregation Techniques in Sensor Networks: A Survey. IEEE Communications Surveys Tutorials, 2006, 8(4): 48–63.
[133] R. Cristescu, B. Beferull-Lozano, M. Vetterli. On Network Correlated Data Gathering. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’04), Hong Kong, China, Mar. 2004: 2571–2582.
[134] C. Hua, T. S. P. Yum. Optimal Routing and Data Aggregation for Maximizing Lifetime of Wireless Sensor Networks. IEEE/ACM Transactions on Networking, Aug. 2008, 16(4): 892–903.
[135] C. Hua, T. S. P. Yum. Data Aggregated Maximum Lifetime Routing for Wireless Sensor Networks. Ad Hoc Networks, May 2008, 6(3): 380–392.
[136] B. Karp, H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom’00), Boston, MA, USA, Aug. 2000: 243–254.
[137] D. Li, J. Cao, M. Liu, et al. Construction of Optimal Data Aggregation Trees for Wireless Sensor Networks. Proceedings of the 15th International Conference on Computer Communications and Networks (ICCCN’06), Arlington, VA, USA, Oct. 2006: 475–480.
[138] R. Kannan, S. S. Iyengar. Game-Theoretic Models for Reliable Path-Length and Energy-Constrained Routing with Data Aggregation in Wireless Sensor Networks. IEEE Journal on Selected Areas in Communications, Aug. 2004, 22(6): 1141–1150.
[139] J. Luo, J. P. Hubaux. Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks. Proceedings of the 24th Annual Joint Conference of the IEEE Computer andCommunications Societies (INFOCOM’05), Miami, FL, USA, Mar. 2005: 1735–1746.
[140] J. Pan, Y. T. Hou, L. Cai, et al. Locating Base-Stations for Video Sensor Networks. Proceedings of IEEE 58th Vehicular Technology Conference (VTC’03-Fall), Orlando, FL, USA, Oct. 2003: 3000–3004.
[141] J. Pan, L. Cai, Y. T. Hou, et al. Optimal Base-Station Locations in Two-Tiered Wireless Sensor Networks. IEEE Transactions on Mobile Computing, Sep. 2005, 4(5): 458–473.
[142] Y. Shi, Y. T. Hou, A. Efrat. Algorithm Design for Base Station Placement Problems in Sensor Networks. Proceedings of the 3rd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine’06), Waterloo, Ontario, Canada, Aug. 2006.
[143] K. Selvarajah, V. Kadirkamanathan. Energy Efficient Sink Node Placement in Sensor Networks Using Particle Swarm Optimization. Proceedings of the 5th International Workshop Ant Colony Optimization and Swarm Intelligence (ANTS’06), Brussels, Belgium, Sep. 2006: 510–511.
[144] J. Rao, S. Biswas. Data Harvesting in Sensor Networks Using Mobile Sinks. IEEE Wireless Communications, Dec. 2008, 15(6): 63–70.
[145] K. Hwang, J. In, H. Y. Yun, et al. Dynamic Sink Oriented Tree Algorithm for Efficient Target Tracking of Multiple Mobile Sink Users in Wide Sensor Field. Proceedings of IEEE 60th Vehicular Technology Conference (VTC’04-Fall), Los Angeles, CA, USA, Sep. 2004: 4607–4610.
[146] C. Busch, S. Surapaneni, S. Tirthapura. Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks. Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’03), San Diego, CA, USA, Jun. 2003: 210–219.
[147] F. Ye, H. Luo, J. Cheng, et al. A Two-Tier Data Dissemination Model for Large-Scale Wireless Sensor Networks. Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom’02), Atlanta, GA, USA, Sep. 2002: 148–159.
[148] S. Nesamony, M. K. Vairamuthu, M. E. Orlowska. On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network. Proceedings of the 4th International Conference on Networked Sensing Systems (INSS’07), Braunschweig, Germany, Jun. 2007: 61–64.
[149] S. Nesamony, M. K. Vairamuthu, M. E. Orlowska, et al. Shortest Path Computation of a Calibrating Mobile Sink in a Wireless Sensor Network. Technical Report-468, School of Information Technology and Electrical Engineering, University of Queensland: Brisbane, Queensland, Australia, Mar. 2007.
[150] S. Nesamony, M. K. Vairamuthu, M. E. Orlowska. On the Traversals of Multiple Mobile Sinks in Sensor Networks. Proceedings of IEEE International Conference on Telecommunications and Malaysia International Conference on Communications (ICT-MICC’07), Penang, Malaysia, May 2007: 432–437.
[151] M. Kamat, A. S. Ismail, S. Olariu. Optimized-Hilbert for Mobility in Wireless Sensor Networks. Proceedings of International Conference on Computational Science and its Applications (ICCSA’07), Kuala Lampur, Malaysia, Aug. 2007: 554–560.
[152] M. Gatzianas, L. Georgiadis. A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink. IEEE Transactions on Wireless Communications, Mar. 2008, 7(3): 984–994.
[153] Y. Shi, Y. T. Hou. Theoretical Results on Base Station Movement Problem for Sensor Networks. Technical Report, Bradley Department of Electrical and Computer Engineering, Virginia Polytechnic Institute and State University: Blacksburg, VA, USA, Jul. 2007.
[154] Y. Shi, Y. T. Hou. Theoretical Results on Base Station Movement Problem for Sensor Network. Proceedings of the 27th IEEE Conference on Computer Communications (INFOCOM’08), Phoenix, AZ, USA, Apr. 2008: 1–5.
[155] J. O. Berger, V. de Oliveira, B. Sansó. Objective Bayesian Analysis of Spatially Correlated Data. Journal of the American Statistical Association, Dec. 2001, 96(456): 1361–1374.
[156] M. C. Vuran, I. F. Akyildiz. Spatial Correlation-Based Collaborative Medium Access Control in Wireless Sensor Networks. IEEE/ACM Transactions on Networking, Apr. 2006, 14(2): 316–329.
[157] M. C. Vuran, O. B. Akan. Spatio-Temporal Characteristics of Point and Field Sources in Wireless Sensor Networks. Proceedings of IEEE International Conference on Communications (ICC’06), Istanbul, Turkey, Jun. 2006: 234–239.
[158] R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows: Theory, Algorithms andApplications. Upper Saddle River, NJ, USA: Prentice Hall, Feb. 1993.
[159] J. H. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: University of Michigan Press, 1975.
[160] J. E. Beasley, P. C. Chu. A Genetic Algorithm for the Set Covering Problem. European Journal of Operational Research, Oct. 1996, 94(2): 392–404.
[161] J. J. Grefenstette, R. Gopal, B. J. Rosmaita, et al. Genetic Algorithm for the TSP. Proceedings of the 1st International Conference on Genetic Algorithms (ICGA’85), Pittsburgh, PA, USA, Jul. 1985: 160–168.
[162] S. Khuri, T. B?ck, J. Heitk?tter. The Zero/One Multiple Knapsack Problem and Genetic Algorithms. Proceedings of the 1994 ACM Symposium on Applied Computing (SAC’94), Phoenix, AZ, United States, Mar. 1994: 188–193.
[163] C. R. Reeves. Using Genetic Algorithms with Small Populations. Proceedings of the 5th International Conference on Genetic Algorithms (ICGA’93), Urbana-Champaign, IL, USA, Jun. 1993: 92–99.
[164] T. E. Davis, J. C. Principe. A Markov Chain Framework for the Simple Genetic Algorithm. Evolutionary Computation, fall 1993, 1(3): 269–288.
[165] G. Rudolph. Convergence Properties of Evolutionary Algorithms. Hamburg, Germany: Verlag Dr. Kova?, 1997.
[166] D. E. Knuth. Two Notes on Notation. American Mathematical Monthly, May 1992, 99(5): 403–422.
[167] S. R. Otto, J. P. Denier. An Introduction to Programming and Numerical Methods in MATLAB. London, UK: Springer-Verlag London Ltd, May 2005.
[168] R. M. Karp. Reducibility Among Combinatorial Problems. Proceedings of Complexity of Computer Computations, New York, NY, USA, Mar. 1972.
[169] F. Y. S. Lin, Y. F. Wen. Multi-Sink Data Aggregation Routing and Scheduling with Dynamic Radii in WSNs. IEEE Communications Letters, Oct. 2006, 10(10): 692–694.
[170] D. P. Bertsekas. Network Optimization: Continuous and Discrete Models. Belmont, MA, USA: Athena Scientific, May 1998.
[171] S. Kim, H. Ahn. Convergence of a Generalized Subgradient Method for Nondifferentiable Convex Optimization. Mathematical Programming, Mar. 1991, 50(1): 75–80.
[172] D. G. Luenberger, Y. Ye. Linear and Nonlinear Programming. 3rd Ed. New York, NY, USA: Springer New York, 2008.
[173] D. P. Bertsekas, R. G. Gallager. Data Networks. 2nd Ed. Englewood Cliffs, NJ, USA: Prentice-Hall, Jan. 1992.
[174] J. Nocedal, S. J. Wright. Numerical Optimization. 2nd Ed. New York, NY, USA: Springer New York, 2006.
[175] S. Boyd, L. Vandenberghe. Convex Optimization. Trumpington Street, Cambridge, UK: Cambridge University Press, 2004.