A learning automata-based algorithm to solve imbalanced k -coverage in visual sensor networks

1.1 Coverage in visual sensor network

In VSNs, one of the most significant issues is coverage referring to collecting data from a certain environment. Complexity of coverage depends upon the type of the sensors utilized; whether they are directional or omnidirectional. Fig. 1. displays how the directional and omnidirectional sensors work. In the former, sensors are assumed to have a disk-like sensing range; that is, a target is covered if it is positioned within the sensing range of a sensor. In the latter, sensors are assumed with a sector-like sensing range. It means that their sensing angle is limited; therefore, they can cover a target if it is positioned not only in their sensing range but also in their sensing angle [2].

OPEN IN VIEWER

Fig. 1

Omnidirectional and directional sensor.

Figure 2 explains the term “coverage”. In this figure, two sensors (S1 and S2) and five targets (T1-T5) are displayed. Each sensor in this figure has three directions each of which can monitor the targets positioned within the sensor’s scope and in the path of its activated direction (i.e., the yellow-colored direction). Remember that each sensor can activate only one of its own directions at each unit of time. Accordingly, in Fig. 2. T1 and T5 are not covered by any sensor. Sensor S2 covers only T3, while S1 covers no sensor currently. T2 and T4 will not be covered since they are not positioned in the path of an activated direction of any sensor in the network.

OPEN IN VIEWER

Fig. 2

Sensor covering target.

In general, coverage problem is addressed under three different titles: area coverage, target coverage, and barrier coverage [3]. The target coverage is aimed to determine a set of sensors to monitor some particular points within the area of study. However, the aim of the area coverage is to provide coverage on a part or the whole area regardless of any certain point, and the barrier coverage can be considered as the coverage with the goal of minimizing the probability of undetected penetration through the barrier. Generally, coverage falls into three different categories: simple coverage, k-coverage, and Q-coverage. In the simple coverage, each target is monitored by only one visual sensor. The problem is that in case the covering sensor functions inefficiently or exhausts its energy or if a preparatory blocks the line of sight, the corresponding target may become suddenly uncovered. Such drawbacks have resulted in shifting researchers’ attention towards the k-coverage into which the fault tolerance can be also incorporated. In other words, in k-coverage, each target is monitored by at least k visual sensors (k denotes a predefined integer constant). Note that a higher value of k results in higher accuracy in the monitoring operation [4, 5]. In the Q-coverage, different numbers of visual sensor nodes are appointed to satisfy the coverage requirement of different targets.

The objective of the k-coverage problem is to cover each target by k sensors. This end cannot be accomplished when the network does not contain enough sensors, e.g., in case of an under-provisioned network. To provide a better solution, there is a need for a new metric in such networks; here, the Balancing Index (BI) proposed in [1] is used. The BI obtained is given by Equation (1).

BI = ( ∑ t = 1 m Ψ t ) 2 m * ∑ t = 1 m Ψ t 2 * ∑ t = 1 m Ψ t km(1)ψ _t denotes the number of sensors that cover Target Ti, and m signifies the total number of targets existing in the network. For example, as can be seen in the following figure, a 3-coverage problem (k=3) is taken into consideration. To simplify Fig. 3, only the activated directions of the sensors are depicted.The BI was obtained for the two different conditions presented in Fig. 3(a) and (b). BI = ( 3 + 1 ) 2 2 * ( 3 2 + 1 2 ) * ( 3 + 1 ) 3 * 2 = 0.53 BI = ( 2 + 2 ) 2 2 * ( 2 2 + 2 2 ) * ( 2 + 2 ) 3 * 2 = 0.67 Therefore, this metric is suitable for recognizing the optimal coverage. Higher BI results in a better coverage.

OPEN IN VIEWER

Fig. 3

Balancing index.

In this paper, the target k-coverage problem is addressed, where there are not enough sensors to monitor all the targets; this shortage is generally known as under provisioned VSN. The whole problem, whose NP-completeness has been proved, is addressed as coverage imbalance problem [1]. This problem is significant mainly due to four reasons. First, directional sensors have a limited sensing angle, which causes them not to sense a full circular region. Second, sensors are susceptible to environmental damages and sensing data can get noised. This is why the sensing region requires to be covered by at least k sensors. Third, the under provisioned networks cannot provide a full k-coverage; thus, there is a need for providing a solution with a higher fault resilience. Fourth, the efficiency of the solutions proposed for this problem is dependent on the number of cameras activated for monitoring operation. Remember that the fewer activated cameras, the less amount of energy is consumed. Therefore, it is necessary to minimize the camera usage and provide coverage on each target in a fault-tolerant way.

The literature consists of several solutions to coverage imbalance problem; although, the up-to-date heuristic methods have not been taken into consideration despite their proved capabilities in solving the problems of NP-completeness. In this paper, an learning automata-based algorithm is proposed in order to balance the coverage using minimum number of sensors in under-provisioned networks. LA is used to address a problem in which some of the targets are monitored for k times, while others have remained uncovered or partly covered. This paper involves several experiments conducted to test the performance of the proposed algorithm. A comparison was made between the obtained results of the proposed algorithm and those of two greedy-based ones introduced in [1] in order to test the efficiency of the proposed algorithm. The results confirmed the capability of the LA-based algorithm and also its superiority over the greedy-based one in terms of solving the problem in hand.

The main contributions of the present study are as follow:

A new algorithm was proposed using learning automata to solve the imbalanced k-coverage.

The remainder of this article is organized as follows. In Section 1, the research already conducted on target coverage problem is presented. In Section 1, the problem of target k-coverage is discussed. In Section 1, the theory of LA is introduced. In Section 1, an LA-based algorithm is proposed to solve the problem in hand. In Section 1, the performance of the proposed algorithm is evaluated through several experiments. Finally, in Section 1, the whole paper is concluded.

5.1 Initialization

Three operations are involved in the initialization phase: construction of an LA network, formation of the LA action-set, and adjusting the action probability vector of LA. To create an LA network, multiple LA are first allocated to each target. The level of coverage required for the application determines the maximum number of automata involved in this step. For example, in case the application requires k coverage, the number of automata is fixed at k. This is because the output of each automaton is the selection of a pair. The selected pair may monitor only the target corresponding to the given automaton or it may monitor some other targets. If the first state takes place, the algorithm has to activate the other automata that are corresponding to that target (recognized as next-level target). The created LA network can be modeled by means of a duple 〈A, α〉, where A = {A_i,j| ∀ t _i  ∈ T, 1 ≤ j ≤ k} denotes the set of LA corresponding to the targets that exist in the network, and α = {α_i,j| ∀ A_i,j ∈ A} signifies the set of LA action-sets, where α i , j = { α i , j 1 , α i , j 2 , . . . , α i , j ri } defines the set of actions that can be chosen by learning automaton A_i,j (for each α_i,j ∈ α), and r _i stands for the cardinality of action-set α_i,j, which depends on the number of pairs that cover the target corresponding to the learning automaton. LA with variable number of actions are applied and a pruning rule is used in order to prune their action-set. Such action-set and pruning rule mainly avoid the selection of redundant pairs and selection of more than one pair from a sensor. At each unit of time, LA are in either active or passive mode, although in the initial stage, all of them are passive.

After the formation of an LA network, the action-set of LA needs to be defined. For this purpose, each learning automaton forms its action-set by assigning an action to each pan that covers its corresponding target. It means that with selection of an action, the automaton actually chooses a pan of the sensor so that both its corresponding target and the targets situated within the sensor’s sensing range can be under a full coverage. Let α _i  = { α i j | ( d i , j ) monitor target t _i }. Action α i j is corresponding to selection of pan (d_i,j) (as an active pan) made by learning automaton A _i . Following the action-set formation, it is turn to adjust the action probability vector. Let p = {p_i,j| ∀ α_i,j ∈ α} signify the action probability vectors and p i , j = { p i , j r | ∀ α i , j r ∈ α i , j } denote the action probability vector of learning automaton A_i,j, where p i , j r is corresponding to the choice probability of action α i , j r . If the algorithm configures the action probability vector of automaton A _i in such a way that the pans possessing high covering power can be chosen with a higher probability, then it can enhance the convergence speed. To do this, the algorithm attempts to configure the action probability vector of automaton A _i as follows:

p i j ( k ) = CP ( d i , j ) ∑ CP ( d i , j )(5) where CP (d_i,j) denotes the covering power of pan (d_i,j), and ∑CP (d_i,j) stands for the total covering power of all pans monitoring target t _i . According to Equation (5), a higher score is given to the pans with capability of covering more targets, and vice versa.

To further clarify, let us consider the example network depicted in Fig. 5(a). comprising four visual sensors and three targets. As can be observed in this figure, target t₁ is monitored by three pans ({d_1,2, d_2,1, d_3,3}), target t₂ is monitored by two pans ({d_1,1, d_4,2}), and target t₃ is monitored by two pans ({d_2,1, d_3,3}). Let us assume that the desired coverage level is 2. Therefore, at most, 2 automata are assigned to each of the targets. As mentioned earlier, the action-set of each learning automaton is formed by assigning an action to each pan that covers the target corresponding to that learning automaton. For example, the learning automaton A_1,1 that is assigned to target t₁ has three actions. This is because target t₁ is covered by three pans ({d_1,2, d_2,1, d_3,3}). Note that the action-set of the automaton corresponding to one target is similar to the action-set of other automata corresponding to that particular target. For instance, learning automaton A_1,2, which is allocated to target t₁, possesses three actions (see Fig. 7). The covering power of the pans is as follows: CP (d_1,2) =1, CP (d_2,1) =2, and CP (d_3,3) =2. Here, the total covering power ∑CP (d_i,j) equals 5. Thus, the initial action probability vector of automaton A_1,1 is defined as p 1 , 1 ( 1 ) = { p 1 , 1 ( d 1 , 2 ) = 0.2 , p 1 , 1 ( d 2 , 1 ) = 0.4 , p 1 , 1 ( d 3 , 3 ) = 0.4 } .

OPEN IN VIEWER

Fig. 5

An example network with four directional sensors and three targets.

OPEN IN VIEWER

Fig. 6

Three operations of initialization phase.

OPEN IN VIEWER

Fig. 7

Snapshot of the simulation environment.

As stated earlier, the proposed algorithm has been assigned with LA possessing variable action-set. This is because the action-set can vary during the operation time. Such variation may take place in two conditions; first, when a sensor has exhausted its energy; and second, when the action-set of a learning automaton is going to be pruned in a way to find a better action from among the available action-set. For instance, in case pan (d_i,j) gets disabled at stage q + 1, the action-set of learning automaton A _i is updated by eliminating the action corresponding to the pan. After that, the choice probability of the eliminated action ( α i j ) is fixed at zero, and that of the other actions ( α i j ′ ) is updated as follows:

p i j ′ ( q + 1 ) = p i j ′ ( q ) . [ 1 + p i j ( q ) 1 - p i j ( q ) ] j ≠ j ′(6) Consider the example network depicted in Fig. 5. Let us assume that automaton A_1,1 is to prune one of its actions at stage q. It is also assumed that the probability vector of automaton A_1,1 at stage q is p 1 , 1 ( q ) = { p 1 , 1 ( d 1 , 2 ) = 0.2 , p 1 , 1 ( d 2 , 1 ) = 0.4 , p 1 , 1 ( d 3 , 3 ) = 0.4 } . According to Equation (6), after pruning pan (d_1,2), the probability vector of automaton A_1,1 at stage q + 1 is defined as p 1 , 1 ( k ) = { p 1 , 1 ( d 1 , 2 ) = 0 , p 1 , 1 ( d 2 , 1 ) = 0.5 , p 1 , 1 ( d 3 , 3 ) = 0.5 } . Up to this step, the main three operations have been accomplished. The way a cover set is formed is explained in the next section.

In this phase, LA choose a subset of pans in a way to create an optimal cover set that can provide all the targets with a balanced coverage using minimum active pans in under-provisioned networks. To obtain such a cover set, several stages are run by the algorithm; each stage results in a cover set cooperatively constructed by LA. Afterward, the optimality of the created cover set is calculated by a random environment whose role is played by VSN. The task of environment is computing the total BI by the pans within the cover set and producing a response to optimality based on which the chosen actions are either rewarded or penalized. This process, which includes the formation of a cover set and updating the action probability vectors, is iterated until a cover set with the most balanced coverage is generated using the minimum number of active pans. The pseudo code of the proposed algorithm is displayed by Algorithm 1. In the following, the q-th stage of the algorithm is elaborated. In the beginning of the cover set formation process, the algorithm identifies the most critical target and then activates its corresponding automaton, which is known as critical automaton. Afterward, the critical automaton uses a pruning rule to prune its action-set. Next, it selects one of its actions corresponding to a pan covering its corresponding target. After that, the pan that is corresponding to the chosen action is added to the cover set (i.e., C _cur ); then, those targets whose balanced coverage has been provided are removed from T _cur . In the next step, the passive automata corresponding to the balanced coverage-provided targets together with the activated automaton (i.e., A_i,1) are added to the list of dominated automata (i.e., D _cur ). This helps to avoid not only the activation of these automata, but also the selection of redundant pans in the following stages. In other words, with selection of a pan covering multiple targets, the automata that are corresponding to the covered targets must be added to D _cur .This way, the algorithm is able to choose only the automata whose actions cover a new target (i.e., a target whose balanced coverage has not been provided yet).

The whole process explained above continues until all targets are provided with balanced coverage. Note that as the under provisioned environments in their nature lack sufficient sensors for monitoring operation, we have to take into consideration the issue of critical targets. In each stage of this system, the algorithm determines the most critical target and activates its corresponding automaton in a way to finally achieve a balanced coverage. The ultimate aim of activating these critical targets is to let the sensors activate only one of their pans that covers a critical target and to avoid the activation of the pans corresponding to non-critical ones. This results in preparing more pans to cover the critical targets, hence providing a more balanced coverage on the whole under provisioned environment.

Pruning rule: This rule is used to prune the action-set of the activated learning automata in two ways: avoiding the addition of more than one pan of a sensor into each cover set, and preventing from the selection of redundant pans. The pruning rule disables the actions corresponding to three cases: the pans selected before, the pans covering the balanced coverage-provided targets, and the other pans of a sensor that has currently a pan in an already-constructed cover set. The results of the pruning rule are a reduction in the number of actions and an increase in the convergence speed. Such a condition results in reducing the algorithm running time.

The output of the above process is a cover set comprising a set of pans. The next step is calculating the optimality of the constructed cover set. To do this, we make use of a factor termed BI [1]; higher value of the BI is normally associated with a better coverage rate. Next, a comparison is made between the value of BI and a dynamic threshold (i.e., T _q ). Based on the result, the selected actions of the chosen automata are either rewarded or penalized. If the BI is higher than the T _q , the selected actions of the activated automata are rewarded; otherwise, they are penalized. Once the initialization process begins, T _q is set to zero; the reason is that our aim is to maximize the BI. In each stage, if a cover set is found, whose BI is equal to or greater than the dynamic threshold, the set of pans gathered in that cover set is kept as the best solution ever found; in addition, the value of T _q is set to the BI value of that cover set. When the action probability vectors of the activated automata are updated, the q-th iteration ends with re-enabling the disabled actions of each activated learning automaton. As the algorithm operation goes on, the automata learn how to choose a subset of pans in such a way that they can ultimately create a cover set with a maximally-balanced coverage through activating the minimum number of pans. The proposed algorithm ends in two conditions: either the probabilities of all selected pans become greater than a definite threshold, or the number of created cover sets gets higher than a certain threshold. The final output of the algorithm is a cover set capable of providing the most balanced coverage using the minimum number of activated pans. An example network depicted in Fig. 5. is presented in order to show the cover set formation process performed in the proposed algorithm. Each round of the proposed algorithm comprises several stages. In the following, a possible execution scenario of the algorithm is explained.

To begin the cover set formation process, first, the algorithm identifies the most critical target and then activates the learning automaton corresponding to that target. In this exemplified network, let us assume that target t₁ is selected. Therefore, the first learning automaton corresponding to this target (i.e., A_1,1) is activated. Afterward, automaton A_1,1 prunes its action-set by means of the above-mentioned pruning rule and chooses one of its actions. Assume that the learning automaton has chosen the action that is correspondent to the pan (d_3,3). Next, the chosen pan (d_3,3) is added into C _cur . After that, set T _cur is updated by removing the targets whose k-coverage has been already provided. As the k-coverage has not been so far provided for any target, no target is eliminated from the list of T _cur . Next, the activated automaton (i.e., A_1,1) and the passive automata that are correspondent to those targets whose k-coverage has been provided by (d_3,3) are added into D _cur . Up to this stage, the cover set, the list of uncovered targets, and the set of dominated automata are updated to C _cur  = {(d_3,3)}, T _cur  = {t₁, t₂, t₃}, and D _cur  = {A_1,1}, respectively.

In case the set T _cur is an empty set (that is, the k-coverage of all the targets has been provided), the current iteration is terminated. Otherwise, the learning automaton corresponding to the next critical target is activated. The automaton then prunes its action-set. Let us assume that the next automaton that needs to be activated is A_1,2. Assume that (d_2,1) is selected as the second pan. As can be observed, with selecting pan (d_2,1), target t₁ is provided with k-coverage (i.e., k=2); whereas target t₂ lacks the k-coverage. The process of activating a critical automaton and choosing an action goes on until all the existing targets are provided with k-coverage, or no automaton has remained to be activated. Assume that the constructed cover set is C _cur = {(d_2,1) , (d_3,3) , (d_4,2)}. Then, the BI provided by the cover set C _cur is computed. Afterward, the value of the BI is compared with the dynamic threshold T _q .

In the first iteration of the algorithm, T _q is set to zero. Therefore, the BI value (i.e., 0.772), which belongs to the constructed cover set, is greater than T _q . As a result, the threshold is set to 0.772. In case the BI value of the cover set is greater than the dynamic threshold, all activated LA give reward to their chosen actions using the reinforcement scheme L_R-I and they also re-enable the actions formerly disabled. This condition enhances the probability of selecting the pans existing in the cover set to be applied to future iterations. The process of cover set construction is repeated until the stopping criteria are met. At each iteration, the pans are rewarded when they succeed in constructing a cover set with a BI value greater than T _q ; otherwise, they are penalized. Finally, the algorithm selects the cover set with maximum value of BI as the output of current round. BI = ( 2 + 2 + 1 ) 2 3 * ( 2 2 + 2 2 + 1 2 ) * ( 2 + 2 + 1 ) 2 * 3 = 0.772

5.3 Time complexity

To measure the time complexity of the proposed algorithm, we consider the following parameters. Here, |S| signifies the number of sensors in the network, while |T| shows the number of targets. In each round of the algorithm, a subset of sensor directions capable of covering targets is selected; then, an activation time is assigned to the selected subset, and the energy of the sensors is updated. If the remained sensors are capable of providing k-coverage for all targets, a new round of algorithm begins. Accordingly, the complexity of the algorithm is as follows. ( ( | S | - | T | * K ) ( | T cur | * | D cur | * | C cur | + | C cur | ) )