Ebrahimi, Dariush (2016) Compressive Data Gathering in Wireless Sensor Networks. PhD thesis, Concordia University.
Preview |
Text (application/pdf)
6MBEbrahimi_PhD_S2016.pdf - Accepted Version |
Abstract
The thesis focuses on collecting data from wireless sensors which are deployed randomly in a region. These sensors are widely used in applications ranging from tracking to the monitoring of environment, traffic and health among others. These energy constrained sensors, once deployed may receive little or no maintenance. Hence gathering data in the most energy efficient manner becomes critical for the longevity of wireless sensor networks (WSNs).
Recently, Compressive data gathering (CDG) has emerged as a useful method for collecting sensory data in WSN; this technique is able to reduce global scale communication cost without introducing intensive computation, and is capable of extending the lifetime of the entire sensor network by balancing the forwarding load across the network. This is particularly true due to the benefits obtained from in-network data compression. With CDG, the central unit, instead of receiving data from all sensors in the network, it may receive very few compressed or weighted sums from sensors, and eventually recovers the original data.
To prolong the lifetime of WSN, in this thesis, we present data gathering methods based on CDG. More specifically, we propose data gathering schemes using CDG by building up data aggregation trees from sensor nodes to a central unit (sink). Our problem aims at minimizing the number of links in the forwarding trees to minimize the number of overall transmissions. First, we mathematically formulate the problem and solve it using optimization program. Owing to its complexity, we present real-time algorithmic (centralized and decentralized) methods to efficiently solve the problem. We also explore the benefits one may obtain when jointly applying compressive data gathering with network coding in a wireless sensor network. Finally, and in the context of compressive data gathering, we study the problem of joint forwarding tree construction and scheduling under a realistic interference model, and propose some efficient distributed methods for solving it. We also present a primal dual decomposition method, using the theory of column generation, to solve this complex problem.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering |
|---|---|
| Item Type: | Thesis (PhD) |
| Authors: | Ebrahimi, Dariush |
| Institution: | Concordia University |
| Degree Name: | Ph. D. |
| Program: | Computer Science |
| Date: | 12 February 2016 |
| Thesis Supervisor(s): | Assi, Chadi |
| ID Code: | 980879 |
| Deposited By: | DARIUSH EBRAHIMI |
| Deposited On: | 16 Jun 2016 15:41 |
| Last Modified: | 18 Jan 2018 17:52 |
References:
[1] R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204–1216, 2000.[2] G. Allard, V. Genc, and J. Yelloz. Fully distributed clock synchronization in wide-range TDMA ad-hoc networks. In MILITARY COMMUNICATIONS CONFERENCE, 2011-MILCOM, pages 920–925. IEEE, 2011.
[3] M. Alnuaimi, K. Shuaib, K. Alnuaimi, and M. Abed-Hafez. Data gathering in wireless sensor networks with ferry nodes. In 2015 IEEE 12th International Conference on Networking, Sensing and Control (ICNSC), pages 221–225. IEEE, 2015.
[4] M. Andrews and M. Dinitz. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In IEEE INFOCOM 2009, pages 1332–1340. IEEE, 2009.
[5] W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak. Compressive wireless sensing. In Proceedings of the 5th international conference on Information processing in sensor networks, pages 134–142. ACM, 2006.
[6] K. C. Barr and K. Asanovi´c. Energy-aware lossless data compression. ACM Transactions on Computer Systems (TOCS), 24(3):250–291, 2006.
[7] M. Borghini, F. Cuomo, T. Melodia, U. Monaco, and F. Ricciato. Optimal data delivery in wireless sensor networks in the energy and latency domains. In Proceedings of the First International Conference on Wireless Internet, pages 138–145. IEEE, 2005.
[8] C. Caione, D. Brunelli, and L. Benini. Compressive sensing optimization over zigbee networks. In 2010 International Symposium on Industrial Embedded Systems (SIES), pages 36–44. IEEE, 2010.
[9] E. J. Cand`e and M. B. Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, 25(2):21–30, 2008.
[10] G. Cao, F. Yu, and B. Zhang. Improving network lifetime for wireless sensor network using compressive sensing. In 2011 IEEE 13th International Conference on High Performance Computing and Communications (HPCC), pages 448–454. IEEE, 2011.
[11] M. Cardei, J.Wu, M. Lu, and M. O. Pervaiz. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In IEEE International Conference on Wireless And Mobile Computing, Networking And Communications, 2005 (WiMob’2005)., volume 3, pages 438–445. IEEE, 2005.
[12] S. Chen and Y. Wang. Data collection capacity of random-deployed wireless sensor networks under physical models. Tsinghua Science and Technology, 17(5):487–498, 2012.
[13] Z. Chen, G. Yang, L. Chen, and J. Wang. An algorithm for data aggregation scheduling with long-lifetime and low-latency in wireless sensor networks. International Journal of Future Generation Communication and Networking, 5(4):141–152, 2012.
[14] J.-H. Chou, D. Petrovic, and K. Ramachandran. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, volume 2, pages 1054–1062. IEEE, 2003.
[15] V. Chvatal. Linear programming. Macmillan, 1983.
[16] T. H. Cormen. Introduction to algorithms. MIT press, 2009.
[17] R. Cristescu, B. Beferull-Lozano, and M. Vetterli. On network correlated data gathering. In INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, volume 4, pages 2571–2582. IEEE, 2004.
[18] R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer. Network correlated data gathering with explicit communication: NP-completeness and algorithms. IEEE/ACM Transactions on Networking, 14(1):41–54, 2006.
[19] F. Cuomo, A. Abbagnale, and E. Cipollone. Cross-layer network formation for energy-efficient IEEE 802.15. 4/zigbee wireless sensor networks. Ad Hoc Networks, 11(2):672–686, 2013.
[20] M. A. Davenport, M. F. Duarte, Y. C. Eldar, and G. Kutyniok. Introduction to compressed sensing. Preprint, 93(1):2, 2011.
[21] D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.
[22] D. Ebrahimi and C. Assi. Optimal and efficient algorithms for projection based compressive data gathering. IEEE Communications Letters, 17(8):1572–1575, 2013.
[23] D. Ebrahimi and C. Assi. Compressive data gathering using random projection for energy efficient wireless sensor networks. Ad Hoc Networks, 16:105–119, 2014.
[24] D. Ebrahimi and C. Assi. A distributed method for compressive data gathering in wireless sensor networks. IEEE Communications Letters, 18(4):624–627, 2014.
[25] D. Ebrahimi and C. Assi. Joint compressive data gathering and scheduling in wireless sensor networks under the physical interference model. In 2015 IEEE 16th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pages 1–9. IEEE, 2015.
[26] M. Enachescu, A. Goel, R. Govindan, and R. Motwani. Scale free aggregation in sensor networks. In Algorithmic Aspects of Wireless Sensor Networks, pages 71–84. Springer, 2004.
[27] J. Gao, L. Guibas, N. Milosavljevic, and J. Hershberger. Sparse data aggregation in sensor networks. In Proceedings of the 6th international conference on Information processing in sensor networks, pages 430–439. ACM, 2007.
[28] K. K. Gautam, N. K. Gautam, and P. Agrawal. Memory required for wireless sensor nodes on the basis of characteristics and behaviour when using TinyOS. 4(1):26–34, 2014.
[29] A. Giridhar and P. Kumar. Computing and communicating functions over sensor networks. IEEE Journal on Selected Areas in Communications, 23(4):755–764, 2005.
[30] D. Gong and Y. Yang. Low-latency SINR-based data gathering in wireless sensor networks. IEEE Transactions on Wireless Communications, 13(6):3207–3221, 2014.
[31] O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer. Complexity in geometric SINR. pages 100–109. ACM MobiHoc, 2007.
[32] D. K. Gupta. A review on wireless sensor networks. Network and Complex Systems, 3(1):18–23, 2013.
[33] H. Gupta, V. Navda, S. Das, and V. Chowdhary. Efficient gathering of correlated data in sensor networks. ACM Transactions on Sensor Networks (TOSN), 4(1):4:1–4:31, 2008.
[34] P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388–404, 2000.
[35] S. Hariharan and N. B. Shroff. Maximizing aggregated information in sensor networks under deadline constraints. IEEE Transactions on Automatic Control, 56(10):2369–2380, 2011.
[36] J. Haupt,W. U. Bajwa, M. Rabbat, and R. Nowak. Compressed sensing for networked data. IEEE Signal Processing Magazine, 25(2):92–101, 2008.
[37] S. He, J. Chen, D. K. Yau, and Y. Sun. Cross-layer optimization of correlated data gathering in wireless sensor networks. IEEE Transactions on Mobile Computing, 11(11):1678–1691, 2012.
[38] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, pages 10–pp. IEEE, 2000.
[39] T.-H. Hsu and P.-Y. Yen. Adaptive time division multiple access-based medium access control protocol for energy conserving and data transmission in wireless sensor networks. IET Communications, 5(18):2662–2672, 2011.
[40] F. K. Hwang, D. S. Richards, and P. Winter. The Steiner tree problem. Elsevier, 1992.
[41] O. D. Incel and B. Krishnamachari. Enhancing the data collection rate of tree-based aggregation in wireless sensor networks. In SECON’08. 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, pages 569–577. IEEE, 2008.
[42] B. Jang, J. B. Lim, and M. L. Sichitiu. An asynchronous scheduled mac protocol for wireless sensor networks. Computer Networks, 57(1):85–98, 2013.
[43] S. Ji, R. Beyah, and Z. Cai. Snapshot and continuous data collection in probabilistic wireless sensor networks. IEEE Transactions on Mobile Computing, 13(3):626–637, 2014.
[44] S. Ji and Z. Cai. Distributed data collection in large-scale asynchronous wireless sensor networks under the generalized physical interference model. IEEE/ACM Transactions on Networking (ToN), 21(4):1270–1283, 2013.
[45] C. Joo, J.-G. Choi, and N. B. Shroff. Delay performance of scheduling with data aggregation in wireless sensor networks. In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010.
[46] S. Katti, S. Gollakota, and D. Katabi. Embracing wireless interference: analog network coding. In ACM SIGCOMM Computer Communication Review, volume 37, pages 397–408. ACM, 2007.
[47] S. Katti, D. Katabi, H. Balakrishnan, and M. Medard. Symbol-level network coding for wireless mesh networks. In ACM SIGCOMM Computer Communication Review, volume 38, pages 401–412. ACM, 2008.
[48] S. Katti, H. Rahul,W. Hu, D. Katabi, M.M´edard, and J. Crowcroft. Xors in the air: practical wireless network coding. In ACM SIGCOMM Computer Communication Review, volume 36, pages 243–254. ACM, 2006.
[49] L. Keller, E. Atsan, K. Argyraki, and C. Fragouli. Sensecode: Network coding for reliable sensor networks. ACM Transactions on Sensor Networks (TOSN), 9(2):25:1–25:20, 2013.
[50] L. Kou, G. Markowsky, and L. Berman. A fast algorithm for steiner trees. Acta informatica, 15(2):141–145, 1981.
[51] T.-W. Kuo and M.-J. Tsai. On the construction of data aggregation tree with minimum energy cost in wireless sensor networks: NP-completeness and approximation algorithms. In 2012 Proceedings IEEE INFOCOM, pages 2591–2595. IEEE, 2012.
[52] L. B. Le, E. Modiano, C. Joo, and N. B. Shroff. Longest-queue-first scheduling under SINR interference model. In Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing, pages 41–50. ACM, 2010.
[53] S. Lee, S. Pattem, M. Sathiamoorthy, B. Krishnamachari, and A. Ortega. Compressed sensing and routing in multi-hop networks. University of Southern California CENG Technical Report, 2009.
[54] H. Li, Q. S. Hua, C. Wu, and F. C. M. Lau. Minimum-latency aggregation scheduling in wireless sensor networks under physical interference model. In Proceedings of the 13th ACM international conference on Modeling, analysis, and simulation of wireless and mobile systems, pages 360–367. ACM, 2010.
[55] J. Li, A. Deshpande, and S. Khuller. On computing compression trees for data collection in wireless sensor networks. In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010.
[56] S. Lindsey, C. Raghavendra, and K. M. Sivalingam. Data gathering algorithms in sensor networks using energy metrics. IEEE Transactions on Parallel and Distributed Systems, 13(9):924–935, 2002.
[57] C. Liu and G. Cao. Distributed monitoring and aggregation in wireless sensor networks. In Proceedings IEEE INFOCOM, 2010, pages 1–9. IEEE, 2010.
[58] C. Liu, K. Wu, and J. Pei. An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation. IEEE Transactions on Parallel and Distributed Systems, 18(7):1010–1023, 2007.
[59] L. Lu, T.Wang, S. C. Liew, and S. Zhang. Implementation of physical-layer network coding. Physical Communication, 6:74–87, 2013.
[60] C. Luo, F. Wu, J. Sun, and C. W. Chen. Compressive data gathering for large-scale wireless sensor networks. In Proceedings of the 15th annual international conference on Mobile computing and networking, pages 145–156. ACM, 2009.
[61] D. Luo, X. Zhu, X. Wu, and G. Chen. Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks. In Proceedings IEEE INFOCOM, 2011, pages 1566–1574. IEEE, 2011.
[62] J. Luo, L. Xiang, and C. Rosenberg. Does compressed sensing improve the throughput of wireless sensor networks? In 2010 IEEE International Conference on Communications (ICC), pages 1–6. IEEE, 2010.
[63] S. Mehrjoo, J. Shanbehzadeh, and M. M. Pedram. A novel intelligent energy-efficient delay-aware routing in WSN, based on compressive sensing. In 2010 5th International Symposium on Telecommunications (IST), pages 415–420. IEEE, 2010.
[64] N. Naderializadeh and A. S. Avestimehr. ITLinQ: A new approach for spectrum sharing in device-to-device communication systems. IEEE Journal on Selected Areas in Communications, 32(6):1139–1151, 2014.
[65] C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[66] M. Safar, H. Al-Hamadi, and D. Ebrahimi. Peca: power efficient clustering algorithm for wireless sensor networks. International Journal of Information Technology and Web Engineering (IJITWE), 6(1):49–58, 2011.
[67] M. Sartipi and R. Fletcher. Energy-efficient data acquisition in wireless sensor networks using compressed sensing. In Data Compression Conference (DCC), pages 223–232. IEEE, 2011.
[68] S. Sengupta, S. Rayanchu, and S. Banerjee. Network coding-aware routing in wireless networks. IEEE/ACM Transactions on Networking, 18(4):1158–1170, 2010.
[69] W.-Z. Song, F. Yuan, R. LaHusen, and B. Shirazi. Time-optimum packet scheduling for many-to-one routing in wireless sensor networks. The International Journal of Parallel, Emergent and Distributed Systems, 22(5):355–370, 2007.
[70] R. Subramanian and F. Fekri. Sleep scheduling and lifetime maximization in sensor networks: fundamental limits and optimal solutions. In Proceedings of the 5th international conference on Information processing in sensor networks, pages 218–225. ACM, 2006.
[71] N. Thepvilojanapong, Y. Tobe, and K. Sezaki. On the construction of efficient data gathering tree in wireless sensor networks. In IEEE International Symposium on Circuits and Systems, 2005. ISCAS 2005, pages 648–651. IEEE, 2005.
[72] D. Traskov et al. Network coding for multiple unicasts: An approach based on linear optimization. PhD thesis, Citeseer, 2006.
[73] D. Traskov, M. Heindlmaier, M. M´edard, R. Koetter, and D. S. Lun. Scheduling for network coded multicast: A conflict graph formulation. In 2008 IEEE GLOBECOM Workshops, pages 1–5. IEEE, 2008.
[74] W. Wang, M. Garofalakis, and K. Ramchandran. Distributed sparse random projections for refinable approximation. In Proceedings of the 6th international conference on Information processing in sensor networks, pages 331–339. ACM, 2007.
[75] X. Wang, Z. Zhao, Y. Xia, and H. Zhang. Compressed sensing based random routing for multi-hop wireless sensor networks. In 2010 International Symposium on Communications and Information Technologies (ISCIT), pages 220–225. IEEE, 2010.
[76] Z. Wei, Y. Sun, and Y. Ji. An integrating data gathering scheme for wireless sensor networks. In 2013 IEEE Wireless Communications and Networking Conference (WCNC), pages 1151–1156. IEEE, 2013.
[77] Wikipedia. List of wireless sensor nodes. http://timmurphy.
org/2009/07/22/line-spacing-in-latex-documents/. Accessed
February 9, 2016.
[78] X. Wu, S. Tavildar, S. Shakkottai, T. Richardson, J. Li, R. Laroia, and A. Jovicic. FlashLinQ: A synchronous distributed scheduler for peer-to-peer ad hoc networks. IEEE/ACM Transactions on Networking (TON), 21(4):1215–1228, 2013.
[79] X. Wu, Y. Xiong, W. Huang, H. Shen, and M. Li. An efficient compressive data gathering routing scheme for large-scale wireless sensor networks. Computers & Electrical Engineering, 39(6):1935–1946, 2013.
[80] Y. Wu, S. Fahmy, and N. B. Shroff. On the construction of a maximum lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm. In IEEE INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008.
[81] L. Xiang, J. Luo, and C. Rosenberg. Compressed data aggregation: Energy-efficient and high-fidelity data collection. IEEE/ACM Transactions on Networking, 21(6):1722–1735, 2013.
[82] L. Xiang, J. Luo, and A. Vasilakos. Compressed data aggregation for energy efficient wireless sensor networks. In 8th annual IEEE communications society conference on sensor, mesh and ad hoc communications and networks (SECON), 2011, pages 46–54. IEEE, 2011.
[83] R. Xie and X. Jia. Transmission-efficient clustering method for wireless sensor networks using compressive sensing. IEEE Transactions on Parallel and Distributed Systems,, 25(3):806–815, 2014.
[84] X. Xu, R. Ansari, and A. Khokhar. Power-efficient hierarchical data aggregation using compressive sensing in WSNs. In 2013 IEEE International Conference on Communications (ICC), pages 1769–1773. IEEE, 2013.
[85] X. Xu, X.-Y. Li, and M. Song. Efficient aggregation scheduling in multihop wireless sensor networks with SINR constraints. IEEE Transactions on Mobile Computing, 12(12):2518–2528, 2013.
[86] B. Yu, J. Li, and Y. Li. Distributed data aggregation scheduling in wireless sensor networks. In IEEE INFOCOM 2009, pages 2159–2167. IEEE, 2009.
[87] Y. Yu, B. Krishnamachari, and V. K. Prasanna. Energy-latency tradeoffs for data gathering in wireless sensor networks. In INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 224–255. IEEE, 2004.
[88] M. Zhao, Y. Yang, and C. Wang. Mobile data gathering with load balanced clustering and dual data uploading in wireless sensor networks. IEEE Transactions on Mobile Computing, 14(4):770–785, 2015.
[89] W. Zhao and X. Tang. Scheduling sensor data collection with dynamic traffic patterns. IEEE Transactions on Parallel and Distributed Systems, 24(4):789–802, 2013.
[90] H. Zheng, S. Xiao, X. Wang, X. Tian, and M. Guizani. Capacity and delay analysis for data gathering with compressive sensing in wireless sensor networks. IEEE Transactions on Wireless Communications, 12(2):917–927, 2013.
[91] G. Zhou, T. He, J. A. Stankovic, and T. Abdelzaher. Rid: radio interference detection in wireless sensor networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 2, pages 891–901. IEEE, 2005.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics