Relay augmentation for lifetime extension of wireless sensor networks

Marcus Nathan Brazil; Charl John Ras; Doreen Anne Thomas

Relay augmentation for lifetime extension of wireless sensor networks

View Fulltext

Author(s): Marcus Nathan Brazil ¹ ; Charl John Ras ¹ ; Doreen Anne Thomas ²
- Affiliations: 1: Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC, 3010, Australia;
  2: Department of Mechanical Engineering, University of Melbourne, Parkville, VIC, 3010, Australia
Source: Volume 3, Issue 2, June 2013, p. 145 – 152
DOI: 10.1049/iet-wss.2012.0126 , Print ISSN 2043-6386, Online ISSN 2043-6394

Received 11/10/2012, Accepted 22/01/2013, Revised 14/01/2013, Published

The authors propose a novel relay augmentation strategy for extending the lifetime of a certain class of wireless sensor networks. In this class sensors are located at fixed and pre-determined positions and all communication takes place through multi-hop paths in a fixed routing tree rooted at the base station. It is assumed that no accumulation of data takes place along the communication paths and that there is no restriction on where additional relays may be located. Under these assumptions the optimal extension of network lifetime is modelled as the Euclidean k-bottleneck Steiner tree problem. Only two approximation algorithms for this NP-hard problem exist in the literature: a minimum spanning tree heuristic (MSTH) with performance ratio 2, and a probabilistic 3-regular hypergraph heuristic (3RHH) with performance ratio √3 + ɛ. The authors present a new iterative heuristic that incorporates MSTH and show through simulation that their algorithm performs better than MSTH in extending lifetime, and outperforms 3RHH in terms of efficiency.

References

1. 1)
  - 10. Brazil, M., Ras, C.J., Thomas, D.A.: ‘Approximating minimum Steiner point trees in Minkowski planes’, Networks, 2010, 56, pp. 244–254 (doi: 10.1002/net.20376).
2. 2)
  - 21. Wang, F., Wang, D., Liu, J.: ‘Traffic-aware relay node deployment for data collection in wireless sensor networks’. Proc. Sixth Annual IEEE Commun. Society Conf. on Sensor, Mesh and Ad Hoc Communications and Networks, 2009, pp. 351–359.
3. 3)
  - 20. Li, J.S., Kao, H.C., Ke, J.D.: ‘Voronoi-based relay placement scheme for wireless sensor networks’, IET Commun., 2009, 3, pp. 530–538 (doi: 10.1049/iet-com.2008.0204).
4. 4)
  - 6. Intanagonwiwat, C., Govindan, R., Estrin, D.: ‘Directed diffusion: a scalable and robust communication paradigm for sensor networks’. Proc. Sixth ACM Annual Int. Conf. on Mobile Computing and Networking, Boston, USA, August 2000, pp. 56–67.
5. 5)
  - 5. Boulis, A., Ganeriwal, S., Srivastava, M.B.: ‘Aggregation in sensor networks: an energy-accuracy trade-off’, Ad Hoc Netw., 2003, 1, pp. 317–331 (doi: 10.1016/S1570-8705(03)00009-X).
6. 6)
  - 17. Wang, Q., Zhang, T.: ‘Bottleneck zone analysis in energy-constrained wireless sensor networks’, IEEE Commun. Lett., 2009, 13, pp. 423–425 (doi: 10.1109/LCOMM.2009.090119).
7. 7)
  - 2. Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D., Anderson, J.: ‘Wireless sensor networks for habitat monitoring’. First ACM Int. Workshop on Wireless Sensor Networks and Applications, New York, USA, 2002, pp. 88–97.
8. 8)
  - 3. Cheng, X., Du, D.-Z., Wang, L., Xu, B.: ‘Relay sensor placement in wireless sensor networks’, Wirel. Netw., 2008, 14, pp. 347–355 (doi: 10.1007/s11276-006-0724-8).
9. 9)
  - 8. Lloyd, E.L., Xue, G.: ‘Relay node placement in wireless sensor networks’, IEEE Trans. Comput., 2007, 56, pp. 134–138 (doi: 10.1109/TC.2007.250629).
10. 10)
  - 11. Bredin, J.L., Demaine, E.D., Hajiaghayi, M.T., Rus, D.: ‘Deploying sensor nets with guaranteed capacity and fault tolerance’. Proc. Sixth ACM Int. Symp. on Mobile Ad Hoc Networking and Computing, New York, USA, 2005, pp. 309–319.
11. 11)
  - 18. Xin, Y., Guven, T., Shayman, M.: ‘Relay deployment and power control for lifetime elongation in sensor networks’, IEEE Int. Conf. Commun., 2006, 8, pp. 3461–3466.
12. 12)
  - 26. Bae, S.W., Choi, S., Lee, C., Tanigawa, S.: ‘Exact algorithms for the bottleneck Steiner tree problem’, Algorithmica, 2011, 61, pp. 924–947 (doi: 10.1007/s00453-011-9553-y).
13. 13)
  - 14. Bouabdallah, F., Bouabdallah, N., Boutaba, R.: ‘On balancing energy consumption in wireless sensor networks’, IEEE Trans. Veh. Technol., 2009, 58, pp. 2909–2924 (doi: 10.1109/TVT.2008.2008715).
14. 14)
  - 28. Lee, J.: ‘A first course in combinatorial optimization’ (Cambridge Texts in Applied Mathematics, Cambridge University Press, New York, 2004).
15. 15)
  - 25. Du, D.Z., Wang, L., Xu, B.: ‘The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points’. Seventh Annual Int. Conf. Computing and Combinatorics, Guilin, China, August 2001, pp. 509–518.
16. 16)
  - 4. Xu, K., Hassanein, H., Takahara, G., Wang, Q.: ‘Relay node deployment strategies in heterogeneous wireless sensor networks’, IEEE Trans. Mob. Comput., 2010, 9, pp. 145–159 (doi: 10.1109/TMC.2009.105).
17. 17)
  - 29. Promel, H.J., Steger, A.: ‘A new approximation algorithm for the Steiner tree problem with performance ratio 5/3’, J. Algorithms, 2000, 36, pp. 89–101 (doi: 10.1006/jagm.2000.1086).
18. 18)
  - 30. Gilbert, E.N., Pollak, H.O.: ‘Steiner minimal trees’, SIAM J. Appl. Math., 1968, 16, pp. 1–29 (doi: 10.1137/0116001).
19. 19)
  - 13. Bae, S.W., Lee, C., Choi, S.: ‘On exact solutions to the Euclidean bottleneck Steiner tree problem’, Inf. Proc. Lett., 2010, 110, pp. 672–678 (doi: 10.1016/j.ipl.2010.05.014).
20. 20)
  - 27. Brazil, M., Ras, C.J., Swanepoel, K., Thomas, D.A.: ‘Generalised k-Steiner tree problems in normed planes’. Submitted for publication, arXiv:1111.1464 [math.CO].
21. 21)
  - 16. Zhang, H., Shen, H.: ‘Balancing energy consumption to maximize network lifetime in data-gathering sensor networks’, IEEE Trans. Parallel Distrib. Syst., 2009, 20, pp. 1526–1539 (doi: 10.1109/TPDS.2008.252).
22. 22)
  - 19. Du, X., Liu, X., Xiao, Y.: ‘Density-varying high-end sensor placement in heterogeneous wireless sensor networks’, IEEE Int. Conf. Commun., 2009, pp. 1–6.
23. 23)
  - 24. Love, R.F., Wesolowsky, G.O., Kraemer, S.A.: ‘A multifacility minimax location method for Euclidean distances’, Int. J. Prod. Res., 2009, 11, pp. 37–45 (doi: 10.1080/00207547308929944).
24. 24)
  - 22. Sarrafzadeh, M., Wong, C.K.: ‘‘Bottleneck Steiner trees in the plane’, IEEE Trans. Comput., 1992, 41, pp. 370–374 (doi: 10.1109/12.127452).
25. 25)
  - 15. Kalpakis, K., Tang, S.: ‘A combinatorial algorithm for the maximum lifetime data gathering with aggregation problem in sensor networks’, Comput. Commun., 2009, 32, pp. 1655–1665 (doi: 10.1016/j.comcom.2009.06.007).
26. 26)
  - 1. Arampatzis, T., Lygeros, L., Manesis, J.S.: ‘A survey of applications of wireless sensors and wireless sensor networks’. Proc. 13th Mediterranean Conf. on Control and Automation, 2005, pp. 719–724.
27. 27)
  - 9. Brazil, M., Ras, C.J., Thomas, D.A.: ‘The bottleneck 2-connected k-Steiner network problem for k ≤ 2’, Discrete Appl. Math., 2012, 160, pp. 1028–1038 (doi: 10.1016/j.dam.2012.01.006).
28. 28)
  - 12. Wang, L., Du, D.Z.: ‘Approximations for a bottleneck Steiner tree problem’, Algorithmica, 2002, 32, pp. 554–561 (doi: 10.1007/s00453-001-0089-4).
29. 29)
  - 7. Krishnamachari, L., Estrin, D., Wicker, S.: ‘The impact of data aggregation in wireless sensor networks’. Proc. 22nd Int. Conf. on Distributed Computing Systems Workshops, Vienna, Austria, July 2002, pp. 575–578.
30. 30)
  - 23. Drezner, Z., Wesolowsky, G.O.: ‘A new method for the multifacility minimax location problem’, J. Oper. Res. Soc., 1978, 29, pp. 1095–1101.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Relay augmentation for lifetime extension of wireless sensor networks

References

Related content