Sink Node Mobility Patterns in Clusters based Wireless Sensor Networks

Sink Node Mobility Patterns in Clusters based Wireless Sensor Networks

Ms Seema Dahiya Dr. Pawan Kumar Singh

Ph. D Scholar ,SRM University Asst. Prof., ECE, SRM University

AbstractMaximization of network lifetime is one of the most important design goals in Wireless Sensor Networks (WSNs). In WSNs with static base stations, sensor nodes close to the base station dissipate most of their energies for relaying other sensor nodes data. Several clustering schemes, data routing algorithms and base station mobility schemes have been proposed by researchers to prolong the network lifetime. This paper analyzes the base station mobility scheme from the perspective of network energy efficiency and its impact on the network lifetime.

Index Terms Wireless sensor networks, cluster ratio, inherent transmission count, packet reception ratio, network lifetime, mobility patterns, optimal sink location, mobile robotics, mixed integer programming, energy efficiency.

1. INTRODUCTION

   A Wireless Sensor Network (WSN) consists of multiple form factor sensor nodes capable of sensing, data processing and wireless communication and play a key role in the Internet of Things (IoT) paradigm. Sensor nodes which perform sensing tasks such as monitoring a region have a limited battery energy and hence, a limited lifetime. It is widely accepted WSN research assumption that the base station operates without energy limitation. In a typical WSN deployment, a single base station performs the data collection while anchored at a stationary position which is usually chosen as the networks geometric center of gravity.

   One of the important design criteria in WSNs is the maximization of network lifetime. As the sensor nodes have limited energy, they become nonfunctional after their energy is depleted. Since it is not practical to replace the batteries of sensor nodes in the eld, development of efcient network strategies, energy efcient Media Access Control (MAC) and routing schemes that optimize the network lifetime by optimizing the energy dissipation is imperative.

   Furthermore, some research efforts have been made on exploring energy efcient network architectures. For example, Heinzelman et al. proposed a cluster-based communication

   protocol called Low-Energy Adaptive Clustering Hierarchy, which is the most well-known clustering scheme for WSNs. Recently, clustering schemes have been explored to enhance energy efciency and communication performance, as well as improve network scalability. Clustering schemes in WSNs can decrease the amount of transmitted trafc at a Cluster Head (CH) using data aggregation, and thus energy can be saved during data transmission. In addition, since nodes are managed as a cluster, the network becomes more robust and the overhead due to frequent topology changes is reduced. Prior research efforts in cluster- based WSNs indicate the importance of Cluster Ratio (CR), which is the ratio of the number of cluster-heads and the total number of nodes. These studies found that an improper choice of CR will result in extra energy dissipation, and thus an appropriate choice of CR is critical for enhancing the network lifetime. However, their results are only based on specic environments and transmission cases, and thus not applicable for general cluster-based WSNs.

   Also, repositioning the base station helps mitigating the hotspot problem in WSNs. Depending on the availability and feasibility, employing a mobile base station (e.g., a mobile robot acting as a base station) can improve the network lifetime signicantly when compared to a network with a static base station. The

   important research problem in this case is the determination of the base station mobility pattern.

   Nevertheless, it is shown that even random mobility of the base station can result in signicant network lifetime gains.

   In this paper, in section II (Model), researchers have integrated an exact mathematical programming model (MIP) with a heuristic search space (the mobility patterns) to characterize the impact of mobility patterns on WSN lifetime. And in section III, we analyze the effects of base station repositioning by using three mobility patterns (random, grid, and spiral). And in section IV we carry out conclusion part on optimal base station movement in cluster based WSNs to maximize the battery lifetime in a WSN network.

2. MODEL

   1. Problem Denition

      In this study, our main goal is to characterize the effects of neglected without leading to signican under estimation of total energy dissipation.

      three base station mobility patterns on WSN lifetime. In network model, there is a single mobile base station and NW sensor nodes with xed positions in the network. Data packets are forwarded as atomic data units (i.e., data packets are neither fragmented nor combined with other data packets until they reach the base station). The base station is allowed to reposition itself within a predetermined set of points which is denoted as Y (the number of points in set Y is denoted as NY). However, the base station is not forced to reside at each point (i.e., the base station can choose a subset of the available set of points to maximize the network lifetime). Furthermore, dwelling time of the base station at the selected points is not necessarily identical. The base station can stay at each selected point for different amounts of time for data collection and it is possible that some points are never used.

   2. Assumptions

      Researchers made the following assumptions:

      1. The base station has the complete topology information (e.g., node positions) and sufciently high processing and energy resources to perform the conict free transmission necessary computation for topology control and mobility planning in a centralized manner.

      2. Upon the completion of data collection at a given point the base station moves to the next point within a negligible amount of time.

      3. All nodes are roughly time synchronized. There are many synchronization protocols designed specically for WSNs with virtually no overhead and satisfactory synchronization performance. Time is organized into rounds and each round has a duration of Trnd = 1 minute. Each sensor node- i creates the same number of data packets periodically (si =1packet) and data packet length, LP, is 256 Bytes.

      4. Energy dissipation of sensor nodes is dominated

         by energy consumed on communication rather than computation. This assumption is supported by the results of experiments in actual WSN testbeds (e.g., it is reported in that communication energy dissipation constitutes more than 90 % of the total energy dissipation).

      5. Both the mobile base station dwelling time and the network reorganization period are sufciently long, therefore, the energy costs of topology discovery and route creation operations constitute a small fraction (e.g., less than 1.0 % ) of the total network energy dissipation. Therefore, control overhead can be

      6. A TDMA-based MAC layer is in operation which mitigates interference between active links through a time-slot assignment algorithm which outputs a

   schedule. C. Energy Model

   Researchers utilized the Mica2 platform communication energy dissipation characteristics which consists of an Atmel Atmega 128L processor and Chipcon CC1000 radio due to their well-characterized energy dissipation properties.

   Energy dissipation for transmission (per bit) at power level l is denoted as Etx(l) and the maximum transmission range at power level l is denoted as Rmax(l). he set of power levels is denoted as SL. Energy dissipation for reception (per bit) is constant

   (Erx =0 .922J). Each node chooses the optimal transmission power dynamically for each ow. The optimal power level for node- i to node-j to transmit over a distance dij is given in Equation 1.

   D. The MIP Model

   The network topology is represented by a directed graph, G

   =(V,A), where V is the universal set of all nodes (i.e., V = W Y ), which includes the set of sensor nodes (W) and the set of virtual base stations (Y ). In fact, the candidate positions of the mobile base stations are treated as distinct static base stations. Once a virtual base station is in active state, all sensor nodes send their data to that base station. Only one of the virtual base stations are active at any given time instance. Inactive virtual base stations are treated as if they do not exist during their periods of inactivity (i.e., they cannot participate in routing neither as a relay nor as a terminal point). Hence, researchers have dene sets Uk to dene the network consisting of all sensor nodes and the virtual base station-k (i.e., Uk = W k). This abstraction enables us to formulate the optimization problem in a more compact form. Links between the nodes are represented as an ordered set of arcs, A = {(i,j):i W,j V i}. Note that the denition of A implies that no node sends data to itself. Furthermore, we dene a set of arc (Ak = {(i,j):i

   rnd

   W,j Uk}) for each set Uk to ensure that all sensors data terminate at virtual base station-k when it is active. The set of selected virtual base stations is denoted as Z and each set Z has NZ members. For example, if there are a total of 49 virtual base stations (NY = 49) and only 7 of them are utilized throughout the network lifetime then NZ

   rnd.

   =7. Total number of data packets transmitted from nodei to node-j that is destined to the virtual base station-k is represented as fk ij.

   The optimization problem is formulated as a MIP

   problem which is presented in Figure 1. The objective is to maximize the lifetime (Lrnd) of the WSN, which is dened as the total number of rounds until the rst sensor node depletes its battery and dies. This denition should be interpreted correctly. If the framework is examined carefully it can be seen that all nodes are forced to dissipate their energies in a balanced fashion to maximize the lifetime, as a result,

   (from all the other sensor nodes) plus the data generated by node-i equals to the sum of data owing out of sensor node-i to the rest of the network (either to the virtual base station-k or to other sensor nodes acting as relays).All data terminates at the virtual base station-k. The total number of rounds that virtual base station-k is active is denoted by Lk and the total number of data packets generated by node-i destined for virtual base station-k is given by siLk Equation 4 gives the total energy used by each sensor node for data transmission and reception (ei). Equation 5 puts an upper limit on the energy used by each sensor node any node-i can dissipate at most battery amount of energy, where battery = 25 .0 kJ (total energy content of two AA batteries). Equation 6 is used to limit the maximum transmission range of each node, where Rmax(lmax) is the maximum transmission range possible. Equation 7 is used to dene the total lifetime of the network. In a broadcast medium, we need to make sure that the bandwidth required to transmit and receive at each node is lower than or equal to the total bandwidth. Such a constraint should take the shared capacity into consideration. We refer to the ows around node-i which are not incoming to or outgoing from node-i and affect the available bandwidth to node-i as interfering ows. Equation 8 presents the constraint for bandwidth. For each node which is a member of Uk the aggregate amount of incoming ows, outgoing ows, and interfering ows is upper bounded by the product of total active duration of virtual base station-k and the channel bandwidth (), where = 38 .4 Kbps for Mica2 motes. This constraint is a modied version of the sufcient condition given in

   [16]. Interference function (Ii ) is formulated in Equation 9.

   jm

   If node-i is in the interference region of the transmission from node-j to node-m, then the value of interference function

   for node-i (Ii ) is unity, otherwise it is zero. Generally

   Sensor nodes in the network collaborate altogether to avoid premature death of any sensor node due to over- utilization of its energy source. We also remind that the MIP framework researchers present in this study provides the optimal results by using global network information.

   Equation 2 states that all ows are non-negative. Equation 3 is used to balance the incoming and outgoing ows for each sensor node-i when virtual base station-k is active. It ensures that the sum of data incoming to sensor node-i

   jm

   speaking, interference range is equal to or greater than transmission range (i.e., 1). This means that, depending on the value of ( =1 .7 is used in this study), node-js transmission to node-m can interfere with node-i even if Rmax(lopt jm) is less than the distance between node-j and node-i.

   We note that in the numerical analysis, we choose the parameters affecting Equation 8 in such a way that the maximum value of the left hand side of the inequality is more than an order of magnitude less than the right hand side value, therefore, construction of a conict-free

   transmission schedule through a non-complicated time- slot assignment algorithm is possible.

3. ANALYSIS

   Researchers use General Algebraic Modeling System (GAMS) for the numerical analysis of the developed MIP model. In Figure 3, normalized network lifetimes and the number of utilized virtual base stations (NZ) as functions

   of NY (the number of available virtual base stations) are presented for random, grid, and spiral mobility patterns. Lifetime normalization is achieved by dividing all data points in each subgure by the largest lifetime value. The data points in the gures are the averages of randomly (uniform distribution) selected sensor node distributions (distributed over a square shaped sensing area) and virtual base station coordinates for random mobility patterns (i.e., MIP problem is solved for at least 100 times for each parameter set). Researchers employed three mobility patterns for the base station to follow which are random, grid, and spiral mobility patterns. Random mobility is the earliest mobility model for base station repositioning as an alternative to static sink. In random mobility, the members of the set Y is chosen from a uniform random distribution (i.e., there are NY candidate sink positions from which the sink chooses a subset of them). Grid mobility is an improvement over random mobility where the set Y consists of vertices of a grid. An alternative view of grid mobility is two dimensional regular sampling of the sensing domain. In spiral mobility, the set Y consists of points on a spiral shaped trajectory over the sensing domain which is centered at the networks geometrical center. The spiral shaped trajectory is generated by using Equation 10 and Equation 11, where the scaling constant is chosen as 0.085 and the interval variable is adjusted

   according to the size of the network. Spiral mobility can be interpreted as a non-regular sampling of the sensing domain (i.e., gradually decreasing density of the candidate base station positions). In Figure 2(a), Figure 2(b), and Figure 2(c), sample candidate base station positions for random, grid, and spiral mobility patterns, respectively, are

   Network lifetime increases for all mobility patterns as NY gets larger. However, the rate of increase in network lifetime gets smaller after a certain value of NY is reached. For example, normalized network lifetime values for spiral mobility are larger than 0.95 for NY

   16. The same trend also applies to grid and random motilities. his behavior can be explained by the principle of diminishing marginal returns. When compared to the case of a single static sink (i.e., Ny =1) all mobility patterns improve the network lifetime signicantly. The most dramatic increases are obtained for random mobility .For example, normalized life times obtained with random mobility in a 400×400 m2 network with NW = 100 for NY =1 , NY =9, and NY = 25 are 0.36, 0.81, and 0.90, respectively (Figure 3(i)). Unlike spiral and grid mobility patterns, in random mobility all virtual base station positions are determined randomly (i.e., in grid and spiral mobility for NY =1the base station positions are the geometric center of the network). Hence, in the extreme case the position of the single virtual base station can be on the network periphery for random mobility, which creates highly unbalanced energy dissipation patterns and lower network lifetime values. For spiral and grid mobility, the largest increases in lifetime when compared to the single static sink case is observed for smaller network areas. For example,

   normalized network lifetimes with NY =1and NW = 100 for grid mobility in 200×200 m2 (Figure 3(g)), 300×300 m2 (Figure 3(h)), and 400×400 m2 (Figure 3(i)) networks are 0.80, 0.60, and 0.54, respectively. The reason for such behavior is that the need for energy balancing through the use of base station mobility in larger sensing areas are more important (i.e., in smaller area networks sensor nodes can balance the energy dissipation more efciently when compared to larger area networks in lack of base station mobility). The general trend is that spiral mobility gives the largest network lifetimes and random mobility results in the lowest Network lifetimes. Grid mobility is in between spiral and random mobilities in terms of network lifetime. In sparser networks (i.e., number of nodes per unit area is lower) network lifetimes obtained by using spiral mobility is signicantly larger than the lifetimes obtained with grid and random mobilities. For example, in a 400×400 m2 network with NW = 50 and Ny = 36, normalized network lifetimes of spiral, grid, and random mobilities are 0.98, 0.78, and 0.75, respectively (Figure 3(c)). In denser networks, especially for larger Ny, the differences in network lifetimes are relatively insignicant (when compared to sparser networks). For example, in a 300 × 300 m2 network with NW = 100 and Ny = 49, normalized network lifetimes of spiral, grid, and random mobilities are 1.00, 0.98, and 0.95, respectively (Figure 3(h)). The number of

   the developed model, we explore the design space of WSNs with mobile base stations using spiral, grid, and random mobility patterns from the perspective of network lifetime. The results of our analysis show that spiral mobility results in longer network lifetimes than both grid and random mobility patterns. Network lifetimes obtained by using spiral mobility can be 35 % and 25 % more than the network lifetimes obtained by using random mobility and grid mobility, respectively. The reason for such a difference is that the trajectory of spiral mobility explores the sensing domain ner in lower radial distances from the geometric center of the network. This enables the mobile base station to nd the optimal positions to collect data from the sensor nodes in a way that maximizes the network lifetime. Our results also show that the number of base station positions do not need to be too large to prolong the network lifetime signicantly. In fact, by using less than ten base station repositioning steps it is possible to attain 99 % of the lifetime obtained with the maximum number of repositioning steps. Furthermore, it also possible to achieve

   90 % of the maximum lifetime with less than four repositioning steps by using spiral mobility.

   REFERENCES

   1. 2013 IEEE 24th International S ymposium on Personal, Indoor and Communications: Mobile

      utilized virtual base

      stations (NZ) increases as the

      Networks. Mobile Radio and Wireless

      number of available virtual base stations (Ny) increases for all mobility patterns. However, the rate of increase in NZ decreases as a function of Ny. For example, in a 300×300 m2 network with NW = 100 and random mobility, for Ny =4 , Ny =9 , Ny = 25, and Ny = 49, the number of utilized virtual base stations are 3.58, 5.87, 10.39, and 13.75, respectively (Figure 3(k)). The number of utilized virtual base stations for spiral mobility is larger than grid mobility, which in turn is larger than random mobility, as a general trend. Since the density of the virtual base station positions in spiral mobility gets higher as the radial distance towards the geometric center of the network decreases, it possible to employ a larger set of candidate positions as actual base station positions. However, in grid mobility, the density of virtual base station positions is uniform throughout the sensing area, hence, an important portion of the candidate positions, especially the ones closer to the periphery of the sensing area, are not optimal. Nevertheless, a higher density of candidate base station positions closer to the geometric center of the network is a better choice to prolong the network lifetime.

4. CONCLUSION

In this study, we saw a novel MIP framework to characterize the impact of base station mobility patterns on WSN lifetime and measured its performance on several scenarios.. By using

1. Z. Cheng, M. Perillo, and W. B. Heinzelman, General network lifetime and cost models for evaluating sensor network deployment strategies, IEEE Transactions on Mobile Computing, vol. 7, pp. 484497, 2008.

2. J. Luo and J.-P. Hubaux, Joint mobility and routing for lifetime elongation in wireless sensor networks, in Proc. Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 3, 2005, pp. 1735 1746.

3. IEEE SENSORS JOURNAL, VOL. 15, NO. 11,

   NOVEMBER 2015

4. 2009 International Conference on Computers and Devices for Communication