Top

Wireless Networks

Published in:

01-07-2010

An approach for near-optimal distributed data fusion in wireless sensor networks

Authors: Damianos Gavalas, Aristides Mpitziopoulos, Grammati Pantziou, Charalampos Konstantopoulos

Published in: Wireless Networks | Issue 5/2010

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In wireless sensor networks (WSNs), a lot of sensory traffic with redundancy is produced due to massive node density and their diverse placement. This causes the decline of scarce network resources such as bandwidth and energy, thus decreasing the lifetime of sensor network. Recently, the mobile agent (MA) paradigm has been proposed as a solution to overcome these problems. The MA approach accounts for performing data processing and making data aggregation decisions at nodes rather than bring data back to a central processor (sink). Using this approach, redundant sensory data is eliminated. In this article, we consider the problem of calculating near-optimal routes for MAs that incrementally fuse the data as they visit the nodes in a WSN. The order of visited nodes (the agent’s itinerary) affects not only the quality but also the overall cost of data fusion. Our proposed heuristic algorithm adapts methods usually applied in network design problems in the specific requirements of sensor networks. It computes an approximate solution to the problem by suggesting an appropriate number of MAs that minimizes the overall data fusion cost and constructs near-optimal itineraries for each of them. The performance gain of our algorithm over alternative approaches both in terms of cost and task completion latency is demonstrated by a quantitative evaluation and also in simulated environments through a Java-based tool.

previous article Node distribution-based localization for large-scale wireless sensor networks

next article Optimal aggregation factor and clustering under delay constraints in aggregate sequential group paging schemes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Admittedly, the payload carried by the MA may practically remain constant as it migrates within the sensor field, given that an efficient fusion algorithm is applied (e.g. [29]). However, this scenario referred to as ‘full aggregation’ [24] only applies to a specific class of applications wherein sensory data exhibit high spatial redundancy so that MAs capability for performing progressive fusion can be exploited. In general, partial aggregation is observed for most applications [24]. On the other hand, NOID represents an itinerary scheduling method that generally applies to any data retrieval application, no matter whether spatial redundancy is present or not.

If, for instance, the deployed sensors monitor the atmospheric temperature within the sensor field and the data fusion task involves collecting the mean or maximum measured temperature, then f is very small (since the MA will carry a single temperature value at a time).

Post-order traversal (for each node v, visit the subtrees rooted at v, then visit v) is more efficient than pre-order (for each node v, visit v, then the subtrees rooted at v) or in-order (for each node v, visit a number of subtrees rooted at v, then visit v, then the rest of the subtrees rooted at v) traversal, as it shows to derive better total itinerary cost. Specifically, post-order traversal enables the MA to visit distant sensors first and leave sensors located close to the processing element for the end of the itinerary. Hence, the relatively ‘expensive’ migrations are performed when the MA has not yet collected many data; in the end of their itinerary, when MAs have already accumulated data from the previously visited sensors, they only have to perform short migrations. The cost efficiency of post-order against pre-order or in-order traversals has been experimentally verified through the simulator tool presented at Sect. 6.

In this approach, sensors comprising each sub-tree would be sorted in decreasing order in terms of their remaining energy level. The sensors with the lowest residual energy would be visited first, when the MA does not yet carry large amounts of data. Hence, the energy requirement for transmitting the MA to the next destination sensor would be minimized; sensors with sufficient energy availability would be left for the end of the MA’s itinerary.

NOID extends and adapts Esau-Williams algorithm in the specific requirements of agent itinerary planning problem. To the best of our knowledge, there is no distributed implementation of the Esau-Williams algorithm. Essentially, this algorithm builds a spanning tree whose subtrees have bounded weight. Distributed algorithms for building spanning trees exist in the literature. The simplest algorithm is to build a breadth -first search tree [25] simply by flooding a message from the root of the tree. However, these approaches, similarly to more recent approaches, [21] are associated with high message overhead, hence high energy cost in WSNs.

Sun Microsystems’ SunSPOTs are equipped with an ARM920T 180 MHz processor, 4 MByte Flash memory and lifetime of 7 h to 909 days, depending on the CPU usage. Crossbow’s MICA2 motes are equipped with an ATmega128L 8 MHz CPU, program memory of 128 KB, external storage of 512 KB and 450 days lifetime (when their duty cycle is 1% on average).

Akyildiz, F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114.CrossRef

Al-Hammouri, A., Zhang, W., Buchheit, R., Liberatore, V., Chrysanthis, P., & Pruhs, K. (2006). Network awareness and application adaptability. Information Systems and E-Business Management, 4(4), 399–419.CrossRef

Baumann, J., Hohl, F., Radouniklis, N., Rothermel, K., & Strabetaer, M. (1997). Communication concepts for mobile agent systems. In Proceedings of the 1st international workshop on mobile agents (MA ‘97) (pp. 123–135).

Boulis, A. (2005). Programming sensor networks with mobile agents. In Proceedings of the 6th international conference on mobile data management (MDM’2005) (pp. 252–256).

Boulis, A., Han, C., & Srivastava, M. (2003). Design and implementation of a framework for efficient and programmable sensor networks. In Proceedings of ACM MobiSys’03 (pp. 187–200).

Chen, M., Kwon, T., & Choi, Y. (2005). Data dissemination based on mobile agent in wireless sensor networks. In Proceedings of the 30th IEEE conference on local computer networks (LCN’05) (pp. 527–529).

Chen, M., Gonzalez, S., & Leung, V. C. M. (2007). Applications and design issues for mobile agents in wireless sensor networks. IEEE Wireless Communications, 14(6), 20–26.CrossRef

Cristescu, R., Beferull-Lozano, B., Vetterli, M., & Wattenhofer, R. (2006). Network correlated data gathering with explicit communication: NP-completeness and algorithms. IEEE/ACM Transactions on Networking, 14(1), 41–54.CrossRef

Esau, L. R., & Williams, K. C. (1966). On teleprocessing system design, Part II—a method for approximating the optimal network. IBM Systems Journal, 5, 142–147.CrossRef

10.

Fok, C. L., Roman, G. C., & Lu, C. (2005). Rapid development and flexible deployment of adaptive wireless sensor network applications. In Proceedings of the 25th international conference on distributed computing systems (ICDCS’2005) (pp. 653–662).

11.

Fuggeta, A., Picco, G. P., & Vigna, G. (1998). Understanding code mobility. IEEE Transactions on Software Engineering, 24(5), 346–361.CrossRef

12.

Gao, J. L. (2002). Analysis of energy consumption for ad hoc wireless sensor networks using a bit-meter-per-joule metric. In IPN Progress Report 42-150 (http://ipnpr.jpl.nasa.gov/progress report/42-150/150L.pdf).

13.

Gavalas, D. (2001). Mobile software agents for network monitoring and performance management. PhD Thesis, University of Essex, UK.

14.

Gavalas, D., Greenwood, D., Ghanbari, M., & O’Mahony, M. (2002). Hierarchical network management: A scalable and dynamic mobile agent-based approach. Computer Networks, 38(6), 693–711.CrossRef

15.

Gavalas, D., Pantziou, G., Konstantopoulos, C., & Mamalis, B. (2006). A method for incremental data fusion in distributed sensor networks. In Proceedings of the 3rd IFIP conference on artificial intelligence applications & innovations (AIAI’2006) (pp. 635–642).

16.

Georgoulas, D., & Blow, K. (2007). In-Motes Bins: A real time application for environmental monitoring in wireless sensor networks. In Proceedings of the 9th IEEE/IFIP international conference on mobile and wireless communications networks (MWCN’2007) (pp. 21–26).

17.

Iqbal, A., Baumann, J., & Straßer, M. (1998). Efficient algorithms to find optimal agent migration strategies. Universität Stuttgart, Fakultät Informatik, Bericht Nr. 1998/05.

18.

Java Native Interface, http://java.sun.com/j2se/1.5.0/docs/guide/jni/index.html.

19.

Jiao, Y., & Hurson, A. R. (2005). Adaptive power management for mobile agent-based information retrieval. In Proceedings of the 19th international conference on advanced information networking and applications (AINA’05) (pp. 675–680).

20.

Kershenbaum, A. (1993). Telecommunications network design algorithms. New York: McGraw-Hill.

21.

Kutten, S., & Peleg, D. (1998). Fast distributed construction of k-dominating sets and applications. Journal of Algorithms, 28, 40–66.MATHCrossRefMathSciNet

22.

Lange, D. B., & Oshima, M. (1999). Seven good reasons for mobile agents. Communications of the ACM, 42(3), 88–89.CrossRef

23.

Lotfinezhad, M., & Liang, B. (2005). Energy efficient clustering in sensor networks with mobile agents. In Proceedings of the IEEE wireless communications and networking conference (WCNC’05).

24.

Luo, H., Liu, Y., & Das, S. K. (2007). Routing correlated data in wireless sensor networks: A survey. IEEE Network, 21(6), 40–47.CrossRef

25.

Lynch, N. (1996). Distributed algorithms. San Francisco, California: Morgan Kauffmann.MATH

26.

Milojicic D. (1999). Mobile agent applications. IEEE concurrency, 7(3), 80–90.CrossRef

27.

Mpitziopoulos, A., Gavalas, D., Konstantopoulos, C., & Pantziou, G. (2009). Mobile agent middleware for autonomic data fusion in wireless sensor networks. In M. K. Denko, L. T. Yang, & Y. Zhang (Eds.), Autonomic computing and networking, chapter 3 (pp. 57–81). USA: Springer.CrossRef

28.

Picco, G. P. (2001). Mobile agents: An introduction. Microprocessors and Microsystems, 25(2), 65–74.CrossRef

29.

Qi, H., Iyengar, S. S., & Chakrabarty, K. (2001). Multi-resolution data integration using mobile agents in distributed sensor networks. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 31(3), 383–391.CrossRef

30.

Qi, H., & Wang, F. (2001). Optimal itinerary analysis for mobile agents in ad hoc wireless sensor networks. In Proceedings of the13th international conference on wireless communications (Wireless’2001) (pp. 147–153).

31.

Reuter, E., & Baude, F. (2002). System and network management itineraries for mobile agents. In Proceedings of the 4th international workshop on mobile agents for telecommunication applications (MATA’02), LNCS (Vol. 2521, pp. 227–238).

32.

Rubinstein, M. G., Duarte, O. C., & Pujolle, G. (2003). Scalability of a mobile agents based network management application. Journal of Communications and Networks, 5(3), 240–248.

33.

Shih, D. H., Huang, S. Y., & Yen, D. C. (2005). A new reverse auction agent system for m-commerce using mobile agents. Computer Standards & Interfaces, 27(4), 383–395.CrossRef

34.

Solis, I., & Obraczka, K. (2004). The impact of timing in data aggregation for sensor networks. In Proceedings of IEEE international conference on communications (ICC’04) (pp. 3640–3645).

35.

Tseng, Y. C., Kuo, S. P., Lee, H. W., & Huang, C. F. (2004). Location tracking in a wireless sensor network by mobile agents and its data fusion strategies. Computer Journal, 47(4), 448–460.CrossRef

36.

Umezawa, T., Satoh, I., & Anzai, Y. (2002). A mobile agent-based framework for configurable sensor networks. In Proceedings of the 4th international workshop on mobile agents for telecommunications applications (MATA’02) (pp. 128-140).

37.

Vazirani, V. (2001). Approximation algorithms. Berlin: Springer.

38.

Wong, K. F. S., Tsang, I. W., Cheung, V., Chan, S. H. G, & Kwok, J. T. (2005). Position estimation for wireless sensor networks. In Proceedings of the 2005 IEEE Global Communications Conference (Globecom’2005).

39.

Wu, Q., Rao, N., Barhen, J., Iyengar, S., Vaishnavi, V., Qi, H., et al. (2004). On computing mobile agent routes for data fusion in distributed sensor networks. IEEE Transactions on Knowledge and Data Engineering, 16(6), 740–753.CrossRef

40.

Xu, Y., & Qi, H. (2004). Distributed computing paradigms for collaborative signal and information processing in sensor networks. Journal of Parallel and Distributed Computing, 64(8), 945–959.MATHCrossRef

41.

Xu, Y., & Qi, H. (2008). Mobile agent migration modeling and design for target tracking in wireless sensor networks. Ad Hoc Networks, 6(1), 1–16.MATHCrossRef

42.

Yuan, W., Krishnamurthy, S., & Tripathi, S. (2003). Synchronization of multiple levels of data fusion in wireless sensor networks. In Proceedings of the 46th IEEE global telecommunications conference (Globecom’03) (pp. 221–225).

Title: An approach for near-optimal distributed data fusion in wireless sensor networks
Authors: Damianos Gavalas
Aristides Mpitziopoulos
Grammati Pantziou
Charalampos Konstantopoulos
Publication date: 01-07-2010
Publisher: Springer US
Published in: Wireless Networks / Issue 5/2010
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI: https://doi.org/10.1007/s11276-009-0211-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2010

A networked mobile sensor test-bed for collaborative multi-target tracking applications

Semantic-based resource discovery, composition and substitution in IEEE 802.11 mobile ad hoc networks

Numerical analysis of hardware architecture for header compression and packet aggregation on wireless networks

Optimal network selection in heterogeneous wireless multimedia networks

Approximation algorithm for minimal convergecast time problem in wireless sensor networks

Optimal transmission methodology for QoS provision of multi-hop cellular network