This paper presents a task allocation-oriented framework to enable efficient in-network processing and cost-effective multi-hop resource sharing for dynamic multi-hop multimedia wireless sensor networks with low node mobility, e.g., pedestrian speeds. The proposed system incorporates a fast task reallocation algorithm to quickly recover from possible network service disruptions, such as node or link failures. An evolutional self-learning mechanism based on a genetic algorithm continuously adapts the system parameters in order to meet the desired application delay requirements, while also achieving a sufficiently long network lifetime. Since the algorithm runtime incurs considerable time delay while updating task assignments, we introduce an adaptive window size to limit the delay periods and ensure an up-to-date solution based on node mobility patterns and device processing capabilities. To the best of our knowledge, this is the first study that yields multi-objective task allocation in a mobile multi-hop wireless environment under dynamic conditions. Simulations are performed in various settings, and the results show considerable performance improvement in extending network lifetime compared to heuristic mechanisms. Furthermore, the proposed framework provides noticeable reduction in the frequency of missing application deadlines.
References
[1]
Madden, S.; Levis, P. Mesh networking research and technology for multihop wireless networks. IEEE Internet Comput. 2008, 12, 9–11.
Olsen, A.B. Energy Aware Computing in Cooperative Wireless Networks. Proceedings of 2005 International Conference on Wireless Networks, Communications and Mobile Computing, Maui, HI, USA, 13–16 June 2005; pp. 16–21.
[4]
Burke, J. Participatory Sensing. Proceedings of Workshop on World-Sensor-Web: Mobile Device Centric Sensor Networks and Applications (WSW 2006), Boulder, Colorado, USA, 31 October–3 November 2006; pp. 117–134.
[5]
AlShahwan, F.; Moessner, K.; Carrez, F. Distributing Resource Intensive Mobile Web Services. Proceedings of 2011 International Conference on Innovations in Information Technology (IIT 2011), Al Abu Dhabi, United Arab Emirates, 25–27 April 2011; pp. 41–46.
[6]
Dieber, B.; Micheloni, C.; Rinner, B. Resource-aware coverage and task assignment in visual sensor networks. IEEE Trans. Circuits Sys. Video Technol. 2011, 21, 1424–1437.
Akyildiz, I.; Melodia, T.; Chowdury, K. Wireless multimedia sensor networks: A survey. IEEE Wirel. Commun. 2007, 14, 32–39.
[9]
Sato, N.; Matsuno, F.; Yamasaki, T.; Kamegawa, T.; Shiroma, N.; Igarashi, H. Cooperative Task Execution by A Multiple Robot Team and Its Operators in Search and Rescue Operations. Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004), Sendai, Japan, 8 September–2 October 2004; pp. 1083–1088.
[10]
Xiao, W.; Low, S.M.; Tham, C.K.; Das, S. Prediction Based Energy-Efficient Task Allocation for Delay-Constrained Wireless Sensor Networks. Proceedings of 6th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks Workshops (SECON Workshops 2009), Rome, Italy, 22–26 June 2009; pp. 1–3.
[11]
Tian, Y.; Ekici, E. Cross-layer collaborative in-network processing in multihop wireless sensor networks. IEEE Trans. Mob. Comput. 2007, 6, 297–310.
[12]
Tracy, D.B.; Howard, J.S.; Noah, B.; Ladislau, L.B.; Muthucumaru, M.; Albert, I.R.; James, P.R.; Mitchell, D.T.; Bin, Y.; Debra, H.; Richard, F.F. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 2001, 61, 810–837.
[13]
Jin, Y.; Jin, J.; Gluhak, A.; Moessner, K.; Palaniswami, M. An intelligent task allocation scheme for multihop wireless networks. IEEE Trans. Parallel Distrib. Sys. 2012, 23, 444–451.
[14]
Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning; Addison-Wesley Longman Publishing Co., Inc.: Boston, MT, USA, 1989.
[15]
Page, A.J.; Keane, T.M.; Naughton, T.J. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J. Parallel Distrib. Comput. 2010, 70, 758–766.
Xie, T.; Qin, X. An energy-delay tunable task allocation strategy for collaborative applications in networked embedded systems. IEEE Trans. Comput. 2008, 57, 329–343.
[18]
Yuan, T.; Ekici, E.; Ozguner, F. Cluster-based information processing in wireless sensor networks: an energy-aware approach: Research articles. Wirel. Commun. Mob. Comput. 2007, 7, 893–907.
[19]
Yu, Y.; Prasanna, V.K. Energy-Balanced Task Allocation for Collaborative Processing in Networked Embedded Systems. Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems (LCTES 2003), San Diego, CA, USA, 11–13 June 2003; pp. 265–274.
[20]
Jin, Y.; Wei, D.; Gluhak, A.; Moessner, K. Latency and Energy-Consumption Optimized Task Allocation in Wireless Sensor Networks. Proceedings of 2010 IEEE Wireless Communications and Networking Conference (WCNC 2010), Sydney, Australia, 18–21 April 2010; pp. 1–6.
[21]
Pezoa, J.; Dhakal, S.; Hayat, M. Maximizing service reliability in distributed computing systems with random node failures: Theory and implementation. IEEE Trans. Parallel Distrib. Sys. 2010, 21, 1531–1544.
[22]
Tian, Y.; Boangoat, J.; Ekici, E.; Ozguner, F. Real-Time Task Mapping and Scheduling for Collaborative in-Network Processing in DVS-Enabled Wireless Sensor Networks. Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Rhodes Island, Greece, 25–29 April 2006; p. p. 10.
[23]
Chen, Y.; Guo, W.; Chen, G. A Dynamic-Alliance-Based Adaptive Task Allocation Algorithm in Wireless Sensor Networks. Proceedings of 9th International Conference on Grid and Cooperative Computing (GCC 2010), Nanjing, Jiangsu, China, 1–5 November 2010; pp. 356–360.
[24]
Aghera, P.; Krishnaswamy, D.; Fang, D.; Coskun, A.; Rosing, T. DynAHeal: Dynamic Energy Efficient Task Assignment for Wireless Healthcare Systems. Proceedings of Design, Automation Test in Europe Conference Exhibition (DATE 2010), Dresden, Germany, 8–12 March 2010; pp. 1661–1664.
[25]
Rajendran, V.; Obraczka, K.; Garcia-Luna-Aceves, J.J. Energy-Efficient Collision-Free Medium Access Control for Wireless Sensor Networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA, 5–7 November 2003; pp. 181–192.
Meghanathan, N. Location Prediction Based Routing Protocol for Mobile Ad Hoc Networks. Proceedings of Global Telecommunications Conference (GLOBECOM 2008), New Orleans, LA, USA, 30 November–4 December 2008; pp. 1–5.
[28]
Heinzelman, W.; Chandrakasan, A.; Balakrishnan, H. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun. 2002, 1, 660–670.
[29]
Balakrishnan, H.; Barrett, C.L.; Kumar, V.S.A.; Marathe, M.V.; Thite, S. The distance-2 matching problem and its relationship to the MAC-Layer capacity of ad hoc wireless networks. IEEE J. Sel. Areas Commun. 2004, 22, 1069–1079.
