×

Algorithms and simulation methods for topology-aware sensor networks. (English) Zbl 1248.68066

Lerner, Jürgen (ed.) et al., Algorithmics of large and complex networks. Design, analysis, and simulation. Berlin: Springer (ISBN 978-3-642-02093-3/pbk). Lecture Notes in Computer Science 5515, 380-400 (2009).
Summary: This chapter presents a number of different aspects related to a particular kind of large and complex networks: A wireless sensor network (WSN) consists of a large number of nodes that individually have limited computing power and information; their interaction is strictly local, but their task is to build global structures and pursue global objectives.
Dealing with WSNs requires a mixture of theory and practice, i.e., a combination of algorithmic foundations with simulations and experiments that has been the subject of our project SwarmNet. In the first part, we describe a number of fundamental algorithmic issues: boundary recognition without node coordinates, clustering, routing, and energy-constrained flows. The second part deals with the simulation of large-scale WSNs; we describe the most important challenges and how they can be tackled with our network simulator Shawn.
For the entire collection see [Zbl 1165.68015].

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science

Software:

ns-2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buschmann, C., Fekete, S.P., Fischer, S., Kröller, A., Pfisterer, D.: Koordinatenfreies Lokationsbewusstsein. IT- Information Technology 47, 70–78 (2005)
[2] Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D., Anderson, J.: Wireless sensor networks for habitat monitoring. In: ACM International Workshop on Wireless Sensor Networks and Applications (WSNA 2002), Atlanta, GA (2002) · doi:10.1145/570738.570751
[3] Szewczyk, R., Mainwaring, A., Polastre, J., Anderson, J., Culler, D.: An analysis of a large scale habitat monitoring application. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys 2004), pp. 214–226. ACM Press, New York (2004) · doi:10.1145/1031495.1031521
[4] Zhang, P., Sadler, C.M., Lyon, S.A., Martonosi, M.: Hardware design experiences in ZebraNet. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys 2004), pp. 227–238. ACM Press, New York (2004) · doi:10.1145/1031495.1031522
[5] Estrin, D., Govindan, R., Heidemann, J.: Embedding the Internet: Introduction. Commun. ACM 43(5), 38–41 (2000) · doi:10.1145/332833.332836
[6] Kumar, V.: Sensor: the atomic computing particle. SIGMOD Rec. 32(4), 16–21 (2003) · Zbl 05444423 · doi:10.1145/959060.959064
[7] Basu, A., Gao, J., Mitchell, J.S., Sabhnani, G.: Distributed localization using noisy distance and angle information. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2006), pp. 262–273. ACM Press, New York (2006) · doi:10.1145/1132905.1132934
[8] Wagner, D., Wattenhofer, R. (eds.): Algorithms for Sensor and Ad Hoc Networks. LNCS, vol. 4621. Springer, Heidelberg (2007)
[9] Fekete, S.P., Kröller, A., Pfisterer, D., Fischer, S., Buschmann, C.: Neighborhood-based topology recognition in sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 123–136. Springer, Heidelberg (2004) · Zbl 1104.68317 · doi:10.1007/978-3-540-27820-7_12
[10] Fekete, S.P., Kaufmann, M., Kröller, A., Zweig, K.A.: A new approach for boundary recognition in geometric sensor networks. In: Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), pp. 82–85 (2005)
[11] Kröller, A., Fekete, S.P., Pfisterer, D., Fischer, S.: Deterministic boundary recognition and topology extraction for large sensor networks. In: Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1000–1009 (2006) · Zbl 1192.68043 · doi:10.1145/1109557.1109668
[12] Choi, H.I., Choi, S.W., Moon, H.P.: Mathematical theory of medial axis transform. Pacific Journal of Mathematics 181, 57–88 (1997) · Zbl 0885.53004 · doi:10.2140/pjm.1997.181.57
[13] Sherbrooke, E.C., Patrikalakis, N.M., Wolter, F.E.: Differential and topological properties of medial axis transforms. Graphical Models and Image Processing 58(6), 574–592 (1996) · Zbl 05473522 · doi:10.1006/gmip.1996.0047
[14] Kröller, A.: Algorithms for Topology-Aware Sensor Networks. Ph.D thesis, Braunschweig Institute of Technology (2008)
[15] Förster, K.T.: Clusterbasierte Objektüberwachung in drahtlosen Sensornetzwerken: Lokal optimale Wege in der Ebene und ihre Anwendung in Sensornetzwerken. Diploma thesis, Braunschweig Institute of Technology (2007)
[16] Fekete, S.P., Förster, K.T., Kröller, A.: Local routing in geometric cluster graphs (2009)
[17] Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Operations Research 6, 419–433 (1958) · doi:10.1287/opre.6.3.419
[18] Fekete, S.P., Hall, A., Köhler, E., Kröller, A.: The maximum energy-constrained dynamic flow problem. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 114–126. Springer, Heidelberg (2008) · Zbl 1155.68561 · doi:10.1007/978-3-540-69903-3_12
[19] Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proc. FOCS, p. 300 (1998) · Zbl 1137.90014 · doi:10.1109/SFCS.1998.743463
[20] University of Southern California, Information Sciences Institute (ISI): Ns-2: Network simulator-2 (1995), http://www.isi.edu/nsnam/ns/
[21] Varga, A.: OMNeT++: Objective modular network testbed in C++ (2007), http://www.omnetpp.org
[22] Levis, P., Lee, N., Welsh, M., Culler, D.: TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In: Proceedings of the First ACM Conference on Embedded Networked Sensor Systems, SenSys 2003 (2003), http://www.cs.berkeley.edu/ pal/research/tossim.html
[23] Szymanski, B.K., Chen, G., Branch, J.W., Zhu, L.: SENSE: Sensor network simulator and emulator (2007), http://www.cs.rpi.edu/ cheng3/sense/
[24] Kröller, A., Pfisterer, D., Buschmann, C., Fekete, S.P., Fischer, S.: Shawn: A new approach to simulating wireless sensor networks. In: Design, Analysis, and Simulation of Distributed Systems 2005 (DASD 2005), pp. 117–124 (2005)
[25] Pfisterer, D., Fischer, S., Kröller, A., Fekete, S.: Shawn: Ein alternativer Ansatz zur Simulation von Sensornetzwerken. Technical report, 4. Fachgespräch Drahtlose Sensornetze der GI/ITG-Fachgruppe Kommunikation und Verteilte Systeme (2005)
[26] Fekete, S.P., Kröller, A., Fischer, S., Pfisterer, D.: Shawn: The fast, highly customizable sensor network simulator. In: Proceedings of the Fourth International Conference on Networked Sensing Systems, INSS 2007 (2007) · doi:10.1109/INSS.2007.4297441
[27] Zhou, G., He, T., Krishnamurthy, S., Stankovic, J.A.: Impact of radio irregularity on wireless sensor networks. In: MobiSys 2004: Proceedings of the 2nd international conference on Mobile systems, applications, and services, pp. 125–138 (2004) · doi:10.1145/990064.990081
[28] Zhou, G., He, T., Krishnamurthy, S., Stankovic, J.A.: Models and solutions for radio irregularity in wireless sensor networks. ACM Trans. Sen. Netw. 2(2), 221–262 (2006) · doi:10.1145/1149283.1149287
[29] Coulouris, G., Dollimore, J., Kindberg, T.: Distributed Systems: Concepts and Design, 4th edn. Addison Wesley, Reading (2005) · Zbl 0848.68021
[30] Tanenbaum, A.S., Steen, M.V.: Distributed Systems: Principles and Paradigms. Prentice Hall PTR, Englewood Cliffs (2001) · Zbl 1157.68017
[31] Fischer, S., Luttenberger, N., Buschmann, C., Koberstein, J.: SWARMS: SoftWare Architecture for Radio-based Mobile Self-organizing Systems, DFG SPP 1140 (2002), http://www.swarms.de
[32] Fekete, S.P., Fischer, S., Kröller, A., Pfisterer, D.: SwarmNet: Algorithmen und Protokolle für Vernetzung und Betrieb großer Schwärme autonomer Kleinstprozessoren, DFG SPP 1126 (2003), http://www.swarmnet.de
[33] Spirakis, P., et al.: Foundations of Adaptive Networked Societies of Tiny Artefacts (FRONTS), Research Academic Computer Technology Institute, 7th Framework Programme on Research, Technological Development and Demonstration (2007)
[34] Fischer, S., et al.: Wireless sensornet test beds (WISEBED), Universität zu Lübeck, 7th Framework Programme on Research, Technological Development and Demonstration (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.