Research on Sensor Network Coverage Enhancement Based on Non-Cooperative Games

Cha of an Duan,Jing Feng, ,Haotian Chang,Jianping Pan and Lim ing Duan

Abstract:Coverage is an important issue for resources rational allocation,cognitive tasks completion in sensor networks.The mobility,communicability and learning ability of smart sensors have received much attention in the past decade.Based on the deep study of game theory,a mobile sensor non-cooperative game model is established for the sensor network deployment and a local information-based topology control (LITC)algorithm for coverage enhancement is proposed.We both consider revenue of the monitoring events and neighboring sensors to avoid nodes aggregation when formulating the utility function.We then prove that the non-cooperative game is an exact potential game in which Nash Equilibrium exists.The proposed algorithm focuses on the local information of the neighboring sensors and decides sensors’ next action based on the actions of the e other sensors,which maximizes its own utility function.We finally evaluate the performance of the proposed method through simulations.Simulation results demonstrate that the proposed algorithm can enlarge the coverage of the entire monitoring area while achieving effective coverage of the events.

Keywords:Sensor network deployment,non-cooperative games,event coverage,topology control.

1 Introduction

Due to the high efficiency and strong adaptability,sensor networks have been widely used in ecological environment surveillance,battlefield detection,etc.Collecting data through sensors has changed the traditional data collection mode,especially when the monitoring environment is hostile or remote,where sensor deployment cannot be actively [Rawat,Singh,Chaouchi et al.(2014)].Detection and working efficiency of the sensor network is closely related to the coverage efficiency of the monitoring area.Therefore,proper sensor deployment method is the key problem in completing the surveillance tasks.

Sensors can be deployed remotely by the means of aircraft or ship spraying.However,sensor positions will be strongly affected by environmental factors such as wind,obstacles,which is difficult to control [Zou and Chakrabarty (2003)].Changes of sensors’positions will cause changes of the e network topology,affecting the effective monitoring tasks.To ensure sufficient coverage of the monitoring area,new sensors are necessary which will greatly increase the overall cost.In this case,smart sensors with mobile platforms and can move around after initial deployment are able to move to the appropriate positions that will greatly increase the success of missions [Zhang,Zheng and Lei (2018)].

In the event monitoring scenario,the objective is to dispatch mobile sensors to the sources of events for better event coverage [Wang (2010)].Koutsougeras et al.[Koutsougeras,Liu and Zheng (2008)] uses the self-organizing maps (SOMs) to monitor the attraction of the target,so that the nodes tend to move to the area with high time density and achieve high events coverage.Zhang et al.[Zhang,Zheng and Lei (2018)]proposed a dynamically optimized sensor deployment strategy.In this strategy,the revenue of the monitoring target,the monitoring cost as well as the obstacle conditions is considered.However,this method assigns events to the sensor before sensor deployment,sensors move to reach its own target,which requires a lot of preparation know ledge.Wang et al.[Wang,Peng,Chang et al.(2007)] established a hybrid sensor network consisting of static nodes and mobile nodes.The corresponding relationship between nodes and events is established through a centralized control algorithm,and solved the deployment problem that maximizes the network lifetime.

The typical feature of the distributed optimization problem is that the decision-making individuals distributed in different physical locations and make the decision independently to achieve the global optimization [Wang,Ju,Gao et al.(2018)].However,in the content of these studies,the actions of sensors are taken according to the global information.In the actual scenario,a single sensor node will only interact with its neighboring nodes,and it is hard to obtain the global information.

The main contributions of the is paper are as follows.We first establish the mobile sensor non-cooperative game model which is proved an exact potential game.We then propose a local information based topology control (LITC) algorithm based on this model,in which sensors move to enhance coverage by exchanging information with neighbors.We finally evaluate the performance of the proposed algorithm.Experimental results show the correctness of the e algorithm and they demonstrated the efficiency compared with a benchmark method.

The rest of the paper is organized as follows:In Section 2,the description of mobile sensor deployment problem and game model are given.In Section 3,the non-cooperative game model of mobile sensor and its theoretical analysis are described.In Section 4,the local information based topology control algorithm is presented.In Section 5,the performance of the proposed algorithm is analyzed.Finally,the conclusion and future work are given in Section 6.

2 Sensor dep loyment problem and game theory description

In this section,we will first introduce some basic concepts of the e sensor deployment and then,a brief description of game theory is given.

2.1 Sensor deployment problem

In areaZ,we consider a set of eventsand a set of mobile sensorsSensors have the ability to sense,move and communicate,the sensing radius is rjwhile the communication radius is rcandA ll of the sensors are homogenous and have the ability to exchange information with sensors within the communication radius.

Definition 1:InZ,for ?ei∈Z,the coverage probability of sensorsjto eventeishould satisfy:

whered(,)represents the Euclidean distance betweenand,rsis the confident radius of the e sensor,λis the perceptual attenuation factor.The probability coverage pattern is shown in Fig.1.

Figure1:Sensor’s probability coverage pattern

Definition 2:For single eventei,it is possible to be covered by multiple sensors.The coverage rate is defined as:

Definition 3:When the Euclidean distance between the sensors is less than rc,then they are neighbor nodes,and the neighbor nodes set of sensorsjis:

2.2 Game theory

Game theory is an important branch of applied mathematics.After decades of development,it has become one of the important methods for multi-user distributed decision-making optimization in wireless communications [Komali,Mackenzie and Gilles (2008)].

Definition 4:The non-cooperative game model can be expressed asin whichis the set of game participants (sensor nodes).Asiis the optional action set of sensorandis the utility function. Assume thatis the action taken bythenrepresents the set of all sensors actions,represents the action set for all sensors exceptrepresents the Cartesian product of all participants, that is a collection of all possible combinations of actions.

Definition 5:In a non-cooperative game,the goal of each node is to maximize its own utility function,and the Nash equilibrium is a steady solution of the non-cooperative game.Forsatisfies:

Nash Equilibrium is acquired when no participant can improve its utility function by changing its own action [Abbasi and Fisal (2015)].

Definition 6:In a finite game modelG,if there is a potential functionfor any sensor nodeany actionsatisfies:

Then this game is the Exact Potential Game (EPG),and the potential function is the Exact Potential Function (EPF).

3 Mobile sensor non-cooperative game model

After the initial deployment,sensor nodes need to move to achieve sufficient coverage to complete the monitoring tasks.For this purpose,the mobile sensor non-cooperative game modelis established.

3.1 Elements of the e non-cooperative game model

Game participants:In this game,participants of the e game are the sensor nodesin the monitoring area.Sensor nodes can determine the action through the local information obtained by itself.

Action set:The next selectable position of the sensorAsiconstitutes an optional set of actions.In this game,sensor node is allowed to move the maximize length of rc/2 in the area.

Utility function:Due to the characteristics of mobile sensors,decision-making individuals have limitations in their ability to acquire and process information.Sensors only interact with neighbors and fail to get the overall information of the network.At the same time,the movement of the sensors will lead to changes of the e network topology.To describe the topological relationships in the network,the matrix theory method is used to analysis the information interaction topology of the sensors in the area [Xin,Gan,Li et al.(2013);Zhang,Zhao and Qi (2013)].

The following n-order binary matrixS(t)is used to describe the two-way information interaction of sensors at the timet.

Any game participant knows its own information at any time,sosii(t)=1,at timet,if information exchange exists between participantsiandj,then we haveon the contrary

S(t)changes its value at the time point {tk,k= 0,1,2...,∞},and keeps constant between two time point,that is:

The information interaction between sensors may be affected by many factors [Bulter and Rus (2003)].In order to simplify the model,the Euclidean distance between sensors is used as the main criterion for judging whether there is information interaction between sensors.

Since the sensors and the event points are randomly distributed,and the sensor nodes have a certain coverage radius,when the initial deployment is completed,the sensor nodes will move to the appropriate location to cover events [Li,Ji,Liu et al.(2013)].Here,we construct the revenue function that examines the revenue of a single sensor:

According to the revenue function,it is easy to see that the function only relates to the current position of the sensor and the position of the events.Therefore,if a single sensor pursues its maximum revenue,it will certainly occur this circumstance that multiple sensors eventually reach to the same position.In order to reduce the overlapping area between the sensors,the balance function is constructed to improve the balance of the rearrangement:

The balance function mainly considers the distance between the sensor nodes and the standard deviation.We hope that the distance between the sensor nodes can be as large as possible to achieve large coverage of the target area,and the standard deviation is as small as possible to make the sensors distribution evenly.Finally,the difference between the two is normalized.

Game participants take actions according to egoism,sensors take actions which maximum the utility functions.At the same time,since the action taken by the sensors in the game will only lead to the change of the balance function of its neighbor nodes [Xu,Wang,Wu et al (2013)],considering these aspects together,the utility function of the game is constructed as follows:

whereαandβare two non-negative weight parameter.

Based on the utility function defined above,the model is:

3.2 Nash equilibrium analysis

Theorem 1:GameGis an exact potential game,while functionΦis an exact potential function of the game.

Pro of :First,we construct the following potential function:

If any node,change its action fromtothen the change of utility function is:

On the other hand,the change of potential function is:

After simplification,the following equation can be obtained:

Since the change in node position is at most rc/2,and sensor node only influence nodes which the Euclidean distance is less than rc/2.Therefore,the change of action will only affect the balance function of the node and its neighbor nodes,and will not affect the change of utility functions of other nodes.

The revenue function of sensor node is only related to its own location and the location of the events.Therefore,the action change ofsiwill not affect the revenue of other nodes.

Therefore,it is easy to have the equation below:

Theorem 1 is proved.GameGis an EPG,and Φis the EPF of the game.

Theorem 2:If gameis an exact potential game,and functionΦis an exact potential function of the game,then the action seta*that maximizesΦis a Nash Equilibrium of the game [Nash (1951)].

Pro of :Details of the e pro of s can be found in Nash [Nash (1951)].We just use the conclusion here.

4 Local information-based topology control algorithm

In this section,a topology control algorithm based on the local information is proposed.Sensor nodes take actions by the acquired local information to complete the event monitoring tasks.The algorithm includes the initial phase,the non-cooperative game phase and the topology maintenance phase.

4.1 Initial phase

Since the initial sensor location and the event location are both random,and the action set is the discrete grid point in the area.Therefore,the target area is first rasterized and sensors are forced to move to the closest grid after initially deployment.Then,the sensor nodes acquire their own coordinates and broadcast a message to its neighbors.The message structure is shown in Tab.1.

Table1:Message structure

This message consists of the e sensors’ Id,coordinates,neighbor set,events covering conditions and residual energy,which are necessary for neighbor sensors to make decisions.

4.2 Non-cooperative game phase

All nodes play a game in a random manner to determine their own action.There is only one sensor in each round to take action while other sensors remain unchanged.After each round of the game,a message is sent to notify its neighbor sensors to update the location information.When a sensor changes its action,it needs to recalculate its neighbor node set.The update strategy of each sensor is:

whereasirepresents the possible actions for sensorsi.

4.3 Topology maintenance phase

In the local information-based topology control algorithm,sensor nodes participate in the game.Each node determines its own action that maximizes the utility function.In order to avoid the occurrence of frequent oscillating motion,the threshold value of the utility function variation is set.The node position remains unchanged when the benefit brought by the action is smaller than the threshold.

When the remaining energy of the node is insufficient to support the node movement,the sensor node keeps its position unchanged and exits the game.Local Information Based Topology Control Algorithm is described as follows:

Input Events E and Sensors S Output Final coordinate of Sensors S 1.Initial sensor deployment 2.For i s S ∈3.i a nearest grid ←4.End 5.while()6.For max t t ＜is S ∈that 1flag ≠7.If then 8.m in P P ＜;10.End 11.;9.is stable ←1 flag =i s J Neighbor set ←12.max i i s a U ←13.If then 14.min i s U U Δ ＞;15. of i i s position s a ←P P d ← -Δ;16.End 17.End 18.1t t ←+19.End

5 Simulation and analysis

In this section,we evaluate the performance of our proposed algorithm.We first select two sets of parameters ofαandβ,then the proposed algorithm is compared with the wellknown virtual force-based sensor movement strategy.It is worth mentioning that we use the percentage of events coverage,percentage of area coverage,percentage of residual energy and the Global events coverage rate as the main metrics of performance evaluation.

5.1 Experimental setup

The position of sensors and events are random in the square area Z.The energy cost for sensor movement is the moving distance from the current position to the next position.The simulation parameters are shown in Tab.2.

Table2:Simulation parameter

5.2 Simulation metrics

The performance of the proposed algorithm is assessed through the following four metrics.

Percentage of events coveragedefined as the ratio of the number of events covered by the sensors to the total number of events.

Percentage of area coveragedefined as the ratio of the area covered by the sensors to the total size of the target area.

Percentage of residual energydefined as the ratio of the average residual energy of the sensors to the initial energy.

Global events coverage ratedefined as the coverage rate of all the events.

5.3 Simulation results

αandβare two important parameters in the utility function,and determines the sensor’s actions.We select two sets of parameters to investigate the impact on the coverage effect and make a comparison with the virtual force algorithm [Zou and Chakrabarty (2003)].

Figure2:Percentage of events coverage

As shown in Fig.2,we can see the percentage of events coverage of the blue line is higher than the red one and the black one,which means if we focus more on the balance function,we get better events coverage.It is obvious that if the weight of revenue function is given too much,sensors will select the nearby event point position as its actions,and most of the nodes may choose similar positions.Since in a single game,sensors have a limited moving distance,and these nodes will not move in the next turn.That is the reason why that the percentage shown by the red line does not increase apparently with the number of sensors increases.In the virtual force algorithm,the movement of the sensor nodes is affected by the gravitational force and repulsive force between the nodes.In the comparative simulation,the effect of the event points on the nodes is not taken into consideration,so the coverage percentage of the event points grows slowly.

With the simulation results shown in Fig.3,it can be concluded that the percentage of area coverage raises with the sensor number increases.Similarly,the blue line shows a better performance than the black one and the red line performances poorly.Since the location of events is random,so the density of events in certain location is higher,and sensors are able to get higher revenue instead of taking other actions.This explains the reason that the percentage of area coverage remains constant when the number of nodes increases from 65 to 80.

Figure4:Percentage of residual energy

The situation seems to be more complex when we consider about the percentage of residual energy.Intuitively,as the number of nodes increases,a single node can complete the monitoring of the event points without having to move too much distance,or the sensor is more crowded due to the increase in the number of sensors in the area.However,when the number of nodes increases from 50 to 60,the remaining energy of the nodes is reduced for both the red and blue lines.After detailed experimentation,we found that when the number of nodes is too small,in some area,the number of sensors is near to zero,no sensors use the balance function to push the sensors to the blank area,causing these nodes to reach a steady state prematurely.

Figure5:Global events coverage rate

The results in Fig.5 show that giving higher weight to the revenue function can lead to a higher event coverage rate.The reason is that if the event is in the confidence circle of the sensor node,the revenue obtained is greater than the revenue in the probability circle.In the case of the red line,sensor nodes are clustered near the event point,forming a densely deployed state.The virtual force algorithm considers the node interaction but not the value of the events,so the black line does not get a high events coverage rate.

6 Conclusion and future work

When initially deployed in the target area,sensors can only obtain local information with neighboring sensors.In this paper,we first construct a mobile sensor non-cooperative game model with the proposed local information based topology control algorithm is proposed.Then the potential function is designed and we prove that this game is an exact potential game.Finally,the simulation shows that sensor achieve a high percentage of event coverage through the proposed algorithm.From the comparison simulation between virtual force algorithm,the proposed algorithm shows a better result in the event coverage percentage as well as the residual energy.It is obvious that the simulation parameters such as sensing radius,number of nodes,sensors’ distribution method,etc.will greatly influences the simulation results.We will further consider these parameters,and make more comparison simulation with other algorithm.In addition,we will consider some more complex networks that have both static nodes and mobile nodes,in which case the goal of optimization is changed and will be more challenging.

Acknowledgment:Thanks for the reviewers’ guidance on the revision of this paper.Scientific issues of the is study come from project supported by the Natural Science Foundation of China with Grant No.6137119.