Reducing Latency In Data Delivery In Wireless Sensor Network With Mobile Elements

Reducing Latency In Data Delivery In Wireless Sensor Network With Mobile Elements

Rachana K, M.Tech II year, The Oxford College of Engineering,

Bangalore

B. Chempavathy, Asst. Professor, The Oxford College of Engineering,

Bangalore

Abstract: Introducing sink mobility to combat this lifetime issue has recently generated a lot of interest among the sensor network research community. But latency may increase due to relatively low speed of the mobile elements which results in buffer over flow and increase latency. We propose two approaches for reducing the latency in a wireless sensor network when there is a mobile sink and hence maximizing the lifetime of the network. The first approach is a stop and wait disk covering (SWDC) , in which it try to reduce the tour length of mobile element, thus the travel time. Second, it proposes a multi-hop SWDP scheme which jointly optimizes the sink trajectory and the packet routing paths. This paper focuses on studying the performance of the approaches proposed.

Index Terms Data collection, latency, mobile elements, wireless sensor network.

1. INTRODUCTION

   A wireless sensor network (WSN) typically consists of a sink node and a large number of sensor nodes, each of these gathers information from its vicinity and delivers information to the sink for further processing in multi-hop fashion. The sensor nodes operate with batteries and are often deployed in not easily accessible environments. It is difficult or impossible to replace the batteries of these sensor nodes. Since the sensor energy is the most precious resource in a WSN, efficient utilization of the energy to increase the network lifetime has been the focus of much of the research on WSNs.

   Data collection may suffer with the problems like wireless communication, especially long-range, may consume the energy of the sensor node, and in shorter range communication, due to data aggregation towards sink node nodes around the sink still have to consume much more energy than others due to heavier volumes of

   traffic transmitted by them, which leads to a lower overall network lifetime.

   Figure1. Wireless Sensor Network with Mobile Elements

   Much work has been done during recent years to increase the lifetime of a WSN (Figure 1). Among them taking advantage of often-available, controlled mobility of certain nodes, referred to as mobile elements, in the WSN has attracted much interest from researchers.

   WSN with mobile sink is given less importance than the static sink, although it has been demonstrated in [11][12] that a mobile sink can potentially increase the networks lifetime by causing lower saturation on the nodes around the sink due to its changing positions. Such a mobile sink may be a small vehicle, possibly unmanned, equipped with wireless transceiver. The vehicle may stop at specied locations where it can stop and collect data without obstructing other vehicles.

   Recently, [1] examined use of mobile sinks on delay tolerant sensor networks. However, the proposed algorithm is not easily adapted to a delay sensitive environment. The main contribution of this paper is the development of an efficient algorithm for a single mobile sink sensor network.

   The rest of the paper is organized as follows. Section II contains the related work with respect to WSN with mobile elements and statement of the problem. In Section III, we define the assumptions our approach. In Section IV, we present the approaches, which progressively reduce the tour length through combining, skipping and substitution. Experimental results are presented in Section V while Section VI concludes the paper and offers directions for future work.

2. RELATED WORK

   Many efforts have put to do research on various devices with different motilities in sensor networks to collect data from sensor nodes [1]-[5]. The three-tier network architecture for mobility in sensor networks is defined in [6]. The mobile entities, called Data Mobile Ubiquitous LAN Extensions (MULEs), lie in the middle tier on top of the stationary sensor nodes, move around in the network to collect data from sensor nodes, and ultimately upload the data to the sink or Base Station. The term Data MULEs was widely used in the literature since then.

   Based on the trajectory of the mobile sink, the sink mobility can be classified into three categories: random path, controllable path,

   and constrained path. In sensor networks where the path is random [6], [12], the mobile sinks are often mounted on some people or animals moving randomly to collect interested information sensed by the sensor nodes. Due to this type of mobility, it is difficult to estimate the data transfer latency and the data delivery ratio. On the other hand, it is possible to guarantee the data delivery efficiency with the help of efficient data collection schemes while the trajectories of the mobile sinks are constrained or controllable.

   Observing the importance of the tour selection for mobile elements, a lot of efforts were put into its optimal design [8], [9]. The mobility strategy following the periphery of the network coverage is found to be optimal in terms of balancing the communication loads among sensor nodes in [10], [20], [20]. In [11], the authors propose a framework of improving the network lifetime by taking advantage of not only sink mobility but also application delay tolerance. The resulting model is called Delay Tolerant Mobile Sink Model (DT-MSM). DT-MSM is suitable to those applications where some amount of delay in data delivery to the sink is permitted [6]. The sensor nodes may delay the transmission of the collected data and wait for the mobile sink to arrive at the location most favorable for improving the network lifetime.

   The tour selection problem with the consideration of the wireless communication range can be modeled as a Traveling Salesman Problem with Neighborhoods (TSPN) [14]. On the other hand, approximation algorithms do exist for certain cases of TSPN. For example, a

   constant-factor approximation algorithm was proposed in [14], where the neighborhoods are discrete objects of comparable diameters. In this project, the tour selection problem corresponds to another category of TSPN where the neighborhoods are intersecting continuous disks of the same size i.e., for a given communication range [17].

   In this project, first by following a stop and wait disk covering (SWDC) optimization approach, we try to reduce the tour length of mobile elements, thus the travel time with the assumption of a constant travel speed [13], [19]. The data sources can be either the ordinary sensor nodes in networks with a flat architecture, or the cluster heads in hierarchical networks. Second, it proposes a multi-hop SWDP (MH-SWDP) scheme which jointly optimizes the sink trajectory and the packet routing paths. In this scheme, the nodes aggregates the data towards the mobile sink using intermediate nodes (i.e., multi-hop) [16].

3. ASSUMPTIONS

   We assume the unit disk communication model in this ideal case, and the time required for data transfer between the mobile element and sensor nodes is negligible when compared with the travel time of the mobile element [6]. With this assumption, all the data collection jobs can be accomplished as long as the tour of the mobile element intersects with the communication disks of all sensor nodes. We call a tour feasible if all data collection

   jobs can be accomplished when the mobile element travels along it.

   Note that although this unit disk model may seem to be idealistic, measurement studis have showed that up to a certain distance from the sending sensor nodes, the packet reception rates are uniformly high [24]. This observation means that although simple, the unit disk model is still of practical value, e.g., we can carefully choose the communication range based on empirical experience or deployment measurements to keep the high reception rate. Furthermore, as mentioned in Section II, the simplification of excluding the communication time from consideration is reasonable when the to-be-transferred data volume is small.

4. PROPOSED TECHNIQUES

   1. Stop And Wait Disk Partitioning (SWDP) Approach

      In this section, we first consider a simplified case with a fixed communication range between the mobile element and sensor nodes without data-rate constraints to introduce the SWDP, and then evaluate and compare its performance through simulation.

      This scheme employs following phases. Step1: It divides the entire region into logical communication disks (sites) of unit area and create overlay graph using Algorithm1.

      Step 2: Find the tour: The different paths (Jobs) to visit all the sites are

      calculated. A schedule to collect data from all the sensor nodes is obtained. Although this schedule may exclude us from achieving the global optimal solution in some cases, it can reduce the search space and thus the computation complexity greatly, while guaranteeing a near-optimal performance.

      Step 3: Combine collection sites: It can combine several jobs, if we can replace several sensor sites with single collection site. This is done if the disk radius is less than the coverage range of the mobile element (Algorithm2).

      Step 4: Skipping: Sometimes data can be collected while the mobile element travelling along the tour. By taking advantage of this we can skip certain sites. The collected data is delivered to the base station (Algorithm3).

      Algorithm1 Partition Algorithm (N: a subset of sensors; r: communication range)

      1: radius; center ;

      2: (radius, center) = Partition(N); // Partition algorithm on S

      3: if radius > r then 4: return false;

      5: else

      6: return radius and center. 7: end if

      Algorithm 2 Combination Algorithm (N: the set of sensors; r: communication range)

      1: Tlength ;

      2: obtain the TSP tour for N and B: i.e., OTlength = {l0, l1, …, ln, l0};

      3: for all li (i = 1, 2, · · · , n 1) do

      4: find the maximum j i.e., no of sensor nodes ( i j n), such that all the locations in {li, li+1, …, lj} can be covered by a disk with radius no more than r, with center ci; 5: ComSet(i) {li, · · · , lj};

      6: end for

      Algorithm 3 Skip-and-Substitute Algorithm (Tcom: combined tour; r: communication range; :binary search threshold)

      1: TTlength ;

      2: for all li (i = 1, 2,…, n) do 3: if li is still on Tlength then 4: continue;

      5: end if

      6: start lj; end lj+1; 7: while |start, end| > do 9: q midpoint(start, end);

      10: if all collection sites that are in C(lilj)

      C(ljq) are also in C(liq) then 11: start q;

      12: else

      13: end q; 14: end if

      15: end while

      16: substitute {li+1, · · · , lj } by q in

      Tlength; 17: end for

      18: TTlength Tlength; 19: return TTlength.

   2. Multi-hop SWDP approach

      In this section, we consider a case where a data collection scheme based on the

      multi-hop communication is designed to improve the amount of data collected.

      In case of multi-hop SWDP (MH-SWDP)

      scheme.

      Step1: It divides the entire region into logical communication disks (sites) of unit area and create overlay graph using Algorithm1.

      Step2: It will elect a Rendezvous Node (RN) among them and algorithm is implemented to route the data from other nodes towards the RN (ANT colony optimization algorithm is used).

      Step3: The Mobile element is scheduled as in the stop and wait disk covering (SWDC) scheme.

5. SIMULATION

   A simulation is performed on set of network topologies with varying number of sensor nodes. The sink will be allowed to move over the network locations and the delay is calculated and the results are analysed.

   The parameters that are considered in the simulation are given in the table below.

   Parameters	Values
   Area	500*500 m
   No. of nodes	20,50
   Initial energy	500 J
   Communication range of each sensor nodes	5,6,7,8
   Transmission power	2mW
   Data generation rate	200kbps
   No. of sinks	1
   Waiting time at each collection site	5sec

   Parameters	Values
   Area	500*500 m
   No. of nodes	20,50
   Initial energy	500 J
   Communication range of each sensor nodes	5,6,7,8
   Transmission power	2mW
   Data generation rate	200kbps
   No. of sinks	1
   Waiting time at each collection site	5sec

   Table 1: Parameters used for simulation

   The SWDP and H-SWDP schemes described above are based on the case of a xed data amount K and a constant mobile element speed v. It is worth mentioning that both schemes can apply to the case of non-uniform data amount K and variable speed v(t).

   We evaluate the performance of the SWDP scheme and compare it with the existing algorithm (random mobility). We consider a sparse square sensing eld with size 500×500 m where nodes are uniformly deployed at random, and the constant speed of the mobile element is 2 m/s. We generate 50 random sets of network topology for each of the cases with 20, 50, 60, 70, 80, 90, and 100 sensor nodes, respectively. The SWDP scheme outperforms the Existing algorithm in terms of the resultant tour length noticeably, as shown in Figure 2

   Figure 2: Performance evaluation

   We also evaluate the performance of the SWDP scheme and compare it with the existing algorithm (random mobility). The MH-SWDP scheme also outperforms the

   Existing algorithm in terms of the resultant tour length, as shown in Figure 2.

6. CONCLUSION AND FUTURE WORK

In this paper, by following the proposed optimization approach, we have presented Stop and Wait Disk Partitioning (SWDP) scheme to reduce the tour length, and thus the data collection latency, in wireless sensor networks with mobile elements. We have also proposed a Multi-Hop SWDP scheme, which takes the advantage and reality of multi-hop wireless communications into account. Through an extensive simulation study, we can find that the proposed schemes can obtain results with lesser delay. Our future work will focus more on extending the schemes further to multiple mobile elements and the online scenarios of them, where the data collection requests arrive at the mobile elements progressively as well.

REFERENCES

[1]. X. Xu, J. Luo, and Q. Zhang, Delay tolerant event collection in Sensor networks with mobile sink, in Proceedings of IEEE INFOCOM10, 2010.

[2]. Y. Zhuang, J. Pan, and L. Cai, Minimizing energy consumption with probabilistic distance models in wireless sensor networks, in Proceedings of IEEE INFOCOM10, 2010.

[3]. J. Luo and J. Hubaux, Joint mobility and routing for lifetime elongation in wireless sensor networks, in Proceedings of IEEE INFOCOM05, 2005.

[4]. Analytical modeling and mitigation techniques for the energy hole problem in

sensor networks, Pervasive and Mobile Computin, vol. 3, no. 8, pp. 233254,

2007.

[5]. S. Gandham, M. Dawande, R. Prakash, and

S. Venkatesan, Energy efficient schemes for wireless sensor networks with multiple mobile base stations, in Global Telecommunications Conference, 2003. GLOBECOM 03. IEEE, December 2003.

[6]. R. C. Shah, S. Roy, S. Jain, and W. Brunette, Data MULEs: Modeling a three-tier architecture for sparse sensor networks, in the First IEEE International Workshop on Sensor Network Protocols and Applications, SNPA 2003, Anchorage, AK, May 2003, pp. 3041.

[7]. M. Ma and Y. Yang, SenCar: an energy-efficient data gathering mechanism for large-scale multihop sensor networks, IEEE Transaction on Parallel and Distributed System, vol. 18, no. 10, pp. 14761488, Oct. 2007.

[8]. J. Luo and J. Huabux, Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility, IEEE/ACM Transaction on Networking, vol. 18, no. 3, pp. 871884, 2010.

[9]. G. Xing, T. Wang, W. Jia, and M. Li, Rendezvous design algorithms for wireless sensor networks with a mobile base station, in Proceedings of ACM MobiHoc08, 2008.

[10].O. Tekdas, V. Isler, J. Lim, et al., Using mobile robots to harvest data from sensor fields, IEEE Wireless Communications, vol. 16, no. 1, pp. 2228, Feb. 2009.

[11].Y. Yun and Y. Xia, Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications, IEEE Transactions on Mobile Computing, vol. 9, no. 9, pp. 13081318, September

2010.

[12].S. Jain, R.C. Shah, W. Brunette, G. Borriello, and S. Roy, Exploiting Mobility for Energy Efficient Data Collection in

Sensor Networks, Mobile Networks and Applications, vol. 11, no. 3, pp. 327-339,

2006.

[13].S. Gandham, M. Dawande, R. Prakash, and

S. Venkatesan, Energy efcient schemes for wireless sensor networks with multiple mobile base stations, in Proc. IEEE GLOBECOM, vol. 1, 2003, pp. 377381.

1. Z. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, Exploiting sink mobility for maximizing sensor networks lifetime, in Proc. 38th HICSS, 2005.

2. I. Papadimitriou and L. Georgiadis, Maximum lifetime routing to mobile sink in wireless sensor networks, in Proc. SoftCOM, Sept. 2005.

[14].K. Elbassioni, A. Fishkin, and R. Sitters, On approximating the TSP with intersecting neighborhoods, in Proceedings of ISAAC06, 2006.

[15].C. Liao and S. Hu, Polynomial time approximation schemes for minimum disk cover problems, Journal of Combinatorial Optimization, vol. 20, no. 4, pp. 399412,

Nov. 2010

[16].J. Beardwood, J. Halton, and J. Hammersley, The shortest path through many points, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 55, no. 04, pp. 299327, 1959.

[17].C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed diffusion: A scalable and robust communication paradigm for sensor networks, in Proc. 6th ACM Int. Conf. MobiCom, Boston, MA, Aug. 2000, pp. 5667.

[18].E. Lawler, J. Lenstra, A. Kan, and D. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization, 1985.

[19].D. Goldenberg et al., Towards Mobility as a Network Control Primitive, Proc. ACM MobiHoc, 2004.

[20].Y. Gu et al., Partitioning Based Mobile Element Scheduling in Wireless Sensor Networks, Proc. SECON, 2005.

[21].I. Chatzigiannakis, A. Kinalis, and S. Nikoletseas, Sink Mobility Protocols for Data Collection in Wireless Sensor Networks, Proc. MOBIWAC, 2006.

[22].M. Wang et al., Exploiting Sink Mobility for Maximizing Sensor Networks Lifetime, Proc. Hawaii Intl. Conf.Sys. Sci., 2005.

[23].J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser, and J.-P. Hubaux, Mobiroute: Routing towards a mobile sink for improving lifetime in sensor networks, in Proc. DCOSS, 2006, pp. 480497.

[24].O. Chipara, et al., Real-time power-aware routing in sensor networks, in Proceedings of IEEE IWQoS06, 2006.

[25].J. Zhao and R. Govindan, Understanding packet delivery performance in dense wireless sensor networks, in Proceedings of ACM Sensys03, 2003.