Sensor Movement using Pareto-Optimal Matching and Spanning Construction

Sensor Movement using Pareto-Optimal Matching and Spanning Construction

Reshma R S1*, Anisha S S2

1*PG Scholar, Dept. of computer science and engineering 2Assistant Professor, Dept. of computer science and engineering TKM Institute of Technology, Kollam, India

Abstract Wireless sensor network is used to sense the environment conditions such as humidity, sound and exchange the message with the neighbor sensors. The hybrid wireless sensor network consists of static and mobile sensors. The static and mobile sensors can analyze multiple attribute of events since they are equipped with multiple sensing devices. The static sensors monitor the environmental changes and pass the event information to the sink node through the network. The condition where the sensory input is above or below the predefined threshold is called an event. The events also have multiple attribute. Mobile sensors then move to these locations to analyze the situation deeply. Here a multi attribute sensor dispatch problem is introduced which is NP-complete. It is solved by pareto-optimal matching and spanning tree construction algorithm. This algorithm considers both the remaining energies of mobile sensors and time to analyze the event to reduce the overall time spent to complete the assignment.

Index Terms Hybrid wireless sensor network, mobile sensor, pareto-optimal matching.

1. INTRODUCTION

   The wireless sensor network provides a means to sense the physical environment. The hybrid wireless sensor network consists of both static and mobile sensors. Introducing mobility to a wireless sensor networks (WSNs) significantly enhances its capability and reduces its deployment and maintenance cost. Static sensors are responsible for environmental monitoring for detecting the event. An event is the condition where the sensory input is higher or lower than the predefined threshold. The static sensor reports the location where the event occurs. Mobile sensors then move to the corresponding location for conduct in-depth analysis of the event. Here events and mobile sensors have multiple attributes. Multiple sensing devices are equipped in both the static and mobile sensors. Each of the sensors can analyze multiple attributes of the events. So static sensor is called as multi-attribute static (MAS) sensors and mobile sensor is called as multi-attribute mobile (MAM) sensor.

   Let A be the set of attributes. Each event is associated with multiple attribute in A. When an event is reported by the MAS sensor(s), only the MAM sensor with same attribute of that event can be dispatched to conduct in-depth analysis. A MAM sensor will move to the location of the event such that both the event and MAM sensor have at least one same

   attribute. In this paper, both the events and mobile sensors are heterogeneous. MAM sensors are battery-powered and due to the movement of MAM sensor the energy loss will occur. So efficiently choose the path to the save remaining energy of MAM sensor. Here the time is divided into number of rounds since the event may appear anywhere and anytime. To reduce the computation overhead schedule the travelling path of MAM sensor in round-by-round manner.

   This work proposes mobile sensor dispatch problem which states how to assign mobile sensor to visit the event locations.

   The problem is NP-complete. To solve this problem, a heuristic is developed which has two phases such as pareto- optimal matching and spanning tree construction. This algorithm reduces the moving energy spent by the MAM sensors. It considers both the distance between the MAM sensor and multi-attribute events and remaining energy of MAM sensor to calculate the edge weight. The algorithm also considers the time to analyze the event for reducing the overall time spent to complete the assignment.

   The rest of the paper is organized as follows: Section II describes related works. Section III defines the method. The performance evaluation is presented in section IV. Section V concludes the paper.

2. RELATED WORKS

   For dispatching MAM sensor, number of methods has been developed. Static sensors have some limitations for handling the changes in the network conditions. Deployment and maintenance cost of the sensor is reduced by adding mobility [1] to WSN. This node mobility could be controllable and even coordinated in hybrid wireless sensor network. The system having immobile sensors uses event- based motion control [2] to move the sensors for maintaining the complete coverage of sensing field. Here a sparse set of sensors would be active and monitoring for event. When an event occur other set of sensors could become active and maintain complete coverage of sensing field.

   To complete the sensing tasks sufficient coverage is very important. Voronoi diagram [3] is used to detect the coverage holes and control the movement of mobile sensors. It describes a distributed protocol for controlling the movement of sensors to fill the holes. G.Wang et al [4] considers sensor relocation problem in a one-to-one manner. Here the sensor does not directly move to the event location; instead it uses

   cascaded movement. This work considers only the mobile sensor network.

   The work of [5] investigates the sensor deployment problem such as sensor placement and sensor dispatch problem. The work proposes both centralized and distributed heuristic to dispatch sensors in an energy-efficient way. Y.C.Wang et al [6] proposes a centralized and distributed heuristic to minimize the moving cost and thus energy consumption of mobile sensors. But these works considers only homogeneous events.

   The work [7] adopts virtual forces among sensors to achieve the coverage and reduce energy consumption. The virtual force is used make the sensors evenly distribute over the sensing field. Y.C.Wang et al [8] discuss how the sensors can efficiently be deployed to get multi-level coverage of an area by introducing k-coverage sensor deployment problem. The solution to these problems dispatches the sensors in an energy-efficient way. R.Tan et al [9] proposes a two-phase detection approach in which mobile sensor cooperate with static sensor to improve the target detection in WSN. To achieve the required detection performance, the static sensor collaborates with mobile senor and move reactively.

   The twophase dispatch heuristic [10] uses hybrid wireless sensor network which consists of both static and mobile sensors. The two phases are pareto-optimal matching and spanning tree construction. But it considers only single attribute event. The main disadvantage of the work is it does not consider the time to analyze the event and remaining energy of the mobile sensor. This work is taken as existing system to compare the performance of the proposed work.

   TABLE I. NOTATIONS

   Notation	Definition
   S	Set of MAM sensor
   E	Set of multi attribute event location
   A	Set of attributes
   Lu	Set of unassigned event location
   ec	Energy cost for a MAM sensor to move one unit
   	distance
   w(s,e)	Moving cost for MAM sensor s to move the from its
   	current location to event location e

   1. Maximum Pareto-optimal Matching

      The algorithm starts by constructing a weighted bipartite graph, G= (SE, S×E). Here the vertices are MAM sensor and event location. Edges connect the vertices btween S and E such that both of them have same attribute. The weight of edge, w(s,e) is calculated by adding the moving cost of MAM sensor and remaining energy of the mobile sensor. The moving cost is product of distance between sensor and event location and energy cost for a MAM sensor to move one unit distance (ec). Here the edge weight is updated based on the remaining energy of mobile sensor. To solve the dispatch problem, a matching set M has to be calculated.

      If (vi,vj)M for all (vi,vj) (S×E) then vertex vi (SE) is considered as free. A path whose end points are free and its edges alternatively appears in M and (S×E) then the path is augmenting path.

3. METHODS

   The MAM sensor dispatch problem is NP-complete. To prove this statement first proves that the problem belongs to NP. Given an instance of dispatch problem and k-round scheduling for S (set of sensors), whether the schedule is valid or not can be verified in polynomial time. Hence the problem belongs to NP.

   Then reduce the partition problem, which is an NP- complete problem to the MAM sensor dispatch problem. Given a finite set X where each element x is assigned with a value v(x); the partition problem determines whether X can be partitioned into two subsets such that the sum of their values are equal. The partition problem reduces to the MAM sensor dispatch problem [10]. Hence the MAM sensor dispatch problem is NP-complete.

   To reduce the moving cost of MAM sensor a dispatch heuristic is developed which consists of two phases such as pareto-optimal matching and spanning tree construction. The pareto-optimal matching assigns one MAM sensor to one event locations. Then Spanning tree construction is used to handle the remaining unassigned event location. The notations used in the heuristic are summarized in the Table I.

   Algorithm

   1. Let M=. Arbitrarily select one edge from (S×E) and assign it to M.

   2. Find an augmenting path from M and calculate new matching M which is the symmetric difference between edges in M and P (M=MP). Set M=M.

   3. Repeat the above step until there is no augmenting path form M.

      To make the matching set M become pareto-optimal some exchanges are done in M. To do so, consider the definition described below.

      Definition: Let M1 and M2 are two matches and s is a MAM sensor which prefers M1 to M2 if one of the following conditions is satisfied.

      • MAM sensor s is not matched to any of the event location in M2 but in M1.

      • Assume that s is matched to the vent location li in M1 and lj in M2 and w(s,li) < w(s,lj) and the time to analyze the event in the location li is less than that of the event in the location lj.

   The condition when no sensors prefer M1 to M2, and some sensor prefer M2 to M1 is denoted by M2 >p M1. A matching M is pareto-optimal if and only if there is no matching M such that M >P M. To make M become pareto-

   optimal modify the algorithm by conducting the following check.

   Assume that an MAM sensor s is assigned to an event location li in M. If there is an unmatched event location lj such that w(s,li) > w(s,lj) and the time to analyze the event in the location lj is less than the time to analyze the event in li then replace the match (s,li) with a match (s,lj) in M. If there is multiple candidates, then select the event location lj such that (s,lj) is minimum. This check is repeated until no such replacement can be conducted.

   Although an MAM sensor has already matched to one event location, it can change to move the closest unmatched event location. This saves the moving energy of MAM sensor.

   1. Spanning Tree Construction

   Spanning tree construction algorithm is used to handle the situation where the number of MAM sensor is not enough to visit all the event location. Each of the matches from pareto-optimal matching is taken as spanning tree with root as corresponding MAM sensor. Each unassigned event location can join a spanning tree if the root MAM sensor has the same attribute.

   Algorithm

   1. For each match in M (si,lj) construct a spanning tree with si as root and (si,lj) as edge.

   2. Select one event location and calculate the tree T whose

      root have the same attribute.

   3. If |T|=1, the location joins the tree. Otherwise sort the tree based on their tree weight and time to analyze the event in ascending order. Among these trees, the event location joins the tree which has minimum weight and takes minimum time to analyze the event.

   4. Delete the event location from Lu. Repeat step 2 and 3 until Lu become empty.

      By applying this algorithm MAM sensors are matched to all the event locations which reduce the energy consumption due to the movement of MAM sensors and also reduce the overall time spend for assignment.

4. PERFORMANCE EVALUATION

   Here compare the proposed work with the existing work [10]. The existing system is also a two-phase heuristic which consists of pareto-optimal matching and spanning tree construction but it has some limitation such as

   1. It analyses only the single attribute event.

   2. It considers only the moving cost of MAM sensor but does not consider the time to analyze the event and remaining energy of MAM sensor.

   The proposed system is used to minimize the energy consumption due to the movement of MAM sensor and overall time spent to complete the assignment which consider both the remaining energy of MAM sensor and the time to analyze the event since analyzing different attribute of event may require different amount of time. Here the event may have multiple attribute. To sense multiple attribute of event the MAS sensor is used which is equipped with multiple

   sensing devices. The algorithm matches the multiple attribute event location with MAM sensor.

   Fig. 1. Comparison of energy consumption between proposed and existing algorithm

   The comparative study in Fig. 1 shows that the energy consumption will be minimized by increasing the number of sensor. Here the energy consumption of MAM sensor using proposed work is less than that of the existing system. The result verifies that the proposed system gives a good performance compared to the existing system.

5. CONCLUSION

This paper solves the MAM sensor dispatch problem in the hybrid wireless sensor network. Here both the event and mobile sensor have multiple attribute. It uses a heuristic which contain two phases such as pareto-optimal matching and spanning tree construction. Pareto-optimal matching gives one-to-one assignment between multi attribute event location and MAM sensor from a weighted bipartite graph. The weight of edge is calculated by adding the moving cost of MAM sensor and remaining energy of the MAM sensor. It also considers the time to analyze the event. The spanning tree construction is used to handle the remaining unassigned event location which also considers the remaining energy of MAM sensors and time to analyze the event.

REFERENCES

1. Y.C. Wang, F.J. Wu, and Y.C. Tseng, Mobility Management Algorithms and Applications for Mobile Sensor Networks, Wireless Comm. and Mobile Computing, vol. 12, no. 1, pp. 7-21, 2012.

2. Z. Butler and D. Rus, Event-Based Motion Control for Mobile- Sensor Networks, IEEE Pervasive Computing, vol. 2, no. 4, pp. 34- 42, Oct./Dec. 2003. s

3. G. Wang, G. Cao, and T.F. La Porta, Movement-assisted Sensor Deployment, IEEE Trans. Mobile Computing, vol. 5, no. 6, pp. 640- 652, June 2006.

4. G.Wang, G.Cao, T.F.LaPorta, and W.Zhang, Sensor Relocation in Mobile Sensor Networks, Proc. IEEE INFOCOM, pp. 2302- 2312, 2005.

5. Y.C. Wang, C.C. Hu, and Y.C. Tseng, Efficient Placement andsss Dispatch of Sensors in a Wireless Sensor Network, IEEE Trans. Mobile Computing, vol. 7, no. 2, pp. 262-274, Feb. 2008.

6. Y.C. Wang, W.C. 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.

7. X. Wang and S. Wang, Hierarchical Deployment Optimization for Wireless Sensor Networks, IEEE Trans. Mobile Computing, vol. 10, no. 7, pp. 1028-1041, July 2011.

8. Y.C. Wang and Y.C. Tseng, Distributed Deployment Schemes for Mobile Wireless Sensor Networks to Ensure Multilevel Coverage, IEEE Trans. Parallel and Distributed Systems, vol. 19, no. 9, pp. 1280- 1294, Sept. 2008.

9. R. Tan, G. Xing, J. Wang, and H.C. So, Exploiting Reactive Mobility for Collaborative Target Detection in Wireless Sensor Networks, IEEE Trans. Mobile Computing, vol. 9, no. 3, pp. 317- 332, Mar. 2010.

10. Y. C. Wang, A Two-Phase Dispatch Heuristic to Schedule the Movement of Multi-Attribute Mobile Sensors in a Hybrid Wireless Sensor Network IEEE. Trans. Mobile Computing, vol.13, no.`4, April 2014.