INTRODUCTION
|
| Sensors are hardware devices that produce measurable response to a change in a physical condition like temperature and pressure. Sensors sense or measure physical data of the area to monitored. The continual analog signal sensed by the sensors is digitized by an Analog-to-digital converter and sent to controllers for further processing. Characteristics and requirements of Sensor node should be small size, consume extremely low energy, operate in high volumetric densities, are autonomous and operate unattended, and be adaptive to the environment. As wireless sensor nodes are micro-electronic sensor device, can only be equipped with a limited power source of less than 0.5 Ah and 1.2 V. Sensors are classified into three categories. |
| • Passive, Omni Directional Sensors: Passive sensors sense the data without actually manipulating the environment by active probing. They are self powered i.e energy is needed only to amplify their analog signal. There is no notion of “direction” involved in these measurements. |
| • Passive, narrow-beam sensors: These sensors are passive but they have well-defined notion of direction of measurement. Typical example is ‘camera’. |
| • Active Sensors: These group of sensors actively probe the environment, for example, a sonar or radar sensor or some type of seismic sensor, which generate shock waves by small explosions. |
| The overall theoretical work on WSN’s considers Passive, Omni directional sensors. Each sensor node has a certain area of coverage for which it can reliably and accurately report the particular quantity that it is observing. Several sources of power consumption in sensors are a) Signal sampling and conversion of physical signals to electrical ones, b) signal conditioning, and c) analog-to-digital conversion. Spatial density of sensor nodes in the field may be as high as 20 nodes/ m3.A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control. In addition to one or more sensors, each node in a sensor network is typically equipped with a radio transceiver or other wireless communications device, a small microcontroller, and an energy source, usually a battery. The envisaged size of a single sensor node can vary from shoebox-sized nodes down to devices the size of grain of dust, although functioning 'motes' of genuine microscopic dimensions have yet to be created. The cost of sensor nodes is similarly variable, ranging from hundreds of dollars to a few cents, depending on the size of the sensor network and the complexity required of individual sensor nodes. Size and cost constraints on sensor nodes result in corresponding constraints on resources such as energy, memory, computational speed and bandwidth. A sensor network normally constitutes a wireless ad-hoc network, meaning that each sensor supports a multi-hop routing algorithm. In computer science and telecommunications, wireless sensor networks are an active research area with numerous workshops and conferences arranged each year. |
II. RELATED WORK
|
| Mobility management is one of the most important issues in wireless networks, and it has received extensive research efforts in different areas of wireless networks such as mobile ad hoc network (MANET), wireless mesh network, vehicular ad hoc network, and so on. Recently, there is a trend to investigate mobility as a means of relieving traffic burden and enhancing energy efficiency in WSN [8]. We can classify sink mobility into two categories: random mobility and controlled mobility. Sinks in the first category move randomly within the network. Schemes based on random mobility are easy to implement, but they suffer from shortcomings like uncontrolled behaviors and poor performance. Recent research tends to use controlled mobility to improve the performance. The hardcore is to jointly schedule different issues (e.g., sink mobility, data routing, information delay, and so on.) to optimize the network lifetime. |
| For this paradigm, Gandham et al. first challenged this problem and proposed a heuristic algorithm. Wang et al. relaxed the problem by doing the sink scheduling and data routing separately, and their proposed routing scheme can work only in a grid network topology. Guney et al. also studied the problem and proposed several greedy algorithms [4]. Recently, Shi and Hou developed the first algorithm with performance guarantee with a single sink. Liang et al. extended Shi’s work by considering issues like multiple sinks and the maximum number of hops from each sensor to a sink. A threestage heuristics has been developed to find high-quality trajectory for each sink as well as the actual sojourn time at each sojourn location [5]. In our recent research [10], we proposed a generalized column generation based algorithm that can be applied to a set of sink mobility problems with near-optimal performance. |
| In above proposals, they assume that sinks are high speed so that information delay caused by moving the sink can be ignored. However, on the one hand, mobile sinks in physical worlds usually have limited speed. On the other hand, underlay applications like the real-time surveillance demand a delay upper bound. Therefore, it is natural to take the delay issue into consideration. |
| Basagni et al. jointly considered the sink mobility and delay. But they assumed that the routes are predetermined. Wang et al. used multiple controllable sinks to travel among event locations to efficiently gather data. They considered issues like the mobile distance of a sink and time delay [7]. However, only one-hop routing has been used. |
| Recently, Yun and Xia [11] jointly considered the multihop routing, sink mobility, and delay bound to improve the energy efficacy. They still used the fast mobility assumption [1], so the delay is caused by nodes holding their transmissions until the location of the sink is most favorable for energy saving, not by the movement of the sink. |
| Keung et al. studied the message delivery capacity problem in delay-constrained mobile sensor networks where the sink nodes are static while sensor nodes are mobile [9], [3]. They focused on maximizing the percentage of sensing messages that can be successfully delivered to sink nodes within a given time constraint. Their network model is fundamentally different with ours and is somehow similar to the DTN. |
| Recently, there are some interesting results to further improve the performance of a mobile sink in WSNs. For example, Li et al. [12] presented a localized geographic routing scheme to ensure the data delivery to the mobile sink in a WSN. Ota et al. [13] proposed an event prediction scheme to predict an event from collected sensory data by studying the mobile sinks’ mobility control in wireless sensor and actor networks. |
| In our previous study [14], we also addressed the problem of lifetime maximization with delay bound in a mobile WSN. The major improvements of this paper over the previous one are twofold. First, we present some new theoretical results like the connectivity analysis of a WSN. Second, we design a set of new simulations to study the effects of different trajectories of the sink and provide important insights for designing mobility schemes in real world mobile WSNs. |
III. DATA COLLECTION USING MOBILE SINKS
|
| In the past decades, wireless sensor network (WSN), one of the fastest growing research areas, has been attracted a lot of research activities. Due to the maturity of embedded computing and wireless communication techniques, significant progress has been made. Typically, a WSN consists of a data collection unit (also known as sink or base station) and a large number of sensors that can sense and monitor the physical world, and thus it is able to provide rich interactions between a network and its surrounding physical environment in a real-time manner [2]. |
| The capacity-limited power sources of small sensors constrain us from fully benefitting from WSNs. Due to the unique many-to-one (converge-cast) traffic patterns, the traffic of the whole network will be converged to a specific set of sensor nodes (e.g., neighboring nodes of the sink) and results in the hotspot problem. Much research effort has been dedicated to resolve this issue, for example, energy efficient communication protocols [6], multisink systems. However, as long as the sink and sensor nodes are static, this issue cannot be fully tackled. Therefore, there is a recent trend to exploit mobility of the sink as a promising approach to the hotspot problem [8]. |
| By the way of using sink mobility, we can classify them into two categories: random mobility based and controlled mobility based. For the first category, the sink is designed to move randomly within the network. For example, Rahul et al. presented an architecture on which mobile entities (named MULEs) pick up data from sensors when in close range in sparse sensor networks. Schemes based on random mobility are straightforward and easy to implement. However, they suffer from shortcomings like uncontrolled behaviors and poor performance. Hence, recent research resorts to controlled mobility to improve the performance. |
| For the controlled mobility, the key problem is to deterministically schedule the sink to travel around the network to collect data. It is shown that by properly setting the trajectory even limited mobility would significantly improve the network lifetime. However, the mobility also brings new issue, i.e., the delay of the data delivery caused by the movement of the sink. Some previous proposals tried to avoid this issue by considering the so called fast mobility, whereas the speed of the sink are sufficiently high so that the resulting delay can be tolerated [1]. While others address this delay-bounded mobility problem by heuristics with little theoretical understanding. |
| To this end, we study the delay-bounded sink mobility problem (DeSM) of WSNs in this paper. We assume that WSNs are deployed to monitor the surrounding environment and the data generation rate of sensors can be estimated accurately. We constrain the mobile sink to a set of sink sites. First, we propose a unified framework that covers most of the joint sink mobility, data routing, and delay issue strategies. Based on this framework, we develop a mathematical formulation that is general and captures different issues. However, this formulation is a mixed integer nonlinear programming (MINLP) problem and is time consuming to solve directly. Therefore, instead of tackling the MINLP directly, we first discuss several induced subproblems, for example, subproblems with zero/infinite delay bound or connected sink sites (sink sites are connected if for any two sites there exists a path that connects them and each edge of that path meets the delay constraint). We show that these subproblems are tractable and present optimal algorithms for them [15]. Then, we generalize these solutions and propose a polynomial-time optimal approach for the origin DeSM problem. We show the benefits of involving a mobile sink and the impact of network parameters (e.g., the number of sensors, the delay bound, and so on.) on the network lifetime. Furthermore, we study the effects of different trajectories of the sink and provide important insights for designing mobility schemes in real-world mobile WSNs. Our main contributions are the following: |
| 1. We provide a unified formulation of DeSM, which is general and practical. We discuss subproblems of DeSM and offer efficient algorithms for them to guide the design of our algorithm for the origin DeSM. |
| 2. We generalize algorithms for subproblems and present an optimal algorithm with polynomial complexity for the DeSM. |
| 3. We study the effects of different trajectories of the sink and provide important insights via extensive simulations. |
IV. ISSUES ON MOBILE SINK SCHEDULING PROCESS
|
| Static and mobility based sink placement schemes are used to handle data collection process. Mobile sinks are used to increase the network lifetime with delay constraints. Random mobility and controlled mobility models are used in the mobile sinks. In random mobility the sinks are moved randomly with in the network. The sinks are deterministically moved across the network is referred as controlled mobility. The network lifetime is managed with the number of nodes and delay values. The Delay bounded Sink Mobility (DeSM) problem is initiated under sensor node allocation to sinks. A polynomial-time optimal algorithm is used for the origin problem. Extended Sink Scheduling Data Routing (E-SSDR) algorithm is used to schedule sink nodes. |
| • The system supports single sink based scheduling scheme |
| • Scheduling overhead is increased in centralized scheduling scheme |
| • The system supports small size networks only |
| • Energy consumption is not managed |
V. DELAY-BOUNDED SINK MOBILITY MODEL (DESM)
|
| Fig. 5.1 shows a reference architecture for a WSN with a mobile sink (i.e., s0). Sensor nodes, which are stationary, keep monitoring the surrounding environment and generating data. A mobile sink is used to gather sensed data by traveling around the network. We assume that only at certain locations, the sink can communicate with the outside network and then deliver cached data to users. For example, due to interference and security issues, for a sensor network deployed in the battle field for the surveillance mission, it is reasonable that the sink can connect with the headquarters only at certain locations using wireless techniques like WiMAX or LTE. These locations are represented by squares in the figure. The sink has a maximum speed Vmax (in m/s). We assume that while the sink is moving, sensors will buffer their newly generated data, as in [11]. Only when the sink stays at one of sink sites, sensors will start transmitting data to the sink through multihop routing. This could potentially cause a high delay for data packets. Here, we define the delay of data as following, |
| The delay of data is defined as the time spent by the mobile sink moving from one sink site to the next sink site. To limit such delay, a delay bound (i.e., ?, in second) is set according to the underlay applications. Moreover, as pointed out in the previous study, whenever a sink has been relocated to a new site, it will take some time to rebuild the routes of sensors. Thus, we set ε as the minimum residual time of any sink site. |
5.1. Network Model
|
| We model a WSN as a graph G = {V?V0, L?L0}, where V and V0 is the set of sensors and sink sites. We define n = |V| as the number of sensors and m = |V0| as the number of sink sites. L C {V × V}, is the set of wireless links between sensors. lij ε L if and only if sensor j is within the communication range ri (in meter) of sensor i. Similarly, L0 C {V ×V0} is the set of links between sensors and sink sites. As in most previous proposals [1], we do not explicitly consider radio interferences, i.e., we assume the data generation rates of sensors can be properly scaled so that underlay MACs like TDMA can eliminate the interference among communications. |
5.2. Energy Model
|
| For a node i, we assume its data generation rate λi (in b/s) can be estimated accurately. Its initial energy is Ei (in J). The total energy consumption of i cannot exceed Ei. Typically, the radio module is the most energy-consuming part, and thus its energy consumption consists of three parts: transmission receives, and sleeps. The power characteristics of two representative radio modules that have been widely used in wireless sensor platforms. Since usually the power assumption in sleep state is several orders of magnitude lower than in other states, it has nonsignificant impact on the network lifetime and thus can be ignored. The energy cost for transmitting one bit data from nodes i to j (or to s0 at site k) can be determined as follows [11]: |
| eTij(k) = α + β. d(i, j(k))θ, (1) |
| where α (in J/bit) and β (in J=bit=m3) are constant coefficients, d(i, j(k)) (in meter) is the distance between nodes i and j (or sink site k), and θ is the path loss index, which is typically in the range of 2 to 6 depending on the environment. We denote energy cost for receiving one unit data as eR (in J/bit), which is constant. |
| For the sink s0, we assume it has limitless energy compared to sensor nodes. The network lifetime is defined. Thus, based on the network and energy models, the problem of our concern can be stated. Problem statement (DeSM problem). Given network topology G, maximize network lifetime by jointly sink scheduling and data routing subject to energy and delay constraints. |
VI. EXTENDED SSDR (E-SSDR) ALGORITHM FOR DESM
|
| To solve the origin DeSM problem, we prove the following conclusion: For an instance of DeSM, if its sink site graphs G’ is not connected, we can divide G’ into connected subgraphs, each of which can be solved optimally by the SSDR. The overall optimal solution for this instance is the same solution of the subgraph with the longest network lifetime. |
| The proof is based on contradiction. Assume that for an instance of DeSM, we have an optimal solution which involves two sites from two different subgraphs. This means that we find a sink path including these two sites that meets the delay constraint. Thus, these two sites are connected and should be in the same subgraph. This is the contradiction and finishes the proof. We propose an E-SSDR approach to solve the origin DeSM optimally: |
| Step 1. Divide G’ into connected subgraphs. Step 2. Apply the SSDR approach to each subgraphs and obtains the optimal sink path as well as corresponding routes. |
| Step 3. Choose the solution of the subgraph with the longest network lifetime as the output. |
| For the E-SSDR approach, we have the following conclusion: |
| E-SSDR is an optimal algorithm for the DeSM problem with O(m3n6) complexity. |
| Ensure that E-SSDR is an optimal algorithm for the DeSM problem. The complexity of ESSDR is decided by Step 2, which is O(m3n6). |
VII. MULTI SINK BASED SCHEDULING SCHEME
|
| The mobile sink scheduling scheme is enhanced to support large size networks. Distributed scheduling algorithm is applied to schedule nodes with high scalability. The scheduling scheme is tuned for multiple sink based environment. Delay and energy parameters are integrated in the sink scheduling process. |
| The mobile sink based data collection scheme is improved for multi sink environment. Scheduling schemes are used to estimate the sink movement plans. Data collection intervals are assigned in the scheduling process. The system is divided into five major modules. They are network boundary analysis, data capture process, centralized scheduling, distributed scheduling and data collection process. |
| Sensor network boundary and node placement details are analyzed in the boundary analysis. Data sensing is performed under the data capture process. Centralized scheduling is used to schedule single sink nodes. Distributed scheduling is used to schedule multiple sink nodes. Data collection process is designed to perform query processing in the network. |
7.1. Network Boundary Analysis
|
| Node and sink properties are collected from the user. Sensor node placement and coverage analysis is carried out under network boundary analysis. Node location and coverage information are analyzed. Node and sink energy levels are analyzed in the network analysis. |
7.2. Data Capture Process
|
| Environment monitoring and data sensing is carried out under the data capture process. Captured data values are updated into the local storages. Captured data values are updated with time details. The data values are transferred to the sink node. |
7.3. Centralized Scheduling
|
| Centralized scheduling is used to estimate the data collection process for single sink environment. Extended Sink Scheduling Data Routing (E-SSDR) algorithm is used to schedule single sink node. Sink node and sensor node transmission coverage details are used for the scheduling process. Delay information is used for data update process in sink node. |
7.4. Distributed Scheduling
|
| Distributed scheduling is designed for the multiple sink nodes. Sink movement is planned with sink coverage and network region details. Distributed sink scheduling algorithm is used for sink movement plan. Region based sink movement model is used in the system. |
7.5. Data Collection Process
|
| Data requests are submitted by the users. Data values are collected by the mobile sinks from the sensor nodes. User query values are processed by the mobile sink nodes. Mobile sink transfers the query results to the requested user. |
VIII. CONCLUSION
|
| Sink nodes are used in the wireless sensor networks to handle data collection and transmission process. Extended Sink Scheduling Data Routing (E-SSDR) is used to schedule sinks. The Delay bounded Sink Mobility (DeSM) is solved with centralized and distributed scheduling schemes. The scheduling scheme is adapted to support multi sink based data collection mechanism. Energy consumption is minimized in the data collection scheme. The scheduling scheme is suitable for single and multiple mobile sink environment. Scheduling overhead is reduced in the multi sink model. Data collection latency is reduced in the sensor networks. |
Figures at a glance
|
 |
 |
| Figure 1 |
Figure 2 |
|
| |
References
|
- 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 Trans. Networking, vol. 18, no. 5, pp. 1387-1400, 2010.
- W. Song, R. Huang, M. Xu, B.A. Shirazi, and R. Lahusen, “Design and Deployment of Sensor Network for Real-Time High-Fidelity Volcano Monitoring,” IEEE Trans. Parallel and Distributed Systems, vol. 21, no. 11, pp. 1658-1674, Nov. 2010.
- G. Keung, B. Li, and Q. Zhang, “Message Delivery Capacity in Delay-Constrained Mobile Sensor Networks: Bounds and Realization,” IEEE Trans.Wireless Comm., vol. 10, no. 5, pp. 1552-1559, May 2011.
- E. Guney, N. Aras, I.K. Altinel, and C. Ersoy, “Efficient Integer Programming Formulations for Optimum Sink Location and Routing in Heterogeneous Wireless Sensor Networks,” Computer Networks, vol. 54, no. 11, pp. 1805-1822, 2010.
- W. Liang and J. Luo, “Network Lifetime Maximization in Sensor Networks with Multiple Mobile Sinks,” Proc. IEEE 36th Conf. Local Computer Networks, Oct. 2011.
- R. Lu, X. Lin, H. Zhu, X. Liang, and X.S. Shen, “Becan: A Bandwidth-Efficient Cooperative Authentication Scheme for Filtering Injected False Datain Wireless Sensor Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 23, no. 1, pp. 32-43, Jan. 2012.
- Y. Wang, W. Peng, and Y. Tseng, “Energy-Balanced Dispatch of Mobile Sensors in a Hybrid Wireless Sensor Network,” IEEE Trans. Parallel and Distributed Systems, vol. 21, no. 12, pp. 1836- 1850, Dec. 2010.
- Y. Wang, F. Wu, and Y. Tseng, “Mobility Management Algorithms and Applications for Mobile Sensor Networks,” Wireless Comm. Mobile Computing, vol. 12, pp. 7-21, 2012.
- G. Keung, Q. Zhang, and B. Li, “The Base Station Placement for Delay-Constrained Information Coverage in Mobile Wireless Networks,” Proc. IEEE Int’l Conf. Comm., May 2011.
- Y. Gu, Y. Ji, H. Chen, J. Li, B. Zhao, and A.V. Vasilakos, “Scheduling Sinks in Wireless Sensor Networks: Theoretic Analysis and an Optimal Algorithm,” Proc. IEEE Int’l Conf. Comm. (ICC ’11), 2011.
- Y. Yun and Y. Xia, “Maximizing the Lifetime of Wireless Sensor Networks with Mobile Sink in Delay-Tolerant Applications,” IEEE Trans. Mobile Computing, vol. 9, no. 9, pp. 1308-1318, Sept. 2010.
- X. Li, J. Yang, A. Nayak, and I. Stojmenovic, “Localized Geographic Routing to a Mobile Sink with Guaranteed Delivery in Sensor Networks,” IEEE J. Selected Areas in Comm., vol. 30, no. 9, pp. 1719-1729, Oct. 2012.
- K. Ota, M. Dong, Z. Cheng, J. Wang, X. Li, and X. Shen, “Oracle: Mobility Control in Wireless Sensor and Actor Networks,” Computer Comm., vol. 35, pp. 1029-1037, 2012.
- Y. Gu, Y. Ji, J. Li, and B. Zhao, “Delay-Bounded Sink Mobility in Wireless Sensor Networks,” Proc. IEEE Int’l Conf. Comm. (ICC ’12), June 2012.
- Yu Gu, YushengJi, Jie Li, and Baohua Zhao, “ESWC: Efficient Scheduling for the Mobile Sink in Wireless Sensor Networks with Delay Constraint”, IEEE Transactions On Parallel And Distributed Systems, Vol. 24, No. 7, July 2013.
|
Menu