Multi-Channel Access Model

We consider a multi-agent Ad-hoc network as being created by agents themselves in an open environment, with set consisting of N distributed agents. Although the multi-hops information sharing method can make each agent finally gain full knowledge of the global state, this consumes a lot of communication resources and also deteriorates the system’s performance. Therefore, an agent makes decisions based on its limited observations, and the entire system would still be partially observed. The network consists of a set of contiguous, orthogonal (non-interfering) and homogeneous channels (e.g., 3 such channels in IEEE 802.11b/g and 12 in IEEE 802.11a), denoted by CH = {c₁, c₂, …, c_K}. The available channels are also numbered from 1 to K, and we assume that N > K agents are seeking channel opportunities in these K channels.

We should recognize that agents can only access channels if the sensed channels are idle. As shown in Fig 1, a time slot consists of 3 parts: sensing, transmission and acknowledgment. Because of practical considerations, agent r_i can sense a set of channels and a subset of sensed channels to access. Limited by its hardware constraints, r_i can sense {C₁} channels, ({C₁} ∈ {CH}, |C₁ | <K) channels and access {C₂} channels, ({C₂} ∈ {C₁}, |C₂| < |C₁|) channels. State statistics of the K channels follows a discrete-time Markov process with 2^K states, where state is either idle or occupied. The channel sensing and access decisions are made to maximize agents reward by fully exploiting the sensing of vacant opportunities and the history statistics.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Multi-agent Multi-channel Access Opportunities.

Several agents are independently seeking available communication opportunities in two channels, a suitable mechanism is required to ensure smooth communication and low conflicts.

https://doi.org/10.1371/journal.pone.0145526.g001

Multi-channel Access Decision Problem

For some reasons, some agents change the status of stable channel access(switch to other channels, increasing the data flow or strong interference, etc.), and other agents need to adjust the channel access based on their limited observation so as to ensure the global rational use of resources and QoS. Therefore, the multi-agent multi-channel access problem can be described as cooperative searching for available resources in a partially observable multi-channel network. As such, this can be modeled as a Dec-POMDP problem in terms of interdependence. A finite-horizon Dec-POMDP can be defined as a tuple , where

• S = {s₀, s₁, …s_n} denotes the finite set of network states.
• A_i = {a₁, a₂, …, a_m} denotes r_i’s available actions set. At each time step, all the agents in take a joint action .
• T denotes Markovian state transition function. P(s′|s, Λ^t) denotes the probability that doing action Λ^t and being in state s then going to state s′.
• denotes the set of joint observations of all the agents and is the observation by r_i at time t.
• O denotes observation function, which specifies the probability of joint observation O(Ω^t|s′, Λ^t).
• denotes the reward value obtained from taking action Λ^t in state s.
• p₀ = {B⁰, s₀} is the initial belief and state distribution.

Action a is determined by the policy π: b→a, which is the function that maps a belief state to the action that an agent should execute. = ×_{1 ≤ i ≤ t−1}{ω^t−1} denotes the known network states.

Formally, most policies can be represented as decision trees. We use Q_i to denote the possible policy space for agent r_i, and Q_−i denotes the sets of policy trees for all agents except r_i. With a programming approach, it is required that we generate incrementally the sets of useful policies for each agent. Thus, a joint policy Π = ×_{i ∈ N}{π_i} is a vector of policy trees. Evaluating a joint policy can then use the following formulation: (1) where Π(ω) is the joint policy of subtree selected after observation ω. So we get the utility function as: (2)

Therefore, the essence of this framework is to find a set of n policies to maximize a total reward function from finite horizon T under initial belief state p₀, and the expected joint reward is given by .

Resource Awareness Policy Generation

From the idealistic view of the Shannon’s theory [22], the optimal available resources under an ideal state for r_i is: (3) where B_n is the channel bandwidth and p_m is the channel state misperception probability. and respectively denote the noise variances from other agents and r_i affected channel ch_i. and respectively denote the communication power of other agents and r_i. g_i is the channel sensing gain. However, in the presence of sensing error, not only the sensing and access policy but also the operating characteristics of the channel sensor affect the performance of the network and the interference perceived by all the agents. The loss of resources caused by interferences are: (4)

As a result, agent r_i can obtain the idealistic expectation channel resources in C₂ as: (5)

We can see that the agent can access the network interval sequence independently, and this follows the same negative exponential distribution G(t) = 1−e^{−μ_i t}, where μ_i is the channel free probability. Thus, we can get the probability of agent r_i to choose and access channel c_j as: (6)

We can use and to denote the probability that agent r_i select channel c_j and the probability of channel c_j being sensed idle respectively. is the Signal to Interference plus Noise Ratio (SINR) for agent r_i from the other agents in channel c_j. This problem cannot be solved in one stage, and as such, should be done in an iterative manner. Therefore, based on the above analysis, we use Eqs (5) and (6) to obtain the policy tree and a target BER equal to , where σ₁ and σ₂ are Lagrangian multipliers, b_{i, n} is the number of bits per symbol in channel c_n, and ζ_{i, n} is the Signal to Noise Ratio (SNR) for the receiver agent r_i in channel c_n. Consequently, we adopt the utility function design in [23]: (7) where the product is the bandwidth (i.e. transmission rate), is the size of access channel in Hz, k_i is the spectral efficiency² in bits per symbol per Hz due to adaptive modulation, and μ₁ and μ₂ are constants that depend on the communications protocol and agent communication system performance, respectively. cost_i is the communication consumption, which relates to the agent’s hardware system. The optimal policy is therefore π* = argmax[U(b, π_i)].

Dynamic Local Search

Based on the model described above, agent r_i cannot get a full view of the state of the system, since it can only use its observation to update its actions. The goal of this problem’s model is to come up with a joint policy Π* = , which can maximize the expected reward of all the agents over a finite horizon. The belief space is a sufficient statistic [21], and can be independent of the decision time. We remark that r_i can only infer what action its neighbors may take, but the inference or conflict is inevitable. At each time slot, we can compute the expected value of a policy as follows: (8)

Solutions to a finite-horizon POMDP can be represented as a decision tree, where nodes denote the actions and arcs denote the observations. Similarly, solving a finite-horizon Dec-POMDP with known state space can be formulated as a multiple vector of horizon T policy tree searching process.

Algorithm 1: Resource aware policy search for agent r_i.

Require:

 Set g₀ = 0; ℜ₀ = {Φ}; ℜ ∈ Q_i;

Ensure:

  ;

1: for each r_i do

2:  random select ploicy candidates set {η_i}from ℜ;

3:  g_i(t) = ;

4:  for all π_i ∈ η_i do

5:   excute π_i to obtain ω_t;

6:   compute g_i(t);

7:   if then

8:    π* = π_i;

9:   else

10:    prune π_i and get new

11:   end if

12:   = argmax {Π′ ∈ ℜ|V(η′) > R(η)};

13:  end for

14:  return π* → Π*;

15: end for

As shown in Algorithm 1, ℜ ∈ Q_i denotes the random initialized policy space with completely unspecified candidate policies. g_i = − is the difference in value between the expected policy and the current one. In the beginning of each searching round, randomly select η₀ from ℜ, if g_i’s value is bigger than , then map π_i to . If not, prune the inappropriate π_i and search new . We assume that the partial policy with the highest heuristic value is selected, and the provided value of is the lower bound for an optimal joint policy, which can be used to prune the search space. If r_i has the minimum g_i value in one round, then it will get priority to access its {C₂}. Other agents are constantly updated to the new strategy, and after finite times evaluation and exploration that they can get all the apposite policies to fix the g_i value. In a limited belief space, by retrieving the limited policies space, and the state transition probability approaching the optimal values, similarly, the decision can approach the optimal policy . At each time slot, the computation of g_i performs a summation over all possible network states and observations, and so the time complexity of this algorithm is O((|S|⋅|Q_i|)^T). The value of a policy is highly dependent on the other agents’ beliefs and the current system status, whereas, without sharing, the policy regeneration can only be derived on the basis of the reckoned joint policies. We define the policy update function as: (9) where Ξ_π represents the conditional expectation given that policy π_i is employed, and B₀ is the initial belief, which can be the stationary distribution of the network state. is the knowledge, consisting of two parts: channels observation ω^t and the known status . The search strategy performs a summation over all possible network states from agents’ observations. Since each policy specifies different actions over possible histories of observations, the number of possible policies for agent r_i is . In consequence, the time complexity of finding the optimal policy by searching this space is: .

Neighbor-Aware Policy Generation

In order to solve a single-agent POMDP, we introduce neighbor policies as a new parameter to the knowledge δ_i, and the joint policy of n neighbors is formulated as . Therefore, we augment the state space to be , where the second set is the state variables of the other agents’ beliefs. In consequence, we resolve and upgrade the Dec-POMDP to a POMDP model as a tuple . All variable definitions remain unchanged, and to accomplish this, we factor the transition distribution into two terms: , and the upper bound of the POMDP value function can be reached through the complete observation. In consequence, the belief update function can be denoted as: (10)

The value function of a POMDP is defined over the space of beliefs, where a belief state b represents a probability distribution over states. The optimal value of policy π* can then be approximated as: (11)

Heuristic Local Policy Search

Modeling our problem as a POMDP model is to search for the optimal policy π*, and maximize the expected reward over a finite horizon-T policy distribution over states. Formally, a belief state b_t+1 = P(s_t+1|δ^t, δ^t−1, …., δ⁰) is a probability distribution over states conditioned on knowledge . In order to avoid a heuristic with unbounded input (the knowledge can be arbitrary), a traditional approach is to learn a mapping from belief states to actions, which is from the known knowledge . But in discrete worlds, beliefs can only be represented by a state with probabilities. We represent the regeneration process of belief states by sampling. A sample x is annotated with a numerical importance factor to account for the difference in the sampling distribution.

Heuristic search is based on the decomposition of the evaluation function into a sequence of exact sub-evaluations. As aforementioned, we denote q^t as an arbitrary depth t policy vector extract from policy vector Q^T, and {q^t, Q^T−t} constitutes a complete policy vector of depth T. This allows us to decompose the policy vector into any t depth vector, and the value of the completion is: (12) where H(q) is the heuristic function, and the value of Q^T−t depends on the previous execution and the underlying state distribution at time t. In consequence, we can describe the heuristic function as: (13)

As in Algorithm 2, randomly extract a sample q^t from the possible policy space Q, and each node in the tree is a belief state b_i. For each encountered state x_i, belief state b_i is updated to include the new state . In each sample searching, the agent selects the policy b′ at the greatest value. The sampling path terminates when it reaches a sufficient depth of the bounds of T_q, and goes back to the root so as to improve the upper and lower bound estimates. The search moves towards π* only with the acceptance probability P(b⁰), otherwise it remains at b′. At this point, the node b⁰ becomes the root of the new search tree, and the remainder of the tree is pruned, as all other beliefs are now impossible. The search in new sample trees would not stop until there appears a policy to meet the resource requirements. Obviously, under a statistical hypothesis, the searching process converges to the expected distribution at a rate of , and H denotes the sample size.

Algorithm 2: Sample extract-based search for agent r_i.

Require:

 random extract sample from Q; v(b₀) = 0;

Ensure:

  ;

1: random extract sample from Q;

2: for each do

3:  qualify T_q;

4:  repeat

5:   for each state x_i from b_i do

6:    compute

7:    if b′ ∈ q^t then

8:     continue to next b_i;

9:    else

10:     add b′ to T_q;

11:     if U(b)<U(b′) then

12:      b⁰ = b′;

13:     end if

14:    end if

15:    prune q^t other than b⁰;

16:   end for

17:   generate new q^t′ from root b⁰;

18:  until

19: end for

20: return π*;

A concise example is described in the following to illustrate our algorithmic process. We demonstrate a minimize-scale: two agents coordination. For each agent r_i, its action space has two actions {Listen, Switch}. These actions achieve channel perception, switch to other channels or stay in current channel, respectively. Each agent can sense two channels and choose one to access. The coordination has two states: establish a connection (R) or fail (W), denoted by S = <R, W>. The channel state misread probability is 0.3. The action-state transfer probability table as in Table 1, the initial joint action is <S, S>.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. State-action transfer probability.

https://doi.org/10.1371/journal.pone.0145526.t001

We define the highest reward (+50) to be the case when both agents get a good resource acquisition. A lower reward (-20) is agents’ access in two different channels, and they can connect but with low resource acquisition. The worst case is lose connection (-100), and the cost of Listen is (-10). As shown in Fig 2, both agents start out with an initial belief state of b(s) = 0.5, and the discount factor is γ = 0.9. The first joint action at this belief is < Listen, Listen >, the reward is (-20). As such, each agent has its own observation and network belief. In order to get a better reward, each agent removes all of the joint beliefs that are not consistent with its entire observation. After policies sharing, there is only a single possible belief b(W) = 0.033, and the optimal joint action for this belief is < Switch, Switch >.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Beliefs Update Processing.

A 3-step policy tree captured from Table 1, each of which can be conditioned on the outcome of previous actions. Each node is labeled with the action that should be taken if it is reached.

https://doi.org/10.1371/journal.pone.0145526.g002

It should be noted that there exists hidden competitions between agents for the finite resources (each agent wants to get more resources), that is, there should exist optimal joint policies to reach the Pareto optimal. But, it is infeasible for Dec-POMDP model because of the partial observation that we briefly described in the previous sections. In our design, it can finally reach the approximate Pareto optimal after a finite search. Therefore, it means that, in the finite belief space, there exists a pair of policies π = (π₁, π₂) such that: . That is, for each agent, playing π_i gives an equal or higher expected resource than playing . So both policies are best responses to each other.

Implicit Competition Game Model

According to the aforementioned, the access problem can be defined as a cooperative game , where the definitions of and S are unchanged, D_i = ×_{1 ≤ i ≤ k}{π_i} is the finite set of policies available to agent r_i, denotes the reward. We use θ_i(π_i) to denote the probability distribution assignment over policies available to agent r_i. Since agents select their policies simultaneously, agent r_i’s belief about the other agents’ likely policies can be denoted as θ_−i. If we define V_πi(s, θ_−i) = ∑_d−i θ_−i(d_−i)V_i(π_i, d_−i), then denotes the best response function of agent r_i, which is the set of policies for agent r_i that maximize its value of some belief about the policies of the other agents d_−i. Any policy that is not a best response to some belief can be abandoned.

Algorithm 3: General framework of competition equilibrium.

Require:

 ∃ θ_−i = {b₁, …, b_i−1, b_i+1, …};

Ensure:

 ∀ s ∈ S and ;

1: for each episode do

2:  Initialize get state S and D;

3:  repeat

4:  

5:   if then

6:   

7:   else

8:    return π_i to D′;

9:   end if

10:  until

11: end for

12: return π_i → π*;

As in Algorithm 3, in a cooperative game, the reward functions for the game correspond to the reward functions of the POMDP, and an agent’s belief is a distribution synthesization over the possible policies of the other agents. For each agent r_i, a belief is defined as a distribution over S×D_−i, where the distribution is still denoted by b_i, and the utility of b_i is: (14)

Given the set of policies and the reward function for a horizon-t’s game, the sets of policies and value functions for the t horizon game are constructed by exhaustive backup. When a horizon-t’s POMDP is represented in the normal form with implicit competition, the policy sets include all depth-t policy trees. Each policy profile is associated with a belief vector , reresenting the expected t-step cumulative reward achieved for each potential start state by following an apposite joint policy, whiles the size of the policy set for each agent r_i is more than , which is doubly exponential in the horizon-t. Because of the large sizes of the candidate policy sets, it is usually not feasible working directly. The search algorithm (Algorithm 2) we present in this paper only partially alleviates this problem by performing iterative elimination of dominated policies at each stage in the construction of the normal form representation, rather than waiting until the construction completes. Considering an N-player implicit competition game, we can formulate the game subject as: (15)

In this constraints equations, r_i’s desired reward is no less than , and this guarantees a minimum level of resources achieved by each agent. v(b_{i, n}) is value of the belief distribution of agent r_i’s access in channel c_n, is the variance of the white Gaussian noise, and . is the expected resource reward, and G_{i, j, n} is the channel gain between two agents in channel c_n, and all policies should meet . The existence and stability of the competition will be investigated in the following subsection.

Evolutionary Equilibrium Analysis with Replicator Dynamics

In a multi-agent multi-channel access game, the stable state can be defined as the following: a joint policy Π* is and only if, for each agent and an arbitrary policy π in its policy space, v_i(π*) ≥ v_i(π, θ_−i) is always satisfied. Consequently, the process of this game can be modeled as a replicator dynamics, and this can be derived for each agent separately.

We consider a concise example with two new access agents r₁ and r₂. These agents appear first in the network with some spared channel opportunity (i.e., c₁ to c_n). With this specification, we analyze the evolutionary equilibrium for both deterministic and stochastic models. For the hidden competition among agents, the evolutionary equilibrium can be obtained as Replicator Dynamics solution [25], where χ_i denotes the proportion of the eager channel resources that agents can get, and the replicator dynamics can be defined as the following: (16) where is the estimated average reward for other agents in channel c_i, and the function U is defined in Eq (7). With the two agents case, the evolutionary equilibrium is obtained as the solution of the following equation: (17) where the terms on both sides of the equation are the rewards that the new access agents can get from their beliefs b₁ and b₂, respectively. Accordingly, the stability of the evolutionary equilibrium can be analyzed using the following Jacobian matrix: (18) where (19) (20) (21) (22) where Z_i specified as and . The two eigenvalues of can be obtained from , and the evolutionary equilibrium is stable if these two eigenvalues have negative real parts [23].

Approximate Fair Maximization Policy Analysis

Among the different Cooperative Game solutions, it is important to note that the issue about fairness in this context, e.g., new access agents, is different from the case of resource occupation among the early-existing agents in the network. In this section we will analyze approximate fairness of the game, and discuss the feasibility of the proposed neighbor-aware channel access scenario in the previous section. In this scenario, the approximate Pareto optimal result can satisfy all agents’ minimum requirements. Typically, if a channel is occupied, the other agents should be denied access to the frequency band.

In the proposed competitive game model, a virtual-feasible resource access assignment set is existent, hence, we can use a bounded set = , which denotes the minimum resource required of the game. The vector r = represents the set of rewards for the access agents. The reward vector in the K channels can form the fairness problem . It has been shown that there exists a unique equilibrium, which can be calculated by Eq (17): (23)

Hence, we can use Eq (23), to confirm the selected solution for stable point in the previous section. This is also the point where “egalitarian” solutions of the game come in, and one such method is applicable to the equal gains principle, a Pareto optimal. For the 2 agents case in the previous section, the proportion χ_i in Φ, which is weakly efficient and satisfies the equal gain condition , is called the “egalitarian” solution. As mentioned earlier, in our resource access method, the stable acts as a marketplace where the primary and secondary systems can do bargaining. The fair solution for two agents about one channel access is at the intersection of the egalitarian solutions: (24)

Condition Eq (24) dictates that the operating point should be on the boundary of the minimum region. Therefore, the intersection gives the unique approximate fairness solution. For a N agents game, the fairness problem Eq (23), should be solved by calculating the χ_i, i = 1, 2, …, N. To verify the case, we note that the stable point in the proposed design is also on the perpendicular boundary to (24) at its intersection. The corresponding optimization satisfies Eqs (15) and (17), defined by , which is subject to , i = 1, 2, …N. It is straightforward to confirm the solution of Eq (18), as it satisfies the description at the beginning of this section.

Resource Lost Rate

As in Fig 3, the results show that the influences of different channel access strategies, have direct impact on the available channel resources. The axes represent the number of agents and the resource loss rates. Agents adopt a RANDOM method, and with the expansion of scale (20–200, from 0 agent there has no conflict), the congestion and resource loss rates continue to rise closing to 90%. Meanwhile, in our algorithm, agents communicate with their neighbors to exchange decision policies, and acquire a better joint behavior through continuous negotiation and iterations (the average max amount of loss is 65.38%, the average sample variance is 8.12%), the variance shows that our algorithm is more stable.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Resources Loss Rate.

With the increased size of the agents, the randomness of the RANDOM method increased interference between agents, which brings down the network resources utilization. OPTIMAL method can maintain an efficient use of the resources, but its time consumption is much larger than the self-decision methods. POMDP methods maintain a relative balance to the above methods.

https://doi.org/10.1371/journal.pone.0145526.g003

The OPTIMAL method can provide a better result, but the resource consumption of global consultations could not be avoided (the average max amount of loss is 21.92%, the average sample variance is 5.67%). Furthermore, due to agents’ misperception and accessing, the resource loss (conflicts) is inevitable, and will increase sharply with the expansion of the agents.

Resource Available Rate

With the premise of partial observation, we set the RANDOM and our algorithm to start from the initial belief probability 0.5, as shown in Fig 4. But the difference is, our algorithm can reach an average resource showed at 52.67% and the average sample variance is 3.32%. RANDOM’s resource obtain rapid descent, and when there has 200 agents, the available resources only remain 33.48%, but with 12.16% average sample variance. When the number of agents and network resources are relatively homogeneous, the available resources rate can approach the expected value. Then due to the increase of the agents’ number, the available rates decrease. The OPTIMAL can keep an average resource obtained at 68.23% and with a very stable average sample variance 2.37%.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Resources Available Rate.

Under the same experimental setup, with the increasing size of the agents, RANDOM method reduces the resources available for each agents. Because of neighbor’s awareness in POMDP, the agents can be maintained in a state of relative balance (less variance than RANDOM).

https://doi.org/10.1371/journal.pone.0145526.g004

Obviously, agents can obtain more resources with our design than RANDOM provides. Especially, with the increase of the agents’ number and passing time (agents can exchange information with neighbors and accumulate from known knowledge), the resource availability rate remains in a relatively stable state until agents reaching network’s saturation.

Available Resource in Different Interaction Frequencies

In this simulation, we test the average available channel resources for the new accessed agents under different interaction frequencies of the other agents in the network. We set 5 channels and 100 per slot new accessed agents, which are uniformly distributed in these 5 channels, the max agents number is 1000. The interaction frequency of the other agents was set to r = [0.2, 0.4, 0.6, 0.8]. X-axis represents the agents’ number. As in Fig 5, we can find two significant changes for the new accessed agents: with increasing numbers of network agents or the higher interaction frequency, the available resources decline. In addition, when the number of agents is more than the maximum number the network can support, the available resources for the entire network will be sharply reduced.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 5. Available Resources in Different Interaction Frequencies.

In different interaction frequencies, the available resources shrink with the increasing number of agents. Similar to the allocation of limited resources in human society, the average gain decreases with the increasing number of people. Experimental results are consistent with the general understanding.

https://doi.org/10.1371/journal.pone.0145526.g005

According to the experiment’s results, we can make a bold hypothesis that while the number of agents and the resource relatively balance, there should be a suitable interaction frequency that makes each agent obtain available resources to maximize its utility.

Resource Available in Different Assignments

In this simulation, we discuss the relationship between different team sizes when agents access channels under different assignment. We divide 100 agents into different team sizes, and allow them to access 5 channels. Simulation results are shown in Fig 6. Caused by new access agent, blocking rate of channel will increase and influence the original agents due to the partial observation.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. Resource Available in Different Assignments.

In the 5 specified channel, the more uniform distribution of the agents, the higher the probability of their available resources, whereas the performance reduces (more crowded, no elimination of competition that makes the average income is lower).

https://doi.org/10.1371/journal.pone.0145526.g006

Obviously, we can see that when the combination in each channel distribution is more uniform, the greater resource available, as assignment [10, 20, 20, 20, 30] and [20, 20, 20, 20, 20]. In an extreme access situation with [100, 0, 0, 0, 0], all agents are in one channel. When communication demand escalates, all agents almost have no chance to obtain available resources. From above analysis, we can conclude that agents will gain more available resources when they distribute more uniformly.

Resource Available Comparison

Fig 7 displays the contrast of channel resources awareness between our algorithm and RANDOM. In this simulation, we set 100 agents with freedom interactive frequency.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. Resource Perception of 500 Tests.

To illustrate the variances in the 4 aforementioned simulation results, this figure gives the resource perception comparison in 500 tests between POMDP and RANDOM.

https://doi.org/10.1371/journal.pone.0145526.g007

It can be seen that, with 500 tests for the same channel (distribution within the circles), agents can obtain the actual state of the channel. The red trail denotes the search result by POMDP, and black trail denotes the RANDOM method. It is obvious that the randomness and divergence of RANDOM far outweigh that of POMDP.