Top

Published in:

2011 | OriginalPaper | Chapter

18. Prolong the Lifetime of Wireless Sensor Networks Through Mobility: A General Optimization Framework

Authors : Jun Luo, Liu Xiang

Published in: Theoretical Aspects of Distributed Computing in Sensor Networks

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

Abstract

Though mobility is rarely considered in traditional wireless sensor networks (WSNs), actively exploiting mobility to improve the performance of WSNs has been increasingly recognized as an important aspect of designing WSNs. This chapter focuses on exploiting mobility to improve the network lifetime of a WSN. We present a general optimization framework that is able to capture several aspects of maximizing network lifetime (MNL) involving mobile entities. Based on this framework, we conduct an in-depth analysis on each of these aspects and also describe algorithms that can be used to solve the resulting optimization problems. We also present certain numerical results where engineering insights can be acquired.

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

previous chapter Dense, Concentric, and Non-uniform Multi-hop Sensor Networks

next chapter Information Spreading in Dynamic Networks: An Analytical Approach

In this chapter, the words sensor node and node are used interchangeably.

These are the entities that collect data from WSNs; sometimes they are also termed base stations.

The physical features of the radio of node i are usually specified by a tuple \((P_i,R,\mu)\); here P _i is the transmission power, R is the data rate, μ is the threshold (specified by the required bit error rate (BER) of a given modulation scheme that produces the rate R) such that a link \((i,j)\) may operate on rate R iff \(P_i\cdot\eta_{i,j} \ge \mu\), where \(\eta_{i,j}\) represents the fading, shadowing, and path loss effects between nodes i and j. Our model can be considered as a more generalized form of the aforementioned model, as \(e^\mathrm{T}_i = \dfrac{P_i}{R} \ge \dfrac{\mu}{R\eta_{i,j}} = c(i,j)\) is indeed the criterion to indicate the existence of link \((i,j)\). Note that, under our model, \(e^\mathrm{T}_i\) may have a unit of, for example, Joules/Bit.

This assumption is reasonable because each sensor node should be equipped with an energy source that is at least enough for the node to forward data for all nodes in one time unit. Otherwise if a node \(i:E_{i}/\left(e_{i}^\mathrm{T}+\mathrm{I}_{j\ne i}\cdot e^\mathrm{R}\right){<}\sum_{i}\lambda_{i}\) is deployed close to a static sink (assuming a randomly deployed WSN), the network lifetime can be even less than one time unit. In addition, it can be proved that an approximation ratio of \((1-\varepsilon)^{-3}\) is still achievable without this assumption.

The original work by Shi and Hou [30] is only designed for a single mobile sink. In this section, we extend their approach by combining it with MNL_ALGO presented in Sect. 18.2.4 to deal with multiple mobile sinks.

A byproduct of this change is that the cost assignment c is not needed anymore, as any link \((i,j)\) is feasible given a sufficiently high transmission energy \(e^\mathrm{T}_{i,j}\).

By aggregation, we refer to any transformation that summarizes or compresses the data acquired and received by a certain node and hence reduce the volume of the data to be sent out, e.g., [25].

As an example, the decision problem related to MNL (on-graph) is the following:

Instance: A set of nodes \(\mathcal{N}\), a cost assignment \(\mathbf{c}:c(i,j)=e, \forall i,j\in\mathcal{N}\), a set \(\mathcal{S}\) of sinks with \(|\mathcal{S}|{<}|\mathcal{N}|\), and for each \(i\in\mathcal{N}\), a transmission energy \(e_i^{\mathrm{T}}\), a receiving energy e ^R, an energy reserve E _i, a rate λ _i, and a positive real number t.
Question: Is there a sink layout schedule \(\{(\mathit{sl}_{k},t_{k})\}\) (\(\mathit{sl}_{k}\) is a vector of \([\delta^{k}_{is}]\) where \(\delta^{k}_{is}:\mathcal{N}\times\mathcal{S}\rightarrow\{0,1\}\) and \(\sum_{i}\sum_{s}\delta^{k}_{is}=|\mathcal{S}|\)) such that the lifetime \(T=\sum_{k}t_{k}\) is at least t?

This problem can be shown as NP-hard by, for example, a polynomial-time reduction from the Dominating Set on a unit disk graph [22].

Although Shi et al. [31] have proposed an approximation algorithm for BSP, using a technique similar to the one presented in Sect. 18.3.2.1 that algorithm is only pesudo-polynomial in time, as the time complexity is actually exponential in the number of base stations.

This is a special case of our general formulation, which assigns a uniform data rate to the source nodes and a zero rate to others.

The “many-to-one” data aggregation implies that, no matter how many unit of flows converge at an intermediate node, node only send one unit flow out. These are cases where special aggregation functions such as Average, Max, or Min are used.

I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. IEEE Communication Mag, 40(8):104–112, 2002.

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3): 544–562, 2004.MATHCrossRefMathSciNet

M.A. Batalin, M. Rahimi, Y. Yu, D. Liu, A. Kansal, G.S. Sukhatme, W.J. Kaiser, M.Hansen, G.J. Pottie, M.Srivastava, and D. Estrin. Call and Response: Experiments in sampling the Environment. In: Proceedings of the 2nd ACM SenSys, Baltimore, Maryland, USA, 2004.

A. Bogdanov, E. Maneva, and S. Riesenfeld. Power-aware base station positioning for sensor Networks. In: Proceedings of the 23rd IEEE INFOCOM, Hong Kong, China, 2004.

A. Chakrabarti, A. Sabharwal, and B. Aazhang. Using predictable observer mobility for power efficient design of sensor networks. In: Proceedings of the 2nd IEEE IPSN, Palo Alto, California, USA, 2003.

J.-H. Chang and L. Tassiulas. Energy conserving routing in wireless Ad-hoc networks. In Proceedings of the 19th IEEE INFOCOM, Tel Aviv, Israel, 2000.

I. Chatzigiannakis, A. Kinalis, S. Nikoletseas, and J. Rolim. Fast and energy efficient sensor data collection by multiple mobile sinks. In: Proceedings of the 5th ACM MobiWAC, Chania, Crete Island, Greece, 2007.

D.-Z. Du, Y. Zhang, and Q. Feng. On better heuristic for euclidian steiner minimum trees. In Proceedings of the 32nd IEEE FOCS, San Juan, Puerto Rico, 1991.

R.W. Floyd. Algorithm 97. Shortest path. Communications ACM, 5(6):345, 1962.CrossRef

10.

L.R. Ford and D.R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.MATH

11.

S.R. Gandham, M. Dawande, R. Prakash, and S. Venkatesan. Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In: Proceedings of IEEE Globecom, San Francisco, California, USA, 2003.

12.

M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, NY, 1979.MATH

13.

N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 38th IEEE FOCS, Miami Beach, Florida, USA, 1997.

14.

M. Grossglauser and D. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Transactions on Networking, 10(4):477–486, 2002.CrossRef

15.

Y. Gu, D. Bozda, E. Ekici, F. Ozguner, and C. Lee. Partitioning-based mobile element scheduling in wireless sensor networks. In: Proceedings of the 2nd IEEE SECON, Santa Clara, California, USA, 2005.

16.

H.S. Kim, T.F. Abdelzaher, and W.H. Kwon. Minimum energy asynchronous dissemination to mobile sinks in wireless sensor networks. In: Proceedings of the 1st ACM SenSys, Los Angeles, California, USA, 2003.

17.

A. Kinalis and S. Nikoletseas. Adaptive redundancy for data propagation exploiting dynamic sensory mobility. In: Proceedings of the 11th ACM MSWiM, 2008. Also in Journal of Interconnection Networks (JOIN), Vancouver, British Columbia, Canada, 2010.

18.

L. Li, J.Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In: Proceedings of the 20th ACM PODC, Newport, Rhode Island, USA, 2001.

19.

N. Li and J. Hou. Topology control in heterogeneous wireless networks: Problems and Solutions. In: Proceedings of the 23rd IEEE INFOCOM, Hong Kong, China, 2004.

20.

Q. Li, M. De Rosa, and D. Rus. Distributed algorithms for guiding navigation across a sensor network. In: Proceedings of the 9th ACM MobiCom, San Diego, California, USA, 2003.

21.

J. Luo and J.-P. Hubaux. Joint mobility and routing for lifetime elongation in wireless sensor networks. In: Proceedings of the 24th IEEE INFOCOM, Miami, Florida, USA, 2005.

22.

J. Luo and J.-P. Hubaux. Joint sink mobility and routing to increase the lifetime of wireless sensor networks: The case of constrained mobility. IEEE/ACM Transactions on Networking, 18(3), June 2010.

23.

J. Luo, J. Panchard, M. Piórkowski, M. Grossglauser, and J.-P. Hubaux. MobiRoute: Routing towards a mobile sink for improving lifetime in sensor networks. In: Proceedings of the 2nd IEEE/ACM DCOSS, San Francisco, California, USA, 2006.

24.

M. Ma and Y. Yang. SenCar: An energy-efficient data gathering mechanism for large-scale multihop sensor networks. IEEE Transactions on Parallel and Distributed Systems, 18(10):1478–1488, 2007.CrossRef

25.

S. Madden, M.J. Franklin, J. M. Hellerstein, and W. Hong. TAG: A tiny aggregation service for Ad-Hoc sensor networks. In: Proceedings of the 5th USENIX OSDI, Boston, MA, USA, 2002.

26.

G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, New York, NY, 1988.MATH

27.

V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE Journal on Selected Areas in Communications, 17(8):1333–1344, 1999.CrossRef

28.

R.C. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In: Proceedings of the 1st IEEE SNPA, Anchorage, Alska, USA, 2003.

29.

F. Shahrokhi and D.W. Matula. The maximum concurrent flow problem. Journal of ACM, 37(2):318–334, 1990.MATHCrossRefMathSciNet

30.

Y. Shi and Y.T. Hou. Theoretical results on base station movement problem for sensor Network. In Proceedings of the 27th IEEE INFOCOM, 2008.

31.

Y. Shi, Y.T. Hou, and A. Efrat. Algorithm design for a class of base station location problems in sensor networks. Springer Wireless Networks, 15(1):21–38, 2009.CrossRef

32.

A. Somasundara, A. Kansal, D.D. Jea, D. Estrin, and M.B. Srivastava. Controllably mobile infrastructure for low energy embedded networks. IEEE Transactions on Mobile Computing, 5(8):958–973, 2006.CrossRef

33.

A.A. Somasundara, A. Ramamoorthy, and M.B. Srivastava. Mobile element scheduling for efficient data collection in wireless sensor networks with dynamic deadlines. In: Proceedings of the 25th IEEE RTSS, Lisbon, Portugal, 2004.

34.

G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment. IEEE Transactions on Mobile Computing, 5(6):640–652, 2006.CrossRef

35.

W. Wang, V. Srinivasan, and K.-C. Chua. Using mobile relays to prolong the lifetime of wireless sensor networks. In: Proceedings of the 11th ACM MobiCom, Cologne, Germany, 2005.

36.

G. Xing, T. Wang, W. Jia, and M. Li. Rendezvous design algorithms for wireless sensor networks with a mobile base station. In: Proceedings of the 9th ACM MobiHoc, 2008.

37.

F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. A Two-Tier data dissemination model for large-scale wireless sensor networks. In: Proceedings of the 8th ACM MobiCom, Atlanta, Georgia, USA, 2002.

Title: Prolong the Lifetime of Wireless Sensor Networks Through Mobility: A General Optimization Framework
Authors: Jun Luo
Liu Xiang
Publisher: Springer Berlin Heidelberg
Book: Theoretical Aspects of Distributed Computing in Sensor Networks
Print ISBN: 978-3-642-14848-4

Electronic ISBN: 978-3-642-14849-1

Copyright Year: 2011
DOI: https://doi.org/10.1007/978-3-642-14849-1_18

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"

Premium Partner