Novel Sensor Scheduling Scheme for Intruder Tracking in Energy Efficient Sensor Networks
Raghuram Bharadwaj Diddigi Prabuchandran K. J. Shalabh Bhatnagar























 Novel Sensor Scheduling Scheme for Intruder 

	Tracking in Energy Efficient Sensor Networks 
    Raghuram Bharadwaj D.^1,
        Prabuchandran K.J.^1,
        and Shalabh Bhatnagar^1
^1 Authors are with the Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India


    December 30, 2023
=================================================================================================================================================================================================================








	

We consider the problem of tracking an intruder using a network of wireless sensors. For tracking the intruder at each instant, the optimal number and the right configuration of sensors has to be powered.  As powering the sensors consumes energy, there is a trade off between accurately tracking the position of the intruder at each instant and the energy consumption of sensors. This problem has been formulated in the framework of Partially Observable Markov Decision Process (POMDP). Even for the state-of-the-art algorithm in the literature, the curse of dimensionality renders the problem intractable. In this paper, we formulate the Intrusion Detection (ID) problem with a suitable state-action space in the framework of POMDP and develop a Reinforcement Learning (RL) algorithm utilizing the Upper Confidence Tree Search (UCT) method to solve the ID problem. Through simulations, we show that our algorithm performs and scales well with the increasing state and action spaces. 
	

	


§ INTRODUCTION

The problem of detecting an intruder (Intrusion Detection (ID) problem) using a network of sensors arises in various applications like tracking the movement of wild animals in the forest, house/shop surveillance for safety and security and so on. In this problem, the objective of the ID system is to track one or more intruders moving in the field of a wireless sensor network (WSN).  Typically, WSNs operate on limited power supply. This imposes a limitation on the number of sensors (energy budget) that can be switched ON over a time period when tracking the intruders and thus, constraints the maximum achievable tracking accuracy.  Hence, the problem focussed in this paper is to propose a novel ID algorithm that respects such resource constraints.

We consider a variant of this problem in which an intruder is moving in a special network configuration, that is a sensor grid in which the battery operated sensors are placed in each block of the grid. At every time period, the intruder moves from one block to another according to a specified governing dynamics. The ID system decides to keep the sensors in some of these blocks ON in order to track the intruder.  Whenever the intruder moves into a block where the sensor is ON, the position of the intruder gets recorded. Instead if he moves into a block where the sensor is OFF, then the intruder's position will not be recorded for that time period. The challenge here is to decide on the optimal number and the right configuration of sensors to be powered ON in order to balance the conflicting objectives of minimizing the energy consumption of the network and maximizing the intruder tracking accuracy.














Significant body of research exists that proposes solutions to the ID problem. In <cit.>, a comprehensive survey of adaptive sensing methods and POMDP solution methodologies are provided.  In <cit.>, a sensor scheduling algorithm has been proposed for detecting an intruder with a known trajectory. In <cit.>, mobile sensors along with the static sensors are deployed. They proposed an algorithm in which these mobile sensors move and detect the position of the intruder. In <cit.>, a method based on the extended Kalman Filter has been applied to the directional sensor network to select a minimum set of sensor nodes. 

In <cit.>, a POMDP for scheduling sensors has been formulated and Monte Carlo sampling along particle filters for belief state estimation has been proposed. This algorithm has also been applied in the context of autonomous UAV tracking <cit.>. In <cit.>, the ID problem has been formulated as a partially observable Markov decision process (POMDP) and two heuristic solutions have been proposed. Note that solving the POMDP for optimal solution is computationally intractable and one often resorts to heuristic POMDP solution. In the first method, they have proposed Q_MDP with an assumption of observation-after-control, i.e., position of the intruder at any time period will be known to the system from the immediate next and future time periods. Under this assumption, they show that the problem can be decomposed into separate sub-problems where individual decisions can be arrived at for each sensor. Each sub-problem can be solved using policy iteration <cit.>. As the policy obtained is myopic in nature, <cit.> developed a point-based approximation method based on the idea of Perseus <cit.>. The key idea behind this method is to find optimal action for a reachable set of simulated beliefs (see Section <ref>) and uses the assumption that the intruder moves in a special path, i.e.,  the transition probability matrix has a special sparse structure rendering only a finite number of path configurations to be actually feasible.  
	
In many practical scenarios, the curse of dimensionality effect (exponential growth of the state and action space of POMDP) renders the problem even more challenging. Point-based techniques attempt to alleviate the curse of dimensionality effect in POMDPs by performing value function back-ups at specific belief points rather than at all the belief points. The efficiency of these techniques depends on these selected belief points. In <cit.>, an effective way of selecting the belief points has been discussed. This technique is then combined with value iteration to arrive at a Point-Based Value Iteration (PBVI) algorithm. However, this method is not scalable as it uses full-width computation accounting all possible actions, observations and the next state in the tree search <cit.>.
In <cit.>, an algorithm VDCBPI that combines the Value Directed Compression (VDC) and Bounded Policy Iteration (BPI) techniques to tackle the state explosion problem has been proposed. Using VDC, the belief space is compressed into smaller subspace containing only the necessary information that is required to evaluate a policy. BPI is then employed to perform the policy improvement only on the reachable beliefs to determine an optimal policy. 

In <cit.>, a hybrid value iteration algorithm for POMDPs that combines the advantages of both the point-based techniques and the tree search methods has been proposed. In the first step of this hybrid algorithm, an offline computation is performed to obtain the upper bounds on the optimal value function. In the subsequent step, this computation is used in the online tree search for obtaining the optimal action. In <cit.>,  a two time-scale Q-Learning algorithm with function approximation has been developed to mitigate the curse of dimensionality problem. In their algorithm, policy gradient update is carried out on the faster timescale and Q-values update on slower time-scale.  The challenge however with function approximation primarily lies in choosing the right features for approximating the Q-values. While all the above mentioned algorithms mitigate the problem of state explosion, the problem of action explosion needs to be handled to obtain scalable solutions. 
    
In addition to the above mentioned POMDP model, many other frameworks have been considered in the literature. In <cit.>, a region prediction sensor activation algorithm (PRSA) has been proposed where a subset of active nodes based on the position and velocity of the intruder is selected.  Among the selected subset of nodes, the lowest number of essential nodes will be switched ON. In <cit.>,  a model in which sensor positions are arranged in the form of a polygon has been considered and an A-star algorithm was applied for selecting the optimal nodes in the polygon. 
    





    
Our contribution in this paper is to apply general RL algorithms to solve the POMDP formulated in <cit.> that tackle both the aspects of state space and action space explosion in a  novel way. Our algorithms do not make any assumptions on the structure of the network or the movement of the intruder and also do not use additional information at the controller. 

The following are our contributions:
 
 
  * We solve the problem of state space explosion arising in the problem of Intrusion Detection (ID) by using the MCTS algorithm. Unlike the prior methods considered for ID problem to mitigate the state space explosion like Monte-Carlo sampling methods and the point-based value iteration methods <cit.>, the MCTS algorithm searches the belief space in a sequentially best first order. 

  * We solve the problem of action space explosion in ID problem by suitably reformulating the action space of POMDP in <cit.>. This reduces the exponential number of actions to be considered in the ID problem to few finite actions. Furthermore, this makes it amenable to the application of the MCTS algorithm. 

  * Our reformulation of the action space is inspired from a simple ID_TG algorithm that greedily selects the top sensors (which implicitly ignores the current belief value). The key idea in our ID_γ_MCTS algorithm is to choose the top sensors dynamically based on the current belief value. 

  * Our  ID_γ_MCTS algorithm is a scalable solution to the ID problem without  any extra assumption. This renders our solution very practical. 




























	


§ POMDP FRAMEWORK FOR THE ID PROBLEM 

Let us consider a sensor grid where sensors are placed, one on each block of the grid.  The intruder moves from one block to another in the grid in each time period. The sensors that are kept ON in the grid send their observation whether the intruder was seen on that block to the central controller. Based on this information, the central controller finds the optimal action to be taken i.e., it decides how many and which sensors need to be switched ON in the next time period, and broadcasts this action to all the sensors in the network. This sequential decision making problem can be posed in the framework of Partially Observable Markov decision process (POMDP) <cit.>.

An MDP is defined via the tuple <S,A,P,K>. Here, S is the set of states that represent the different block positions of the intruder, A is the set of actions corresponding to the number and the configuration of sensors that needs to be switched ON at a given time period, P is the transition probability matrix governing the state evolution where P(s_k = i, s_k+1=j, u_k=a) represents the probability dynamics of  the intruder, i.e., probability of moving from the current block position, the state s_k=i at time k to the next state s_k+1=j at k+1 under action a, and K(s_k = i, s_k+1=j, u_k=a) corresponds to the single stage cost incurred by taking action a when intruder position at time k was i and the position at k+1 is j. The objective here is to obtain an optimal stationary policy π: S → A. This policy gives the optimal action to be chosen in the current block position of the intruder so that we could track the intruder in the next time period such that the long-term cost objective (constructed based on the single-stage cost function) is minimized. In order to determine the optimal stationary policy,  the ID system should know the state or position of the intruder at all the time periods. However, in our setting, whenever intruder moves to a block in which the sensor is not turned ON the intruder cannot be tracked. In this case, the position of the intruder at the next time instant will remain unknown. Thus, it is not possible to solve this problem directly in the framework of MDP.  We have to recast this problem as a partially observable MDP (POMDP) to capture the unknown state information. 

A POMDP <cit.> is formally defined as a  tuple <S,A,Z,P,O,R>. Here, the tuple <S,A,P,R> remains the same as in the MDP setup and  Z corresponds to the set of observations. As we do not directly observe the state, an observation corresponding to the state and action chosen will be obtained. This is modeled using the observation function O, i.e., O:S × A →π(Z), where π(.) is the probability distribution over the space of observations. In simple terms, we obtain the partial information or observation about the state in POMDP as opposed to obtaining the complete information about the state in MDP. As described earlier, in the ID problem the state information can become unknown based on our decisions and thus our problem lies in the realm of POMDP.

We now formally present the POMDP formulation for the ID problem <cit.>.  
	


  * Let n denote the total number of sensors in the network.
	

  * Let the actual position of the intruder at time k be denoted as s_k.
	

  * The stochastic matrix P of dimension (n+1) × (n+1) models the actual transition probability of the intruder movement between various blocks. Note that the transition between states modeling the intruder movement for this POMDP does not depend on our decision or action, i.e., which sensors have been turned ON. 
	

  * Action Space : At time k, let u_k denote the vector that indicates the decision on which sensors to be switched on for the next time period
	  
    u_k = (u_k,l)_l=1,…,n∈{0,1}^n,

	where 0 denotes the action to keep the sensor OFF and 1 denotes the action to keep the sensor ON. Here, u_k,l denotes the decision for the lth sensor in the kth time period. Note that the number of actions is exponential in the number of sensors and thus leaving us with a large number of actions from which we need to decide.
	

  * Observations: There can be three possibilities. If we track the position of the intruder, then the observation is the state of the system s_k itself. In some cases, we may not be able to track the position of the intruder. We let ϵ to represent this situation. The final possibility is that the intruder may have moved out of the network. Let  indicate this situation. We assume that if the intruder moves out of the network (i.e., observation =  ) this information gets immediately known to the controller. So, 	

    o_k+1 =  s_k+1,    if  s_k+1≠𝒯 and  u_k,s_k+1 = 1 
    ε   if  s_k+1≠𝒯 and  u_k,s_k+1 = 0 
    𝒯   if  s_k+1 = 𝒯.
	


  * The history or information content available at time k is: I_k =  {o_0,u_0,o_1,u_1,.....o_k,u_k}.	  
	  

  * The optimal action is obtained from the optimal policy according to:	  
 
    u_k = μ_k(I_k),

where μ_k denotes the optimal action selection function given the `information vector' at time k.
	   

  * State Space: As the number of stages or the time slots increase, the size of history increases and thus, it becomes difficult to compute the optimal policy using finite memory. So we need to develop a different representation for the state space. We solve this problem with the help of belief vectors. The  belief vector p is an (n+1) × 1 vector, in which p_k(l) indicates the probability of the intruder being at position l at time k. This evolves as follows: 
	 
    p_k+1 =    e_𝒯1_{s_k+1 = 𝒯} + e_s_k+11_{u_k+1,s_k+1 = 1}
       + [p_kP]_{j : u_k+1,j =1 }1_{u_k+1,s_k+1 = 0 },

	 
where e_i is the vector that represents 1 at position i and 0 at other positions. The notation [V]_S represents the probability vector obtained by setting all components V_i, such that i ∈ S to 0 and then normalizing this vector so that the sum of the components in V is 1. This is to account that we did not track the position of intruder, so we are sure that intruder did not move to sensor positions which are switched on.
	 

  * We define the single stage cost model for the ID problem using two cost components. The system incurs unit cost, if we do not track the position of intruder at a given time period and 0, if we track the position. Let us define

    T(s_k,u_k,s_k+1) =  1_{u_k,s_k+1 = 0},

where 1(.) is the indicator function. This cost T(s_k,u_k,s_k+1) captures the fact whether intruder is tracked or not. The other cost component C(s_k,u_k,s_k+1) provides constraint on the number of sensors that can be kept awake, i.e., 
    C(s_k,u_k,s_k+1) = ∑_l =1^n1_{u_k,l = 1}.

	

  * The long-run objective is to minimize the average expected tracking error while satisfying the limit on the number of sensors to be ON (energy budget constraints):
 
    min_u_k, k ≥ 0lim_m →∞𝔼[∑_k = 0^m-1 T( s_k,u_k, s_k+1)]/m
	
 subject to
 
    lim_m →∞𝔼[∑_k=0^m-1 C(s_k,u_k,s_k+1)]/m≤ b,

		
 where  𝔼[·] denotes the Expectation over state transitions and b specifies the energy budget (upper bound on the number of sensors that can be kept awake) in a time period.
 


  * Relaxed Cost Function: We modify the single-stage cost function to include the constraint as follows:

    g(s_k,u_k,s_k+1)    = T(s_k,u_k,s_k+1) 
        + λ× C(s_k,u_k,s_k+1),
 	
where λ∈ [0,1] is a suitable threshold for tracking error and budget constraints. If we set λ to 0, it is similar to having unlimited budget, in which case all the sensors will be kept ON all the time. On the other hand, λ = 1 implies there is strict budget constraint, in which case, all the sensors will be switched OFF. In this way, by optimally tuning λ, the algorithm could support different levels of tracking error and average energy budget.



Now we have modeled the ID problem using the POMDP framework. The uncertainty in the state can be removed by treating belief vector as our new state. We now have all the ingredients for an MDP and one would hope to utilize the standard dynamic programming methods like policy iteration and value iteration <cit.> for solving the MDP. However, these methods operate on finite state space whereas the possible belief vector, which forms the new state space for this problem is uncountably infinite. Therefore, finding an optimal policy for this problem by solving the MDP is intractable <cit.> leading us to focus on developing a suitable algorithm that can handle a large state and action space. This would ensure good tracking performance while meeting the energy budget constraints.



§ OUR ID ALGORITHMS

In this section, we describe our RL algorithms.












 §.§ Greedy Algorithm (ID_TG)

This is a simple greedy algorithm in which the top probable sensor positions the intruder might move to will be turned ON for tracking during each time period. The number of sensors that will be kept ON is decided based on a chosen parameter γ, where γ∈  (0,1). The first step of this algorithm involves obtaining the approximate belief vector for the next time period. Note the belief vector gives the probability of the intruder reaching various possible positions in the next time period. In order to compute the belief vector, we use (<ref>). Then we select those positions in the belief vector that sum up to γ starting from the highest probability value. 

We could view γ as a minimum confidence index on tracking the position of intruder. For example, consider the approximate belief vector for the next time period to be  [ 0.3,  0.3,   0.2,  0.2]. Let γ = 0.6. Then the sensors at positions 1 and 2 will be switched ON for the next time period and with confidence of 0.6, we know that intruder will be present in either position 1 or 2. 

We can see that this algorithm is very easy to implement and at the same time solves the problem of state and action space explosions. However, at every instance, γ chosen is constant and independent of the number of non-zero values in belief vector. Consider a scenario in which the belief vector is `dense'. By `dense', we mean that there are many non-zero probability positions in the belief vector whose values are very close to each other. Suppose we did not track the position of intruder in that time slot. Then, the belief vector grows further dense (see (<ref>)). In this case, we would like to use a higher γ so that we could have more number of sensors ON and track the position of the intruder. Otherwise, the belief vector would grow more dense resulting in bad tracking accuracy. On the other hand, if the belief vector is sparse, then even a smaller  γ would give better tracking. Also, we do not know, the best choice of γ for a given budget and the current belief. In summary, having a constant gamma value at every time period is not the right choice for optimal performance. However, the idea of using  γ as a handle for deciding the actions instead of directly searching over the number and configurations of sensors will play a crucial role in solving the action space explosion problem in our proposed algorithm ID_γ_MCTS.







 §.§ Monte Carlo Tree Search (MCTS)

In this section for completeness, we first describe the idea of MCTS  for determining the optimal decisions for an MDP and then we adapt this algorithm to the POMDP setting. For more details about the algorithm the reader is referred to <cit.> . MCTS has gathered a lot of attention in recent times due to its success in playing strategic games like GO <cit.>. The main idea behind this algorithm is to run multiple simulations (with the help of simulator placed at  the controller) from the current state to determine the best action in each iteration. We begin with a single node where the node represents the current state. Then, we select an action for the given state using the Upper Confidence Bound for Trees (UCT) rule. The general UCT rule is given in <cit.> as follows:


    UCT_action  =max_jX̂_j + C * √(log N / N_j),


where X̂_j denotes the estimate of the average/discounted long-run reward (negative of the long-term cost) one obtains by selecting action j starting from the current state, N denotes the total number of runs so far and N_j corresponds to the total number of runs by selecting action j.

In the beginning, all actions have 0 count, i.e., N_j = 0. Therefore, we can see that an unexplored action will have a higher probability of being selected on each simulation run. After all the actions have been explored, the action that has led to the highest reward collected, i.e, the term X̂_j gets selected. In this manner it balances both exploration and exploitation. When an action is selected, we obtain the single stage reward/cost and a next state. Then, a new node and a new edge is added to the tree, where the edge represents the action we have chosen and the new node represents the next state obtained. We continue this construction, adding new nodes and edges to the tree till the desired depth. In this manner, we obtain a Monte-Carlo sample trajectory and a sample for the  estimate of the long-run reward/cost.  We could obtain multiple trajectories by trying out different actions (including the tried action) in the current state for getting better estimates of the long-run reward. This procedure is now repeated again from the root node till the timeout <cit.>. At the end of the timeout, we pick the action that has maximum long-run reward.  This method helps in breaking the curse of dimensionality of the state space by sampling the state transitions instead of considering all possible state transitions to estimate long-run reward. If the exploration is done in an optimal manner, <cit.> has shown that the algorithm converges to the optimal policy.
 
 

  §.§.§ ID_MCTS Algorithm

In this algorithm, we run the MCTS <cit.> on our setting. That is, for the belief vector at time k, we run the MCTS algorithm and obtain the action to be executed for the next time instant using the UCT action selection (<ref>). At each iteration of the algorithm, the position of the intruder needs to be known for the simulator to generate the next state. We can estimate it from the belief vector in two ways. The first method involves sampling a position from the belief vector according to its distribution at each iteration. The second approach selects the position with maximum probability at every iteration. The second approach is very natural and we employ it in our algorithm.
 
From the experiments, we observe that the algorithm increases the number of sensors that are kept ON in the subsequent intervals if it does not detect the position of the intruder for a large number of contiguous time periods. Similarly, as the intruder gets tracked continuously, the number of sensors that are kept ON in the subsequent time periods reduces.
 
As discussed earlier, this algorithm solves the problem of state explosion. However, the algorithm requires all the (exponential) number of actions (the different configuration of sensors out of n block positions) to be tried out sufficient number of times before the timeout. There can be 2^n actions as n is the total number of sensor position actions possible. As the size of network increases, the action space exponentially increases and it takes large amounts of time to execute all the actions due to which some actions  might not be tried. Thus, the action we finally obtain at the end of the timeout will be `sub-optimal'.  We overcome the main difficulty due to large action space by appropriately changing the action space (all possible sensor positions) of the POMDP to a discretized parameter γ∈ [0,1]  that was fixed in the ID_TG algorithm and develop the final algorithm ID_γ_MCTS that solves the problems of both state and action explosions.  
 


 §.§ ID_γ_MCTS Algorithm

In the ID_γ_MCTS algorithm, we let the action space to be a predefined set of γ values in the range 0 to 1 (with a uniform gap of 0.05). Note that the number of possible actions for this algorithm is constant unlike the exponential actions in the earlier algorithms in the literature. We run MCTS to obtain the optimal γ value for the present belief vector. As we have discretized the action space, all the actions are chosen a sufficient number of times. The idea behind this construction is that it suffices to know how many sensors need to be kept awake in terms of γ during each time period instead of explicitly knowing the exact configuration of the sensors. We could then use this value of γ to select the top probable positions in the belief vectors as described in Algorithm <ref>. These sensor positions will be kept ON for the next time period. This process is repeated until the intruder moves out of the network. The complete ID_γ_MCTS algorithm is described in Algorithm <ref>.

As described above, Algorithm 3 imbibes the ideas of both ID_TG and ID_MCTS and totally solves the problems of state and action explosions. Moreover, we observe that the γ value at each time period is selected dynamically and is not kept constant, which is a significant drawback for the ID_TG algorithm. 

From the experiments, we observe that in few cases the actual path of the intruder and the path that we are estimating diverge. This happens whenever the belief vector gets too dense and γ selected is not very high. Then, we lose the position of the intruder and in this case, the belief vector grows more dense in the subsequent time periods. This results in the intruder not getting tracked for many contiguous time intervals and which affects the tracking accuracy. To overcome this problem, we introduce the restart mechanism. This involves switching on all the sensor positions that have non-zero probability whenever the belief vector has more than the threshold number of non-zero values. We observe this divergence problem occurs rarely and thus the restart cost can be practically ignored.









§ EXPERIMENTS AND RESULTS















We considered three different configurations of the sensor network. In our first setting, we considered a 1-dimensional sensor network with 41 sensors with probability transition matrix similar to the one considered in <cit.>. At the start of the experiment, the intruder is placed at the center of the network with the movement constraint that he could either move 3 positions left or 3 positions right from the current position. The restart threshold for this setting is set to 14. In the second setting, we ran our algorithms on a two-dimensional sensor grid of dimension 8× 8. The feasible movements of the intruder are left, right, down, up and along all the diagonals. In our final experiment,  we ran our algorithms on 2-D grid with dimension 16× 16.  In both the second and third settings, we generated the transition probability matrix randomly and the restart threshold is set to 20.

We averaged the results of our simulations over 30 time periods. The MCTS algorithm was run for 500 iterations in every time period. We computed the long-term cost in the experiments as the discounted sum of single-stage costs for learning the decisions. Note that by choosing the discount factor close to 1, the actions learned for the long-run discounted cost setting will be similar to the actions learned for the long-run average cost setting. We have set the discount factor α = 0.9. For the ID_γ_MCTS algorithm, we chose the γ parameter corresponding to the actions by discretizing the interval [0,1] in steps of 0.05. Thus, there are totally 20 discretized actions in the action space. The Q_MDP method is implemented by solving the policy iteration in <cit.> and making the assumption of observation-after-control, i.e., p_k+1 = e_b_k+1 at the controller. In the plots, the X-axis corresponds to the average number of sensors awake which is computed as the ratio of the total number of sensors switched ON during the run of the algorithm and the total number of time periods and the Y-axis corresponds to the average tracking error which is obtained as the ratio of the number of time periods in which the intruder is not tracked and the total number of time periods.





 






In our experiments, we run our algorithms for different values of λ and choose the λ value that meets the given budget constraints (the average number of sensors awake) and also has the lowest tracking error. We plot the average number of sensors awake and its corresponding tracking error. The λ value for which we obtained results for our ID_γ_MCTS on all the 3 settings is shown in Table (<ref>),(<ref>),(<ref>). Note that for different algorithms different values of λ could lead to the same average number of sensors.  As the size of the sensor network is large in the second and third settings, our ID_MCTS algorithm doesn't scale up owing to the action space explosion. Thus, we do not show results for ID_MCTS algorithm in the second and third plots and compare mainly our ID_γ_MCTS algorithm against Q_MDP given in <cit.>. All the results for ID_γ_MCTS algorithm are averaged across 10 simulation runs of the experiment.





 
 
 
 
 
 

















In the Figure 2, we observe that ID_γ_MCTS outperforms ID_MCTS. This is because the cardinality of the action space in ID_MCTS is 127 where as in ID_γ_MCTS the cardinality is 20. However, we can see that Q_MDP performs better than both our proposed algorithms. This is mainly because of the observation after control assumption (that we do not impose in our setting) and partly due to the small size of the sensor network. As noted earlier, this assumption imposes a severe constraint and we don't make this assumption. Thus, it is noteworthy that our algorithm performs well even without this assumption. In the Figure 3, we observe that the performance of ID_γ_MCTS  in comparison with Q_MDP has improved over a 2D sensor network. In fact, it performs better than Q_MDP until the average number of sensors is 3. In the Figure 4, we see the performance of the ID_γ_MCTS algorithm has further improved. To conclude, the ID_γ_MCTS performs better than other algorithms when the sensor network become very large which is typical in most of the practical applications.

As discussed earlier, since ID_TG, uses a constant γ its performance is poor (see Figs. 2 and 4). In summary, we can conclude that ID_γ_MCTS without making any strong assumptions performs and scales well.

















§ CONCLUSION

In this work, we proposed three algorithms for solving the problem of intruder detection under energy budget constraints. Our first algorithm ID_ TG is greedy, simple and easy to implement. However, due to its static nature, it does not yield good performance. Our second (ID_MCTS) algorithm is a suitable adaptation of the MCTS algorithm for the ID problem. This solves the problem of state space explosion problem, however, the action space is still large and remains to be handled. Our final algorithm (ID_γ_ MCTS) combines ideas from our earlier two algorithms and totally solves both the state and action space explosion problem and this algorithm is the first of its kind for the ID problem. In our MCTS based algorithms, as we only need to account for the belief vectors that are encountered during the run, which are finite, holds the key to mitigating the state space explosion. Further, as we suitably modify the action space using predefined set of γ values the action space explosion is also effectively handled. From simulations, we observed that the ID_γ_MCTS algorithm is our best algorithm when the network size becomes large and performs well without making any assumption on the intruder movement or the intruder position information. In the future, we would like to extend this problem when multiple intruders are moving in the sensor network. In this scenario, we could consider the possibility of more than one intruder moving in the network with possibly different transition probabilities and their movements could be correlated as well. Our objective would be to track the positions of as many intruders as possible satisfying energy budget constraints. 




§ ACKNOWLEDGMENT


The above work is supported by Joint DRDO-IISc Programme to Advance The Frontiers of Communications,
Control, Signal Processing and Computation.



 IEEEtran
 



