{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:39:35Z","timestamp":1760243975374,"version":"build-2065373602"},"reference-count":59,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2009,2,3]],"date-time":"2009-02-03T00:00:00Z","timestamp":1233619200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this work we focus on the energy efficiency challenge in wireless sensor networks, from both an on-line perspective (related to routing), as well as a network design perspective (related to tracking). We investigate a few representative, important aspects of energy efficiency: a) the robust and fast data propagation b) the problem of balancing the energy dissipation among all sensors in the network and c) the problem of efficiently tracking moving entities in sensor networks. Our work here is a methodological survey of selected results that have already appeared in the related literature. In particular, we investigate important issues of energy optimization, like minimizing the total energy dissipation, minimizing the number of transmissions as well as balancing the energy load to prolong the system\u2019s lifetime. We review characteristic protocols and techniques in the recent literature, including probabilistic forwarding and local optimization methods. We study the problem of localizing and tracking multiple moving targets from a network design perspective i.e. towards estimating the least possible number of sensors, their positions and operation characteristics needed to efficiently perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. Under this model, we abstract the tracking network design problem by a covering combinatorial problem and then design and analyze an efficient approximate method for sensor placement and operation.<\/jats:p>","DOI":"10.3390\/a2010121","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T03:03:04Z","timestamp":1233716584000},"page":"121-157","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Probabilistic Distributed Algorithms for Energy Efficient Routing and Tracking in Wireless Sensor Networks"],"prefix":"10.3390","volume":"2","author":[{"given":"Sotiris","family":"Nikoletseas","sequence":"first","affiliation":[{"name":"Computer Technology Institute (CTI) and Dept of Computer Engineering and Informatics, University of Patras, Greece"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Computer Technology Institute (CTI) and Dept of Computer Engineering and Informatics, University of Patras, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2009,2,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","article-title":"Wireless sensor networks: a survey","volume":"38","author":"Akyildiz","year":"2002","journal-title":"J. Comput. Networks"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/1150334.1150336","article-title":"Algorithmic construction of sets for k-restrictions","volume":"2","author":"Alon","year":"2006","journal-title":"ACM Trans. Algorithms"},{"key":"ref_3","unstructured":"Antoniou, T., Boukerche, A., Chatzigiannakis, I., Mylonas, G., and Nikoletseas, S. (,  2004). A New Energy Efficient and Fault-tolerant Protocol for Data Propagation in Smart Dust Networks using Varying Transmission Range. Proc. 37th Annual ACM\/IEEE Simulation Symposium (ANSS\u201904)."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1109\/MCOM.2002.1024422","article-title":"A Survey on Sensor Networks","volume":"40","author":"Akyildiz","year":"2002","journal-title":"IEEE Commun. Mag."},{"key":"ref_5","unstructured":"Aspnes, J., Goldberg, D., and Yang, Y. (2004). Proc. 1st Int. Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2004), Springer-Verlag. Lecture Notes in Computer Science, LNCS 3121."},{"key":"ref_6","unstructured":"Boukerche, A., Cheng, X., and Linus, J. (, January September). Energy-Aware Data-Centric Routing in Microsensor Networks. Proc. of ACM Modeling, Analysis and Simulation of Wireless and Mobile Systems."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1448","DOI":"10.1109\/TC.2002.1146711","article-title":"Grid coverage for surveillance and target location in distributed sensor networks","volume":"51","author":"Chakrabarty","year":"2002","journal-title":"IEEE Trans. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Nikoletseas, S., and Spirakis, P. (,  2002). Smart Dust Protocols for Local Detection and Propagation. Proc. 2nd ACM Workshop on Principles of Mobile Computing (POMC\u20192002), This article also appeared as: Chatzigiannakis, I.; Nikoletseas, S.; Spirakis, P. Efficient and Robust Protocols for Local Detection and Propagation in Smart Dust Networks. Mobile Networks and Applications 2005, 10, 133\u2013149.","DOI":"10.1023\/B:MONE.0000048551.54039.f0"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Dimitriou, T., Nikoletseas, S., and Spirakis, P. (,  2004). A Probabilistic Algorithm for Efficient and Robust Data Propagation in Smart Dust Networks. Proc. 5th European Wireless Conference on Mobile and Wireless Systems beyond 3G (EW 2004), This article also appeared as: Chatzigiannakis, I.; Dimitriou, T.; Nikoletseas, S.; Spirakis, P. A probabilistic algorithm for efficient and robust data propagation in wireless sensor networks. Ad-Hoc Networks 2006, 4, 621\u2013635.","DOI":"10.1016\/j.adhoc.2005.06.006"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., Dimitriou, T., Mavronicolas, M., Nikoletseas, S., and Spirakis, P. (,  2003). A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks. Proc. International Conference on Parallel and Distributed Computing (EUPOPAR), Euro-Par 2003 Parallel Processing; Springer-Verlag: Heidelberg, Germany, 2003; Lecture Notes in Computer Science, Capter 15, pp. 1003-1016. This article also appeared as: Chatzigiannakis, I.; Dimitriou, T.; Mavronicolas, M.; Nikoletseas, S.; Spirakis, P. A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks. Parallel Processing Letters 2003, 13, 615\u2013627.","DOI":"10.1007\/978-3-540-45209-6_138"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chatzigiannakis, I., and Nikoletseas, S. A Sleep-Awake Protocol for Information Propagation in Smart Dust Networks. Proc. 3rd Workshop on Mobile and Ad-Hoc Networks (WMAN), IPDPS Workshops, This article also appeared as: Chatzigiannakis, I.; Nikoletseas, S. Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks. Mobile Networks and Applications 2004, 9, 319\u2013332.","DOI":"10.1023\/B:MONE.0000031591.74793.52"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chen, B., Jamieson, K., Balakrishnan, H., and Morris, R. (,  2001). SPAN: An energy efficient coordination algorithm for topology maintenance in ad-hoc wireless networks. Proc. ACM\/IEEE International Conference on Mobile Computing (MOBICOM).","DOI":"10.1145\/381677.381686"},{"key":"ref_13","unstructured":"Dhilon, S.S., Chakrabarty, K., and Iyengar, S.S. (, January Jul). Sensor placement for grid coverage under imprecise detections. Proc. 5th International Conference on Information Fusion, (FUSION\u201902), Annapolis, MD."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Duh, R.-C., and Fuerer, M. Approximation of k-Set Cover by Semi-Local Optimization. Proc. 29th Annual ACM Symposium on the Theory of Computing, 1997.","DOI":"10.1145\/258533.258599"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Estrin, D., Govindan, R., Heidemann, J., and Kumar, S. (,  1999). Next Century Challenges: Scalable Coordination in Sensor Networks. Proc. 5th ACM\/IEEE International Conference on Mobile Computing, (MOBICOM\u201999).","DOI":"10.1145\/313451.313556"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Euthimiou, H., Nikoletseas, S., and Rolim, J. (,  2004). Energy Balanced Data Propagation in Wireless Sensor Networks. Proc. 4th International Workshop on Algorithms for Wireless, Mobile, Ad-Hoc and Sensor Networks, (WMAN \u201904), This article also appeard as: Euthimiou, H.; Nikoletseas, S.; Rolim, J. Energy balanced data propagation in wireless sensor networks. Wireless Networks 2006, 12, 691\u2013707.","DOI":"10.1007\/s11276-006-6529-y"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A Threshold of ln n for Approximating Set Cover","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gui, C., and Mohapatra, P. (,  2004). Power conservation and quality of surveillance in target tracking sensor networks. Proc. ACM MobiCom Conference.","DOI":"10.1145\/1023720.1023734"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gupta, R., and Das, S.R. (,  2003). Tracking moving targets in a smart sensor network. Proc. VTC Symp.","DOI":"10.1109\/VETECF.2003.1286181"},{"key":"ref_20","unstructured":"Halldorsson, M.M. (,  1995). Approximating Discrete Collections via Local Improvements. Proc. ACM SODA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Halldorsson, M.M. (,  1996). Approximating k-Set Cover and Complementary Graph Coloring. Proc. IPCO.","DOI":"10.1007\/3-540-61310-2_10"},{"key":"ref_22","unstructured":"Hollar, S.E.A. (2000). COTS Dust. [M.Sc. Thesis, University of California]."},{"key":"ref_23","unstructured":"Heinzelman, W.R., Chandrakasan, A., and Balakrishnan, H. (,  2000). Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proc. 33rd Hawaii International Conference on System Sciences (HICSS\u20192000)."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Heinzelman, W.R., Kulik, J., and Balakrishnan, H. (,  1999). Adaptive Protocols for Information Dissemination in Wireless Sensor Networks. Proc. 5th ACM\/IEEE International Conference on Mobile Computing (MOBICOM\u20191999).","DOI":"10.1145\/313451.313529"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Intanagonwiwat, C., Govindan, R., and Estrin, D. (,  2000). Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. Proc. 6th ACM\/IEEE International Conference on Mobile Computing (MOBICOM\u20192000).","DOI":"10.1145\/345910.345920"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TNET.2002.808417","article-title":"Directed Diffusion for Wireless Sensor Networking","volume":"11","author":"Intanagonwiwat","year":"2003","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"ref_27","unstructured":"Intanagonwiwat, C., Estrin, D., Govindan, R., and Heidemann, J. (2001). Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Technical Report 01-750."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Jain, S., Demmer, M., Patra, R., and Fall, K. (,  2005). Using Redundancy to Cope with Failures in a Delay Tolerant Network. Proc. SIGCOMM.","DOI":"10.1145\/1080091.1080106"},{"key":"ref_29","unstructured":"Kahn, J.M., Katz, R.H., and Pister, K.S.J. (, January September). Next Century Challenges: Mobile Networking for Smart Dust. Proc. 5th ACM\/IEEE International Conference on Mobile Computing."},{"key":"ref_30","unstructured":"Karp, B. (2000). Geographic Routing for Wireless Networks. [Ph.D. Thesis, Harvard University]."},{"key":"ref_31","unstructured":"Kleinrock, L. (1975). Queueing Systems Theory, John Wiley & Sons."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Liu, J., Liu, J., Reich, J., Cheung, P., and Zhao, F. (,  2003). Distributed group management for track initiation and maintenance in target localization applications. Proc. Int. Workshop on Information Processing in Sensor Networks (IPSN).","DOI":"10.1007\/3-540-36978-3_8"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Lund, C., and Yannakakis, M. (1994). On the hardness of approximating minimization problems. J. ACM, 960\u2013981.","DOI":"10.1145\/185675.306789"},{"key":"ref_34","unstructured":"\u03bc-Adaptive Multi-domain Power aware Sensors. http:\/\/www-mtl.mit.edu\/research\/icsystems\/uamps."},{"key":"ref_35","unstructured":"Manjeshwar, A., and Agrawal, D.P. (,  2002). TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Proc. 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, satellite workshop of the 16th Annual International Parallel & Distributed Processing Symposium (IPDPS\u201902)."},{"key":"ref_36","unstructured":"Mehlhorn, K., and N\u00e4her, S. (1999). LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/978-3-540-77871-4_4","article-title":"Efficient Sensor Network Design for Continuous Monitoring of Moving Objects","volume":"Volume 4837","author":"Nikoletseas","year":"2008","journal-title":"Proc. of the Third International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 07)"},{"key":"ref_38","unstructured":"Nikoletseas, S., Chatzigiannakis, I., Euthimiou, H., Kinalis, A., Antoniou, A., and Mylonas, G. (,  2004). Energy Efficient Protocols for Sensing Multiple Events in Smart Dust Networks. Proc. 37th Annual ACM\/IEEE Simulation Symposium (ANSS\u201904)."},{"key":"ref_39","unstructured":"Perkins (2001). C.E. Ad Hoc Networking, Addison-Wesley."},{"key":"ref_40","unstructured":"Poduri, S., and Sukhatme, G.S. (, January April-May). Constrained coverage in mobile sensor networks. Proc. IEEE Int. Conf. Robotics and Automation (ICRA\u201904), New Orleans, LA, USA."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1109\/12.214691","article-title":"Computational complexity issues in operative diagnostics of graph based systems","volume":"42","author":"Rao","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"ref_42","unstructured":"Ross, S.M. (1995). Stochastic Processes, John Wiley and Sons. [2nd Edition]."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Shorey, R., Ananda, A., Chan, M.C., and Ooi, W.T. (2006). Mobile, Wireless, and Sensor Networks: Technology, Applications, and Future Directions. Wiley.","DOI":"10.1002\/0471755591"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Schurgers, C., Tsiatsis, V., Ganeriwal, S., and Srivastava, M. (,  2002). Topology Management for Sensor Networks: Exploiting Latency and Density. Proc. MOBICOM.","DOI":"10.1145\/513800.513817"},{"key":"ref_45","unstructured":"Tiny, O.S. A Component-based OS for the Network Sensor Regime. http:\/\/webs.cs.berkeley.edu\/tos\/."},{"key":"ref_46","unstructured":"Triantafilloy, P., Ntarmos, N., Nikoletseas, S., and Spirakis, P. (,  2003). NanoPeer Networks and P2P Worlds. Proc. 3rd IEEE International Conference on Peer-to-Peer Computing."},{"key":"ref_47","unstructured":"Ye, W., Heidemann, J., and Estrin, D. (2002, January June). An Energy-Efficient MAC Protocol for Wireless Sensor Networks. Proc. 12th IEEE International Conference on Computer Networks (INFOCOM), New York, NY, USA."},{"key":"ref_48","unstructured":"Wireless Integrated Sensor Networks. http:\/www.janet.ucla.edu\/WINS."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Xu, Y., Heidemann, J., and Estrin, D. (2001, January July). Geography-informed energy conservation for ad-hoc routing. Proc. ACM\/IEEE International Conference on Mobile Computing (MOBICOM), Rome, Italy.","DOI":"10.1145\/381677.381685"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1109\/2.895117","article-title":"Smart dust: communicating with a cubic-millimeter computer","volume":"34","author":"Warneke","year":"2001","journal-title":"Computer"},{"key":"ref_51","unstructured":"Zhang, W., and Cao, G. (,  2004). Optimizing tree reconfiguration for mobile target tracking in sensor networks. Proc. IEEE InfoCom."},{"key":"ref_52","unstructured":"Zhao, F., and Guibas, L. (2004). Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann Publishers."},{"key":"ref_53","unstructured":"Zou, Y., and Chakrabarty, K. (, January April). Sensor deployment and target localization based on virtual forces. Proc. IEEE InfoCom, San Francisco, CA."},{"key":"ref_54","unstructured":"Ringwald, M., and Roemer, K. (,  2005). BitMAC: a deterministic, collision-free, and robust MAC protocol for sensor networks. Proc. of the Second European Workshop on Sensor Networks."},{"key":"ref_55","first-page":"735","article-title":"Markov Chain Monte Carlo Data Association For General Multiple-Target Tracking Problems","volume":"Vol. 1","author":"Oh","year":"2004","journal-title":"Proc. Fourty-third IEEE Conference on Decision and Control"},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Demirbas, M., Arora, A., and Gouda, M.G. (,  2003). A Pursuer-Evader Game for Sensor Networks. Proc. Self-Stabilizing Systems, San Francisco, CA, USA.","DOI":"10.1007\/3-540-45032-7_1"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"He, T., Gu, L., Luo, L., Yan, T., Stankovic, J.A., and Son, S.H. (2006, January 29). An overview of data aggregation architecture for real-time tracking with sensor networks. Proc. IPDPS, Rhodes Island, Greece.","DOI":"10.21236\/ADA446929"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.jpdc.2006.10.007","article-title":"Energy optimal data propagation in wireless sensor networks","volume":"67","author":"Powell","year":"2007","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Jarry, A., Leone, P., Powell, O., and Rolim, J. (2006, January June). An Optimal Data Propagation Algorithm for Maximizing the Lifespan of Sensor Networks. Proc. DCOSS, San Francisco, CA, USA.","DOI":"10.1007\/11776178_25"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/1\/121\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:09:47Z","timestamp":1760220587000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/1\/121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,3]]},"references-count":59,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2009,3]]}},"alternative-id":["a2010121"],"URL":"https:\/\/doi.org\/10.3390\/a2010121","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,2,3]]}}}