# Evolutionary Overlapping Coalitional Game-Based Link Selection for Distributed Cooperative Localization in Mobile Networks

Authors: Ting Yin; Decai Zou; Rui Zhang; Dongliang Jing; Yongzhao Li; Xiaochun Lu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the increasing application of Internet of Things (IoT), the localization of IoT devices has been widely used. The distributed cooperative localization is expected to be applied in a large-scale dynamic network, such as IoT. It is located through the exchange of information among multiple nodes. For a large amount of battery-based users, the high-computational complexity and heavy communication overhead will lead to huge energy consumption. In this paper, we propose a link selection algorithm based on the evolutionary overlapping coalitional (EOC) game to mitigate the energy consumption for distributed cooperative localization in the dynamic network. The equivalent Fisher information matrix (EFIM) and the Cramér–Rao lower bound (CRLB) are employed to keep location accuracy. Numerical results verify that the distributed cooperative localization based on the EOC game achieves lower energy consumption while keeping localization accuracy in the dynamic networks.


---

## Body

## 1. Introduction

Internet of Things (IoT) is fast increasing key scenes in wireless network [1, 2]. Localization technology plays an important role in Internet of Things (IoT), intelligent transportation system, and indoor environment [3–5]. However, the signal of global navigation satellite systems (GNSS) is usually weakened or unavailable in these scenarios. Therefore, alternative localization schemes with robust and efficient are needed. With the advantages of high localization accuracy and flexible deployment, the wireless network localization is widely applied in the GNSS-challenged scenarios.In wireless network localization, compared with noncooperative localization, cooperative localization no longer has strict requirements on the number of anchors, and it will be applicable to more scenarios [6]. In cooperative localization, the centralized method requires a central processor to estimate the other nodes’ locations; on the contrary, the distributed method demands each node to locate itself. Therefore, the distributed method is more scalable and robust than the centralized method. Specifically, the performance of distributed cooperative localization significantly benefits from the direct internode measurements, including distances and angles, which can be acquired by advanced 5G technologies, such as millimeter Wave communication, massive Multiple Input Multiple Output, and device-to-device (D2D) communication [7]. However, the distributed cooperative localization with massive nodes results in high computational complexity and heavy communication overhead. Especially, for the nodes of IoT, due to energy limitation, it is necessary to design an efficient link selection mechanism in distributed cooperative localization.Previous scholars have studied the link selection algorithm in cooperative localization. In [8], the authors propose a computationally efficient particle filter-based link selection algorithm accounting for neighbors uncertainties. In [9], a Gaussian message passing-based cooperative localization with node selection scheme (NSS) is proposed to mitigate the system overhead in dense wireless networks. However, the relevant work does not consider a targeted algorithm to select agents. In recent years, game theory is a typical approach to the link selection problem in distributed cooperative localization [10–12]. It is employed to analyze complex interactions among players. In [11], the link selection algorithm based on coalitional game is exploited to achieve a tradeoff between localization accuracy and network consumption which includes communication costs and computing resource consumption. Furthermore, opportunistic cooperative localization based on the overlapping coalition formation (OCF) game is able to determine the most informative agents to exchange information [12]. However, the abovementioned link selection algorithms are based on the static game and do not consider the dynamic network topology. More importantly, none of them consider the energy consumption of distributed cooperative localization.The main focus of paper is the energy consumption of distributed cooperative localization. We propose an evolutionary overlapping coalitional (EOC) game for distributed cooperative localization in the large-scale dynamic network, to decrease energy consumption while keeping localization accuracy. Firstly, we design an EOC game in the dynamic location network. Then, we propose a link selection algorithm to solve the limitation of distributed cooperative localization and employ the location algorithm of posterior linearization belief propagation (PLBP) to verify the effectiveness and predominance of our proposed algorithm in static and dynamic networks.


## 2. System Model

We consider a wireless network including two types of nodes: anchors and agents, and they are assumed to be synchronous in wireless networks. The neighboring nodes of thek agent are defined as the nodes within communication range of the k agent, which can cooperatively locate the k agent. We define Nb and Na as the set of anchors and agents, respectively. Each agent determines its own position based on distance measurements among neighbors.In distributed cooperative localization, the process of localization includes the range measurements and position estimations of agents. At the measurements’ step, for estimating its position and keeping synchronization, each agent attempts to find its neighbors and measure distances and angles between anchors and agents. At the position estimation step, agents calculate themselves beliefs at each iteration according to those received from neighbors and broadcast them.We adopt PLBP [12] as the localization algorithm in this paper, which is a message passing algorithm with nonlinear measurement model. The model of range measurement is composed of xi,xj with Gaussian noise:(1)zi,j=Ai,j1xi+Ai,j2xj+bi,j+ei,j+ηi,j,where Ai,j1,Ai,j2,andbi,j are the parameter of measurement and ei,j and ηi,j are zero-mean Gaussian noise with covariance matrix Ωi,j and Ri,j. For simplicity, Algorithm 1 gives the approach for localizing nodes. It is an iterative algorithm implemented in parallel by virtue of exchanging and computing statistical information through all agents in wireless networks. The PLBP algorithm is carried out to estimate agents’ positions at the position estimation step.Algorithm 1: PLBP in cooperative localization.
Input: set the positions of nodes Pi,j0=xi,xjT and the covariance matrix Wi,j0=diagwi,wj, for i,j∈N.Output: the position of all agents.(1)
forIteration=1 to Niter do(2)
ObtainAi,j1,Ai,j2,bi,j,Ωi,j for all i,j∈N(3)
Run statistical linear regression algorithm to replacePi,j and Wi,j(4)
Exchange and Calculate statistic message;(5)
CalculatePi,j and Wi,j(6)
end


### 2.1. Energy Consumption

In cooperative localization, agents need to receive and transfer the neighbors’ information, which can be divided into two types: broadcast information and D2D information. Agents discover neighbors, measure distances, and transmit beliefs by broadcasting. And agents exchange a set of parameters required for locating by D2D communication. We consider a simple energy function in ad hoc mode of IEEE 802.11 wireless network [13], consumed by receiving and sending a packet, which can be expressed as a linear equation:(2)Ek=G×size+b,where G represents the incremental cost, size is the size of packet, and b represents fixed circuit costs. Specifically, the energy consumption of broadcast and D2D communication are given by [13]. Due to the distinction of channel access modes between the broadcast and D2D communication, the value of fixed circuit cost is also different in the reception and transmission of these two modes. For the incremental cost, it is only varied between sending and receiving data.


### 2.2. Error Bounds on Position Estimation

The equivalent Fisher information matrix (EFIM) is effective to reflect the localization accuracy of agents in cooperative localization [14]. In a large-scale network, the information coupling caused by the interaction between neighbors requires additional attention [15]. Similarly, the squared position error bound (SPEB) is utilized to characterize the limit of localization accuracy of massive networks is concerned in [16]. Next, we employ the EFIM to estimate the performance limits of localization.We first introduce the vector of unknown parametersθ=PTθ˜1T⋯θ˜NTT, where P consists of all the agents’ positions and θ˜k is the vector of the multipath parameters associated with the waveforms received at the k agent.The mean squared error (MSE) matrix ofθ^ based on the observation y satisfies the information inequality:(3)Ey,θθ^−θθ^−θT±Jθ−1.Jθ is the Fisher information matrix (FIM) for θ, given by(4)Jθ=Ey,θ−∂2∂θ∂θTlnfy,θ,where fy,θ is the joint probability density function of the observation y and the parameter vector θ. The FIM for θ can be written as Jθ=JθA+JθC+JθP, where JθA represents the localization information from anchors, JθC denotes ranging information between cooperative agents, and JθP represents the agents’ prior knowledge. Since the EFIM retains the necessary information of θ, the relationship between the EFIM and FIM is represented to Jθ−1n×n=Jeθ1−1, where θ=θ1Tθ2TT. For the positions of agents P∈θ, we employ the EFIM characterized by JeP to reflect the agents’ positions. Specifically, if the channel parameters of different waveforms are independent, the EFIM is expressed as without agents’ prior knowledge [17]:(5)Jepk=∑j∈Na,bλkj1−γ2W2∑m=1NtJyϕkj+NtγW+fc2Gkjzkj2Jyϕkj+π2,where λkj is the path-overlap coefficient and 0≤λkj≤1, W represents the transmission bandwidth, γ indicates the baseband-carrier correlation, Nt represents the number of antennas with an array at a node, Gij is the squared array aperture function, and fc is the carrier frequency. The matrix Jy of equation (5) is the ranging direction matrix with angle ϕ, given by(6)Jyϕ≜cos2ϕcosϕsinϕcosϕsinϕsin2ϕ.Note that theJyϕkj term is the information of TOA, and the Jyϕkj+π/2 term corresponds to the information of AOA.The SPEB of thek agent is defined to be(7)SPEBk≜trJeP2×2,k−1,which is a fundamental limit of localization accuracy. According to equation (5), we find that more agent cooperation improves the SPEB performance.


## 2.1. Energy Consumption

In cooperative localization, agents need to receive and transfer the neighbors’ information, which can be divided into two types: broadcast information and D2D information. Agents discover neighbors, measure distances, and transmit beliefs by broadcasting. And agents exchange a set of parameters required for locating by D2D communication. We consider a simple energy function in ad hoc mode of IEEE 802.11 wireless network [13], consumed by receiving and sending a packet, which can be expressed as a linear equation:(2)Ek=G×size+b,where G represents the incremental cost, size is the size of packet, and b represents fixed circuit costs. Specifically, the energy consumption of broadcast and D2D communication are given by [13]. Due to the distinction of channel access modes between the broadcast and D2D communication, the value of fixed circuit cost is also different in the reception and transmission of these two modes. For the incremental cost, it is only varied between sending and receiving data.


## 2.2. Error Bounds on Position Estimation

The equivalent Fisher information matrix (EFIM) is effective to reflect the localization accuracy of agents in cooperative localization [14]. In a large-scale network, the information coupling caused by the interaction between neighbors requires additional attention [15]. Similarly, the squared position error bound (SPEB) is utilized to characterize the limit of localization accuracy of massive networks is concerned in [16]. Next, we employ the EFIM to estimate the performance limits of localization.We first introduce the vector of unknown parametersθ=PTθ˜1T⋯θ˜NTT, where P consists of all the agents’ positions and θ˜k is the vector of the multipath parameters associated with the waveforms received at the k agent.The mean squared error (MSE) matrix ofθ^ based on the observation y satisfies the information inequality:(3)Ey,θθ^−θθ^−θT±Jθ−1.Jθ is the Fisher information matrix (FIM) for θ, given by(4)Jθ=Ey,θ−∂2∂θ∂θTlnfy,θ,where fy,θ is the joint probability density function of the observation y and the parameter vector θ. The FIM for θ can be written as Jθ=JθA+JθC+JθP, where JθA represents the localization information from anchors, JθC denotes ranging information between cooperative agents, and JθP represents the agents’ prior knowledge. Since the EFIM retains the necessary information of θ, the relationship between the EFIM and FIM is represented to Jθ−1n×n=Jeθ1−1, where θ=θ1Tθ2TT. For the positions of agents P∈θ, we employ the EFIM characterized by JeP to reflect the agents’ positions. Specifically, if the channel parameters of different waveforms are independent, the EFIM is expressed as without agents’ prior knowledge [17]:(5)Jepk=∑j∈Na,bλkj1−γ2W2∑m=1NtJyϕkj+NtγW+fc2Gkjzkj2Jyϕkj+π2,where λkj is the path-overlap coefficient and 0≤λkj≤1, W represents the transmission bandwidth, γ indicates the baseband-carrier correlation, Nt represents the number of antennas with an array at a node, Gij is the squared array aperture function, and fc is the carrier frequency. The matrix Jy of equation (5) is the ranging direction matrix with angle ϕ, given by(6)Jyϕ≜cos2ϕcosϕsinϕcosϕsinϕsin2ϕ.Note that theJyϕkj term is the information of TOA, and the Jyϕkj+π/2 term corresponds to the information of AOA.The SPEB of thek agent is defined to be(7)SPEBk≜trJeP2×2,k−1,which is a fundamental limit of localization accuracy. According to equation (5), we find that more agent cooperation improves the SPEB performance.


## 3. Evolutionary Overlapping Coalitional Game-Based Link Selection Mechanism

In this section, we develop a link selection algorithm based on the EOC game model to reduce the energy consumption for distributed cooperative localization in the dynamic network, and we employ the SPEB to keep location accuracy.Most link selection algorithms based on coalition game consider in a static network. While, in the dynamic network, due to changes of the network topology, it needs to repeat the game process to estimate positions. The evolutionary coalitional (EC) game is adopted to capture more behaviors in large-scale wireless networks, such as the joining of new agents and the quitting of former agents [18–20]. In essence, the class of EC game needs less information compared to the standard repeated game approaches. Combined with the advantage of the OCF game, we propose an EOC game including coalitional strategic learning and game stability analysis.


### 3.1. Link Selection Algorithm

In the dynamic network, a multiple number of iteration results in unnecessary communication overhead. Therefore, we design an effective link selection algorithm of distributed cooperation localization in the dynamic network.The link selection algorithm based on the EOC game is described in Algorithm 2. At the first stage, each agent discovers its neighbor nodes and measures ranges and angles with neighbors. Each agent forms coalition with neighboring anchors in step 1, as anchors hold accurate location and synchronization information. At the second stage, agents calculate the fitness of all the possible strategy combinations to format coalitions in steps 5–7. Agents calculate the change probability that includes the quitting of part of agents in coalitions and the joining of new agents in step 9 and exchange their combinations in step 10. At the third stage, when the EOC games achieve stable coalitional structures, agents exchange their pdf among their coalition members to estimate their positions and broadcast their beliefs in step 11 and 12. Note that, at the first stage, without neighboring anchor or only one neighboring agent, this agent would estimate its position until receiving the broadcast information of its neighboring agent. This process is carried out completely in static networks or at the first time in dynamic networks. At the following time in dynamic networks, the second and third stages are repeated only once every second.Algorithm 2: Link selection mechanism-based EOC game.
Input: anchors and agents in wireless networks; the distances among these nodes.Output: the members of coalitions.(1)
Set of agents form coalitions with neighboring anchorsℳa:CS0=ℱ10,…,ℱN0(2)
repeat(3)
for agent = 1: N do(4)
Each anchor broadcast its location;(5)
Each agent calculates its fitnessuk;(6)
Exchange the message with its neighboring agents for forming a coalition;(7)
The neighboring agents calculates their fitnessuj;(8)
if iteration ≥ 2 then(9)
Calculate each agent the change rateρki,j and the evolution of coalition preference q˙k,i(10)
Update the coalitionℱk(11)
When the coalitionℱk is stability, the k agent has an accuracy location;(12)
Thek agent broadcasts its belief(13)
end(14)
end(15)
until Iteration = Niter or all coalitions are stability;


### 3.2. Evolutionary Overlapping Coalitional Game

The proposed EOC game is defined as follows.Definition 1.
An EOC game is defined byGEOC=N,S,u,CS,s, where N is the set of players, S is the strategies of players, u is the fitness of players, CS is the set of coalitions, and s is the state of player.
In a coalitional strategic learning algorithm, agents select a group of strategies and update its preference. It is divided into two stages including the formation stage and the learning stage. In the formation stage, we assume that each agent formats a coalition with the neighboring anchors and agents from a coalition candidate set. In the learning stage, agents calculate their fitness for different strategy combinations and choose the strategy combination of maximize fitness.Definition 2.
An EOC structure at iteration l is defined as a setCSl=ℱ1l,…,ℱNl, where N is the number of players. Each coalition is defined as ℱkl=Na,Nb, where Na∈Sk represents the neighboring agents in the strategy set Sk of players and Nb∈Sk is the neighboring anchors.
We assume distances and angles among agents could be obtained. Since anchors have accurate positions, we employNb to participate in localization of the k agent. Besides, the k agent participates in other coalitions. Figure 1 describes a net-factor graph of the conventional cooperative localization (left) and the EOC-based (right). The blue dots, the white dots, and the edges represent the anchors, agents, and the communication links. In the figure of the right, the irregular dashed circle represents a coalition, in which agents communicate with the members of the same coalition. The player fitness is mainly composed of SPEB of the k agent and communication consumption required for locating, which can be formulated as(8)ukt=α⋅1SPEBk−β⋅Ek,where αandβ are balance factors and SPEBk and Ek are described in Section 3. Each agent calculates its fitness in equation (12) and forms a stable strategy combination.
The average fitnessu¯kt for the k agent is defined as(9)u¯kt=∑i=1Skqk,it∏n∈ℱn,kqn,ituk,it,where qk,it is the probability that the ith agent cooperates and forms the coalition ℱk, where qk,i∈0,1.
The number of agents with cooperating and forming coalitionℱk is nk. If cooperating with the ith agent has a greater fitness than with the jth agent, then the k agent might change its strategy combination. The rate of change ρi,j is(10)ρi,jℱkt=1nku¯k,jt−u¯k,it+,where + represents that ρi,j is a positive value.
To update the preference of agent, we adopt replicator dynamics to model the unplanned joining and quitting coalition. The evolution of coalition preference for thek agent in coalition ℱk is given by(11)q˙k,it=∑ℱj∈Sk/ℱiρj,iℱktqk,jt−qk,it∑ℱj∈Sk/ℱiρi,jℱkt.
Ifq˙k,it≥0 indicates that the ith agent join in the coalition ℱk for achieving a better fitness, when q˙m,it equals 0, this represents a stationary point for the k agent being in coalition ℱk. Oppositely, q˙k,it<0 means that the ith agent in coalition ℱk is no benefit.
Additionally, the coalitional strategic learning algorithm permits agents updating their strategy combinations for the next iteration in the EOC game as follows:(12)qk,it+1=qk,it+q˙k,it.
Evolutionary stable coalitional structure (ESCS) is significant notion to express the stability and robustness of the game [21]. A stable coalition implies that, in a coalition, no agent can improve its fitness by quitting its current coalition and joining in another one. An ESCS is resilient by small perturbation of strategies, such as the joining of new agents, the message congestion of agents, and agent loss of battery. The ESCS is defined as follows.Figure 1
Illustration of evolutionary overlapping coalition formation.Definition 3.
The coalition setℱk′is an ESCS if there exists0<ρ≤ρk∗for eachk∈Nsuch that(13)u¯kℱk′,1−ρℱ−k′+ρℱ−k∗≥u¯kℱk∗,1−ρℱ−k′+ρℱ−k∗,where ℱk′ and ℱk∗ are different strategy combinations respectively. When ρ portion of agents from the coalition ℱ−k′ quits and ρ portion of agents from the coalition ℱ−k∗ joins in the coalition ℱ−k′, the coalition ℱk′ always has larger fitness.


### 3.3. Complexity and Energy Consumption Analysis

For the proposed EOC game-based link selection algorithm given in Algorithm 2, the complexity of each agent is given asOQ⋅nk, where Q represents the message representation complexity prelink and nk is the number of agents’ neighbors selected. The message representation complexities including the discretized, sample-based, and parametric message representation are given in [22]. Similar with the complexity of other link selection methods, nk decreases in the EOC game method. For the upper bound of complexity, nk of each agent is equal to the number of all neighbors. In this situation, the complexity of the proposed algorithm is also the complexity of distributed cooperative localization. Therefore, the computational complexity of the proposed method is low compared with the conventional distributed cooperative localization.Since the agent’s energy consumption is relative to the number of receiving and sending packets, the proposed EOC game-based link selection algorithm selects the most informative links to exchange location messages. Although the equilibrium of the EOC game brings some additional communication overhead, it is far less than the message exchanges of localization for distributed cooperative localization. Significantly, the message passing algorithm based on link selection acquires more benefit at energy consumption when the number of nodes is large. Considering that the equilibrium of the evolutionary game is gradual, it does not need to spend more iterations to find the most stable coalitional structure compared to a static game. The proposed link selection algorithm based on the EOC game has lighter energy consumption than most cooperative localization schemes.


## 3.1. Link Selection Algorithm

In the dynamic network, a multiple number of iteration results in unnecessary communication overhead. Therefore, we design an effective link selection algorithm of distributed cooperation localization in the dynamic network.The link selection algorithm based on the EOC game is described in Algorithm 2. At the first stage, each agent discovers its neighbor nodes and measures ranges and angles with neighbors. Each agent forms coalition with neighboring anchors in step 1, as anchors hold accurate location and synchronization information. At the second stage, agents calculate the fitness of all the possible strategy combinations to format coalitions in steps 5–7. Agents calculate the change probability that includes the quitting of part of agents in coalitions and the joining of new agents in step 9 and exchange their combinations in step 10. At the third stage, when the EOC games achieve stable coalitional structures, agents exchange their pdf among their coalition members to estimate their positions and broadcast their beliefs in step 11 and 12. Note that, at the first stage, without neighboring anchor or only one neighboring agent, this agent would estimate its position until receiving the broadcast information of its neighboring agent. This process is carried out completely in static networks or at the first time in dynamic networks. At the following time in dynamic networks, the second and third stages are repeated only once every second.Algorithm 2: Link selection mechanism-based EOC game.
Input: anchors and agents in wireless networks; the distances among these nodes.Output: the members of coalitions.(1)
Set of agents form coalitions with neighboring anchorsℳa:CS0=ℱ10,…,ℱN0(2)
repeat(3)
for agent = 1: N do(4)
Each anchor broadcast its location;(5)
Each agent calculates its fitnessuk;(6)
Exchange the message with its neighboring agents for forming a coalition;(7)
The neighboring agents calculates their fitnessuj;(8)
if iteration ≥ 2 then(9)
Calculate each agent the change rateρki,j and the evolution of coalition preference q˙k,i(10)
Update the coalitionℱk(11)
When the coalitionℱk is stability, the k agent has an accuracy location;(12)
Thek agent broadcasts its belief(13)
end(14)
end(15)
until Iteration = Niter or all coalitions are stability;


## 3.2. Evolutionary Overlapping Coalitional Game

The proposed EOC game is defined as follows.Definition 1.
An EOC game is defined byGEOC=N,S,u,CS,s, where N is the set of players, S is the strategies of players, u is the fitness of players, CS is the set of coalitions, and s is the state of player.
In a coalitional strategic learning algorithm, agents select a group of strategies and update its preference. It is divided into two stages including the formation stage and the learning stage. In the formation stage, we assume that each agent formats a coalition with the neighboring anchors and agents from a coalition candidate set. In the learning stage, agents calculate their fitness for different strategy combinations and choose the strategy combination of maximize fitness.Definition 2.
An EOC structure at iteration l is defined as a setCSl=ℱ1l,…,ℱNl, where N is the number of players. Each coalition is defined as ℱkl=Na,Nb, where Na∈Sk represents the neighboring agents in the strategy set Sk of players and Nb∈Sk is the neighboring anchors.
We assume distances and angles among agents could be obtained. Since anchors have accurate positions, we employNb to participate in localization of the k agent. Besides, the k agent participates in other coalitions. Figure 1 describes a net-factor graph of the conventional cooperative localization (left) and the EOC-based (right). The blue dots, the white dots, and the edges represent the anchors, agents, and the communication links. In the figure of the right, the irregular dashed circle represents a coalition, in which agents communicate with the members of the same coalition. The player fitness is mainly composed of SPEB of the k agent and communication consumption required for locating, which can be formulated as(8)ukt=α⋅1SPEBk−β⋅Ek,where αandβ are balance factors and SPEBk and Ek are described in Section 3. Each agent calculates its fitness in equation (12) and forms a stable strategy combination.
The average fitnessu¯kt for the k agent is defined as(9)u¯kt=∑i=1Skqk,it∏n∈ℱn,kqn,ituk,it,where qk,it is the probability that the ith agent cooperates and forms the coalition ℱk, where qk,i∈0,1.
The number of agents with cooperating and forming coalitionℱk is nk. If cooperating with the ith agent has a greater fitness than with the jth agent, then the k agent might change its strategy combination. The rate of change ρi,j is(10)ρi,jℱkt=1nku¯k,jt−u¯k,it+,where + represents that ρi,j is a positive value.
To update the preference of agent, we adopt replicator dynamics to model the unplanned joining and quitting coalition. The evolution of coalition preference for thek agent in coalition ℱk is given by(11)q˙k,it=∑ℱj∈Sk/ℱiρj,iℱktqk,jt−qk,it∑ℱj∈Sk/ℱiρi,jℱkt.
Ifq˙k,it≥0 indicates that the ith agent join in the coalition ℱk for achieving a better fitness, when q˙m,it equals 0, this represents a stationary point for the k agent being in coalition ℱk. Oppositely, q˙k,it<0 means that the ith agent in coalition ℱk is no benefit.
Additionally, the coalitional strategic learning algorithm permits agents updating their strategy combinations for the next iteration in the EOC game as follows:(12)qk,it+1=qk,it+q˙k,it.
Evolutionary stable coalitional structure (ESCS) is significant notion to express the stability and robustness of the game [21]. A stable coalition implies that, in a coalition, no agent can improve its fitness by quitting its current coalition and joining in another one. An ESCS is resilient by small perturbation of strategies, such as the joining of new agents, the message congestion of agents, and agent loss of battery. The ESCS is defined as follows.Figure 1
Illustration of evolutionary overlapping coalition formation.Definition 3.
The coalition setℱk′is an ESCS if there exists0<ρ≤ρk∗for eachk∈Nsuch that(13)u¯kℱk′,1−ρℱ−k′+ρℱ−k∗≥u¯kℱk∗,1−ρℱ−k′+ρℱ−k∗,where ℱk′ and ℱk∗ are different strategy combinations respectively. When ρ portion of agents from the coalition ℱ−k′ quits and ρ portion of agents from the coalition ℱ−k∗ joins in the coalition ℱ−k′, the coalition ℱk′ always has larger fitness.


## 3.3. Complexity and Energy Consumption Analysis

For the proposed EOC game-based link selection algorithm given in Algorithm 2, the complexity of each agent is given asOQ⋅nk, where Q represents the message representation complexity prelink and nk is the number of agents’ neighbors selected. The message representation complexities including the discretized, sample-based, and parametric message representation are given in [22]. Similar with the complexity of other link selection methods, nk decreases in the EOC game method. For the upper bound of complexity, nk of each agent is equal to the number of all neighbors. In this situation, the complexity of the proposed algorithm is also the complexity of distributed cooperative localization. Therefore, the computational complexity of the proposed method is low compared with the conventional distributed cooperative localization.Since the agent’s energy consumption is relative to the number of receiving and sending packets, the proposed EOC game-based link selection algorithm selects the most informative links to exchange location messages. Although the equilibrium of the EOC game brings some additional communication overhead, it is far less than the message exchanges of localization for distributed cooperative localization. Significantly, the message passing algorithm based on link selection acquires more benefit at energy consumption when the number of nodes is large. Considering that the equilibrium of the evolutionary game is gradual, it does not need to spend more iterations to find the most stable coalitional structure compared to a static game. The proposed link selection algorithm based on the EOC game has lighter energy consumption than most cooperative localization schemes.


## 4. Simulation Results

We evaluate the simulated scenario, which is a reference for the existing works [6, 23], with 13 anchors and massive agents. The communication range is set to 20 m. For the anchor, the position is drawn from a Gaussian distribution whose mean is the actual position and covariance is 0.1 m. The covariance of the agent is 10 m. The error of range measurements is 1 m. In the static network, the numbers of agents are 50, 100, and 200, which represent the sparse, normal, and dense scenes, respectively. In the dynamic network, the number of agents is 100 and the speed of agents is randomly selected from 0 to 1 m/s in Figure 2. The energy consumption per second to send and receive information in broadcast is 274.1×10−6J and 50.26×10−6J. Likewise, the D2D are 431.48×10−6J and 316.12×10−6J under 2.4 GHz [13]. The balance factor β is SPEBt−1/Et−1 in order to make the SPEB and the energy equal in value, and α is 1. The localization algorithm has been implemented using the PLBP algorithm with a weight 1/3. We evaluate the algorithms using Monte Carlo simulation with 500 runs of random measurements.Figure 2
The simulated scenario in dynamic networks. The red squares represent anchors and the lines represent the agents’ trajectories.Initially, each agent forms an independent coalition. The neighbor agents in a coalition are equal probability to join in this coalition. The proposed EOC method are compared with the link selection scheme (NSS) in [9], the OCF-based method [12], and PLBP (no link selection) [23].The root mean square error (RMSE) value of the proposed EOC game method, OCF game, and PLBP for static networks considered in the comparison is summarized in Table1. The proposed EOC game method, respectively, estimated with RMSE of 0.6324 m, 0.5636 m, and 0.4677 m under 50, 100, and 200 agents’ conditions. It is evident from the results that the proposed model performed well when compared with the OCF game method and the NSS. The localization error of PLBP with connecting all neighboring nodes is the smallest on account of localization accuracy which are subject to more connections. In addition to that, the RMSE of localization error in the dynamic network is shown in Figure 3. Similarly, in dynamic networks, the performance of the EOC game is also suboptimal. Specifically, the localization error converges within the first few seconds. However, as the number of neighbors is less than 3 due to node movement, the localization error ascends. It is clear from Figure 3 that performance degradation of the proposed is minor, i.e., the difference from the PLBP can be neglected as suggested in [12].Table 1
RMSE of localization error in the static network (Monte Carlo = 500).
AgentsEOCOCFNSSPLBP500.6324 m0.6713 m0.924 60.4365 m1000.5636 m0.5822 m0.822 10.3147 m2000.4677 m0.5325 m0.475 40.3216 mFigure 3
RMSE of localization error in dynamic networks.Figure4 depicts the mean energy consumption of agents within 200 s. The energy consumption of agents relies on information exchange among neighbors. Compared with the PLBP algorithm communicated with all neighbors, other methods have lighter energy consumption. The variation of network topology makes the OCF game method reform coalitions every time. Although the NSS method does not require additional communication overhead to form a coalition, the number of connected nodes is still relatively large, whereas the proposed method only consumes a small amount of energy to maintain coalitions and locate. Therefore, distributed cooperative localization based on the EOC game consumes the least energy, when compared with the OCF game, NSS, and PLBP.Figure 4
Mean energy consumption of agents.


## 5. Conclusion

In this paper, we have formulated a link selection algorithm to reduce energy consumption and proposed an EOC game to consider the dynamic network topology in distributed cooperative localization, where agents formed coalitions based on SPEB and energy consumption, in a fully distributed and autonomous manner. Simulation results demonstrate that the proposed EOC game algorithm reduces agents’ energy consumption and keeps network localization accuracy.



---

*Source: 6588197-2022-02-16.xml*