# Cross-Layer Optimized Energy-Balanced Topology Control Algorithm for WSNs

Authors: Yongwen Du; Zhangmin Wang; Junhui Gong; Ning Xu; Xiaohui Hu
Journal: Journal of Sensors
 (2019)

---

## Abstract

Because of the complexity of the environment and the limited resources of nodes, there will be an imbalanced energy consumption and a short life among nodes in the wireless sensor network. In this paper, by introducing the concept of game theory and supermodel game theory, we solve the challenge of a wireless sensor network topology control method based on cross-layer information design. The cross-layer information such as node degree, network connectivity, and MAC layer interference is integrated into the design of utility function to establish a new topological game model. Then, based on this topology control model, we propose a cross-layer optimized energy-balanced topology control algorithm (COETC). Compared with other algorithms, our COETC algorithm not only guarantees the network connectivity and robustness while reducing the required node transmitting power but also achieves good energy balance and high energy efficiency. Ultimately, our method effectively prolongs network lifetime and improves network performance.


---

## Body

## 1. Introduction

A wireless sensor network (WSN) is a multihop self-organizing network intended for data collection. WSNs are widely used in IoT systems because of their low cost, small size, and rapid deployment characteristics. However, due to the complexity of network working environments and node resource limitations, it is difficult to supplement the energy of WSNs after their energy is exhausted [1]. Therefore, energy efficiency and energy balance have always been the main factors that restrict WSN development. Topology control technology is a key aspect of the WSN field, which is mainly applied to the link and network layers. It is also important to improve the efficiency of routing and MAC protocols, reduce communication interference, and make network energy consumption balanced. Therefore, effectively controlling and optimizing the network topology is a key challenge in WSNs [2].Topology control technology provides an optimized network topology, which affects network routing and MAC protocols. The network layer, MAC layer, and physical layer in WSNs can all affect the result of topology control, and they also have a mutually restricted relationship. The transmitting power and transmission rate of the physical layer can affect access control in the MAC layer and routing decisions in the network layer. The MAC layer channel allocation limits the network bandwidth and affects routing decisions in the network layer, which is responsible for both routing decisions and packet transmission. Therefore, the design of an effective topology control method needs to consider not only the energy consumption factors but also the cross-protocol layer for a variety of performance parameters.When the sensor nodes perform data forwarding, they will exhibit selfish behavior due to energy saving considerations, and competition will occur between nodes [3]. On this basis, game theory was introduced into the study of WSN topology control. Game theory provides a powerful tool [4] for describing the phenomena of competition and individual coping strategies between intelligent rational decision-makers, and it has been used in systems involving action and payoff. Topkis proposed a supermodular game in 1978 [5], which used a game theory based on lattice theory. The model has the following properties [6]: (1) It considers the complementarity of the strategies between the parties in the game, while making the existence of the Nash equilibrium and related static results clearly visible. (2) It makes up for the shortcomings of the traditional game theory, which makes game theory no longer need convexity and differentiability of objective function and expands the application scope of noncooperative game theory.In order to accurately describe the topological game behavior between nodes, this paper introduces the supermodel game theory into the WSN topology control technology and integrates multiple performance parameters across the protocol layer into the utility function of the model. First, this paper establishes a new topology game model. Secondly, COETC is proposed, which is a multilayer optimized topology game algorithm for wireless sensor networks. Finally, experiments show that the network topology constructed by the COETC algorithm can accurately describe the competition and contradictory behavior between nodes. Under the premise of ensuring network connectivity and robustness, COETC solves the problem of energy imbalance between nodes, which improves energy efficiency and effectively prolongs network lifetime.


## 2. Related Work

So far, many topology control algorithms have been proposed for WSN, which are mainly divided into layering, power control, and game-type topology control algorithms. For example, in [7], a low-power multilevel hierarchical WSN topology control algorithm is designed. The algorithm extends the network level and improves WSN maintainability using a combination of static and dynamic addresses. In [8], a low-energy adaptive clustering hierarchy (LEACH) topology control method was established for WSNs using time slots, in which a cluster-head-selecting approach reduced cluster size differences and the responsibility mechanism of the active node leads to a more balanced energy consumption in the cluster. In [9], Kubisch et al. implemented dynamic power control to set the upper and lower limits of the node degree, thus resulting in a network topology with lower total energy consumption. The power control algorithm proposed in [10] uses a Borel Cayley graph to construct a network topology with a short average link and low energy consumption. However, it does not consider the robustness of the network topology and the residual energy of nodes, both of which affect network operation.Traditional game theory methods are used in current research. Komali et al. [11, 12] formulated energy-efficient topology control as a potential noncooperative game. This approach guaranteed the existence of at least one Nash’s equilibrium (NE) and proposed a distributed noncooperative game topology control algorithm based on game theory. The authors of [13] designed a topology control algorithm based on a link power consumption game to run the minimum MLPT algorithm for the maximum power of the node. To also consider network lifetime, researchers have proposed two game-based topology control algorithms: the virtual game-based energy-balanced (VGEB) algorithm [14] and the energy welfare topology control (EWTC) algorithm [15], both of which were developed to improve network lifetime via energy-balanced network topologies. In [16], the adaptive cooperative topological control algorithm (CTCA) based on game theory considered the smallest potential lifetime and degree as primary and secondary utility functions, respectively. In [17], a distributed energy-balanced topology control algorithm (DEBA) based on an ordinal potential game was proposed by designing a payoff function that considered both network connectivity and the energy balance of nodes. In [18], Wang et al. proposed ATGG, an adaptive topology game algorithm for energy balance in a wireless sensor network. According to the average life of nodes, nodes adjust their own power to help nodes with the shortest life to reduce transmitting power, which can prolong the entire network life. In [19], a novel topological control game algorithm, TCAMLPM, was proposed based on Markov’s life prediction model, a distributed topology control game algorithm for WSN which ensures the algorithm to converge to the Nash equilibrium by making use of the best response strategy. In [20], by comprehensively considering the benefits between node coverage and residual energy, CTCL, a node scheduling algorithm, is proposed, which introduces a noncooperative game theory. Although some of the abovementioned algorithms based on game theory achieve network topology control and improve network performance, they cannot guarantee the connectivity and robustness of the network. Additionally, the algorithms do not fully consider the remaining energy, energy balance, and energy efficiency of the nodes. Thus, the existing algorithms based on game theory can achieve network topology control to some extent and improve network performance, but they cannot effectively guarantee the network’s connectivity and robustness. Simultaneously, due to the complexity of the WSN deployment environment, the factors that affect network operation make it more difficult to quantify the node revenue; therefore, the existing topology control algorithms based on game theory cannot accurately describe the phenomena of balancing the competition between nodes with network energy consumption. The above method requires that the objective function is convex and differentiable, which affects the result of the algorithm.


## 3. Supermodular Game Theory

A supermodular game is based on a rich mathematical foundation of lattice theory and comparative statics. The strategy space of every player is a partially ordered set, and the utility of playing higher strategy increases when the opponents also play higher strategy [21]. Suppose fx is a real valued function in lattice I, I is a partially ordered set, and I′ is a subset of I. If x≺x′, then x′ is the upper bound of I′, where x∈I and x′∈I′. If x≻x′, then x′ is the lower bound of I′. If the set of the upper (lower) bounds of I′ has a least (greatest) element, then this least upper bound (greatest lower bound) of I′ is the supremum of I′.The strategy gameΓ consists of N players, the possible strategy S of the players, and consequences u of applying strategy. The following definition is given for the strategy game:
(1)Γ=N,S,ui,where (1) N=1,2,3,⋯,n represents the player set, and n is the number of players in the game; (2) S represents the policy space, and S is the Cartesian product of the set of policies Sii∈N, where Si=si1,si2,⋯,sik represents an optional set of policies for node i, usually abbreviated as Si=s1,s2,⋯,sk. In general, we use s=si,s−i∈S to describe a strategy combination, where si represents the strategy choice of node i and s−i represents the strategy choices of nodes other than node i. Finally, (3) u represents a utility function u=u1,u2,⋯,un, where ui denotes the maximum utility function that node i can achieve in the policy combination si,s−i.A strategy gameΓ=N,S,ui is a supermodular game if the set S of feasible joint strategies is a sublattice of Rn. The utility function of the supermodular game belongs to the supermodular function, whose definition is as follows: for set I, ∀x,y∈I,∃x∨y,x∧y∈I, I can be called a lattice, where x∨y represents the upper bound [5] of set I and x∧y represents the lower bound [5] of set I. For an objective function f defined on lattice I, ∀x,y∈I,fx−fx∧y≤fx∨y−fy, it can be understood that the increment of the function f realized from the point x∧y change to the point x (or y) is smaller than the change from the point y (or x). For the corresponding increment of point x∨y, then f can be the supermodular function on I.Definition 1.
In a strategy gameΓ=N,S,ui, if the strategy si∗ of any game player i is the best strategy response to the strategy combination s−i∗ of the remaining game participants, then there must be a uis1∗,⋯,si∗,⋯sn∗≥uis1∗,⋯,sij∗,⋯sn∗, where sij means that ∀sij∈Si, and the jth strategy for the game player i is valid. Then, s1∗,·s,sn∗ is called the “Nash equilibrium (NE)” [22] of the game.Theorem 1.
If the game is supermodular, there exists the largest and the smallest Nash equilibrium in pure strategies [23].Lemma 1.
The condition that the functionf on the set Rn is a supermodular function is that f must have a difference on Rn [23].Lemma 2.
IfI=x¯,x¯ is the interval on set Rn and the existence function f is quadratic and continuously different in an open interval containing I, then the necessary and sufficient condition for f to become a supermodular function at I is ∀i≠j,∂2fx,y/∂xi∂yj≥0, where vector x=x1,⋯,xn and y=y1,⋯,yn in the n dimension Euclid spaces [23].Definition 2.
For the strategy gameΓ=N,S,ui, in the case where the strategy space Si=s1,s2,⋯,sk of any participant i is a real interval and the utility function uisi,s−iis twice continuously differentiable on Si, when ∀j≠k∈N,∃∂2ui/∂sj∂sk≥0, the strategy game is a supermodular game [24].Theorem 2.
A supermodular game with a limited space for any participant strategy will converge to a pure strategy Nash equilibrium point when a better response strategy is adopted [24].


## 4. System Model

In this section, we first construct a topology control game model. Then, we prove that the game model belongs to the supermodular game and has a pure strategy Nash equilibrium.


### 4.1. Topological Game Model

This paper uses the strategy game to realize the cooperative optimization of various WSN performance goals. To maximize the utility function, the participants in this game model adjust their power selfishly, which is typical behavior in a noncooperative topology control game. The three elements of the game model are as follows:(1)
Participant set: all the nodes in the network can be regarded as game participants, specifically expressed asN=1,2,3,⋯,n, where n is the total number of nodes in the network
(2)
Strategy space: the optional power setPi=p1,p2,⋯,pl of the node can be regarded as the game strategy space, where pi indicates the current power selection of node i and l represents the number of candidate powers of node i
(3)
Utility function: the environments in which WSNs are used are complex, and it is difficult to quantify the node revenue. Therefore, the design of node utility functions needs to consider the influence of multiple factors. To accurately describe the competition phenomenon between nodes and the energy balance situation, for nodei, this paper comprehensively considers the utility function design problem from the following aspects:
(a)
Network connectivity at the link layer: for network topology, maintaining connectivity is a basic network aspect that must be guaranteed. Therefore, when constructing the utility function, it is necessary to consider network connectivity. The connectivity factor is defined asfipi,p−i, fipi,p−i=1 indicates that the network is in the connected state, and fipi,p−i=0 indicates that the network is in a unconnected state. ∀pi,qi∈Pi, when transmitting power pi>qi,fipi,p−i≥fiqi,p−i. Obviously, fipi,p−i is monotonically nondecreasing
(b)
Node degree: by optimizing the node degree, the total energy consumption of the network can be reduced and the overall performance of the network can be improved. Therefore, the node degreempi of the node i in the power transmission pi state is introduced into the design of utility function, and mpi represents the total number of one-hop neighbor nodes of node i.
(c)
Degree of interference at the MAC layer: interference between nodes also affect network performance. The interference between nodes will increase with the growth of power, and at the same time, the probability of packet retransmission will also increase. Similarly, network operating efficiency will decrease with the increase of the network energy consumption. The definition of the degree of interference at the MAC layer ismpipi/∑k≠ipk, where node k is the one-hop neighbor of node i, and mpi represents the total number of one-hop neighbor nodes of node i in the power transmission pi.
(d)
Residual energy balance: when the residual energy distribution of the network nodes is uneven, some nodes will experience premature death, which will affect network operation. Therefore, the residual energy needs to be considered in the design of the utility function. The residual energy equalization factor of the defined node isEri/E0i+1/mpi∑k≠iErk/E0k, where Eri and E0i represent the residual energy and the initial energy of node i, and mpi represents the total number of one-hop neighbor nodes of node i in the power transmission pi, respectively.In summary, for∀i∈N, considering factors such as network node degree, node residual energy, and network interference, the utility function is designed as follows:
(2)uipi,p−i=fipi,p−iαpimax−mpipi+EriE0i+βmpi∑k≠iErkE0k−mpipi∑k≠ipk,where α and β are weighting factors to ensure that the revenue when the network is connected is greater than the income in the unconnected case, and both are positive numbers, which in the simulation analysis part of this paper, we will determine how to set weighting factors α and β. Although the node selects a larger transmit power, it can increase the node degree to enhance the network connectivity. However, a larger transmit power will inevitably generate a stronger network interference, increase network energy consumption, and reduce network operating efficiency. These factors exist between contradictions and constraints.


### 4.2. Model Analysis

Theorem 3.
The topological game model using equation (2) as the utility function is a supermodular game and must have a Nash equilibrium solution.Proof 1.
The policy setPi of node i is a subset of the real set R.
(1)
If the network is in the unconnected state,fipi,p−i=0, equation (2) can be simplified to
(3)uipi,p−i=−mpipi∑k≠ipk
For equation (3), ∀j≠i∈N,pi,pj∈P,∃maxpi,pj∈P and ∃minpi,pj∈P, the first-order partial derivative is obtained for power:
(4)∂ui∂pipi,p−i=−1∑k≠ipk∂mpi∂pipi+mpi,where k is one-hop neighbor of node i. The second-order partial derivative is obtained:
(a)
For nodej is not a neighbor of node i
(5)∂2ui∂pi∂pjpi,p−i=∂−1/∑k≠i,k≠jpk∂mpi/∂pipi+mpi∂pj=0
(b)
For nodej is a neighbor of node i
(6)∂2ui∂pi∂pjpi,p−i=∂mpi/∂pipi+mpi∑k≠ipk2
In the network environment,mpi is positively correlated with pi, ∂mpi/∂pi≥0. Therefore, in equation (6), ∂2ui/∂pi∂pjpi,p−i≥0.
(2)
And if the network is in the connected state,fipi,p−i=1, equation (2) can be simplified to
(7)uipi,p−i=αpimax−mpipi+EriE0i+βmpi∑k≠iErkE0k−mpipi∑k≠ipk
For equation (7), ∀j≠i∈N,pi,pj∈P,∃maxpi,pj∈P and ∃minpi,pj∈P, the first-order partial derivative is obtained for power:
(8)∂ui∂pipi,p−i=−∂mpi∂pipi+mpi+β∑k≠iErkE0k−1mpi2∂mpi∂pi−1∑k≠ipk∂mpi∂pipi+mpi,where k is the one-hop neighbor of node i. The second-order partial derivative is obtained:
(a)
For nodej is not a neighbor of node i
(9)∂2ui∂pi∂pjpi,p−i=∂−∂mpi/∂pipi+mpi+β∑k≠i,k≠jErk/E0k−1/mpi2∂mpi/∂pi−1/∑k≠i,k≠jpk∂mpi/∂pipi+mpi∂pj=0
(b)
For nodej is a neighbor of node i
(10)∂2ui∂pi∂pj=∂−1/∑k≠ipk∂mpi/∂pipi+mpi∂pj=∂mpi/∂pipi+mpi∑k≠ipk2
Obtained by Equation (6), in Equation (10), ∂2ui/∂pi∂pjpi,p−i≥0.
In summary,∂2ui/∂pi∂pjpi,p−i≥0, which indicates that the utility function of the topological game model has incremental differences. Thus, according to Definition 2, the topological game model is a supermodular game, and there is at least one pure strategy Nash equilibrium.


## 4.1. Topological Game Model

This paper uses the strategy game to realize the cooperative optimization of various WSN performance goals. To maximize the utility function, the participants in this game model adjust their power selfishly, which is typical behavior in a noncooperative topology control game. The three elements of the game model are as follows:(1)
Participant set: all the nodes in the network can be regarded as game participants, specifically expressed asN=1,2,3,⋯,n, where n is the total number of nodes in the network
(2)
Strategy space: the optional power setPi=p1,p2,⋯,pl of the node can be regarded as the game strategy space, where pi indicates the current power selection of node i and l represents the number of candidate powers of node i
(3)
Utility function: the environments in which WSNs are used are complex, and it is difficult to quantify the node revenue. Therefore, the design of node utility functions needs to consider the influence of multiple factors. To accurately describe the competition phenomenon between nodes and the energy balance situation, for nodei, this paper comprehensively considers the utility function design problem from the following aspects:
(a)
Network connectivity at the link layer: for network topology, maintaining connectivity is a basic network aspect that must be guaranteed. Therefore, when constructing the utility function, it is necessary to consider network connectivity. The connectivity factor is defined asfipi,p−i, fipi,p−i=1 indicates that the network is in the connected state, and fipi,p−i=0 indicates that the network is in a unconnected state. ∀pi,qi∈Pi, when transmitting power pi>qi,fipi,p−i≥fiqi,p−i. Obviously, fipi,p−i is monotonically nondecreasing
(b)
Node degree: by optimizing the node degree, the total energy consumption of the network can be reduced and the overall performance of the network can be improved. Therefore, the node degreempi of the node i in the power transmission pi state is introduced into the design of utility function, and mpi represents the total number of one-hop neighbor nodes of node i.
(c)
Degree of interference at the MAC layer: interference between nodes also affect network performance. The interference between nodes will increase with the growth of power, and at the same time, the probability of packet retransmission will also increase. Similarly, network operating efficiency will decrease with the increase of the network energy consumption. The definition of the degree of interference at the MAC layer ismpipi/∑k≠ipk, where node k is the one-hop neighbor of node i, and mpi represents the total number of one-hop neighbor nodes of node i in the power transmission pi.
(d)
Residual energy balance: when the residual energy distribution of the network nodes is uneven, some nodes will experience premature death, which will affect network operation. Therefore, the residual energy needs to be considered in the design of the utility function. The residual energy equalization factor of the defined node isEri/E0i+1/mpi∑k≠iErk/E0k, where Eri and E0i represent the residual energy and the initial energy of node i, and mpi represents the total number of one-hop neighbor nodes of node i in the power transmission pi, respectively.In summary, for∀i∈N, considering factors such as network node degree, node residual energy, and network interference, the utility function is designed as follows:
(2)uipi,p−i=fipi,p−iαpimax−mpipi+EriE0i+βmpi∑k≠iErkE0k−mpipi∑k≠ipk,where α and β are weighting factors to ensure that the revenue when the network is connected is greater than the income in the unconnected case, and both are positive numbers, which in the simulation analysis part of this paper, we will determine how to set weighting factors α and β. Although the node selects a larger transmit power, it can increase the node degree to enhance the network connectivity. However, a larger transmit power will inevitably generate a stronger network interference, increase network energy consumption, and reduce network operating efficiency. These factors exist between contradictions and constraints.


## 4.2. Model Analysis

Theorem 3.
The topological game model using equation (2) as the utility function is a supermodular game and must have a Nash equilibrium solution.Proof 1.
The policy setPi of node i is a subset of the real set R.
(1)
If the network is in the unconnected state,fipi,p−i=0, equation (2) can be simplified to
(3)uipi,p−i=−mpipi∑k≠ipk
For equation (3), ∀j≠i∈N,pi,pj∈P,∃maxpi,pj∈P and ∃minpi,pj∈P, the first-order partial derivative is obtained for power:
(4)∂ui∂pipi,p−i=−1∑k≠ipk∂mpi∂pipi+mpi,where k is one-hop neighbor of node i. The second-order partial derivative is obtained:
(a)
For nodej is not a neighbor of node i
(5)∂2ui∂pi∂pjpi,p−i=∂−1/∑k≠i,k≠jpk∂mpi/∂pipi+mpi∂pj=0
(b)
For nodej is a neighbor of node i
(6)∂2ui∂pi∂pjpi,p−i=∂mpi/∂pipi+mpi∑k≠ipk2
In the network environment,mpi is positively correlated with pi, ∂mpi/∂pi≥0. Therefore, in equation (6), ∂2ui/∂pi∂pjpi,p−i≥0.
(2)
And if the network is in the connected state,fipi,p−i=1, equation (2) can be simplified to
(7)uipi,p−i=αpimax−mpipi+EriE0i+βmpi∑k≠iErkE0k−mpipi∑k≠ipk
For equation (7), ∀j≠i∈N,pi,pj∈P,∃maxpi,pj∈P and ∃minpi,pj∈P, the first-order partial derivative is obtained for power:
(8)∂ui∂pipi,p−i=−∂mpi∂pipi+mpi+β∑k≠iErkE0k−1mpi2∂mpi∂pi−1∑k≠ipk∂mpi∂pipi+mpi,where k is the one-hop neighbor of node i. The second-order partial derivative is obtained:
(a)
For nodej is not a neighbor of node i
(9)∂2ui∂pi∂pjpi,p−i=∂−∂mpi/∂pipi+mpi+β∑k≠i,k≠jErk/E0k−1/mpi2∂mpi/∂pi−1/∑k≠i,k≠jpk∂mpi/∂pipi+mpi∂pj=0
(b)
For nodej is a neighbor of node i
(10)∂2ui∂pi∂pj=∂−1/∑k≠ipk∂mpi/∂pipi+mpi∂pj=∂mpi/∂pipi+mpi∑k≠ipk2
Obtained by Equation (6), in Equation (10), ∂2ui/∂pi∂pjpi,p−i≥0.
In summary,∂2ui/∂pi∂pjpi,p−i≥0, which indicates that the utility function of the topological game model has incremental differences. Thus, according to Definition 2, the topological game model is a supermodular game, and there is at least one pure strategy Nash equilibrium.


## 5. Cross-Layer Optimized Energy-Balanced Topology Control Algorithm

In this section, we design the cross-layer optimized energy-balanced topology control algorithm (COETC) based on a supermodular game using the topological game model constructed in Section4.1.The node must meet certain preconditions when running the algorithm: (1) the network node ID must be unique; (2) the node cannot be moved after deployment; (3) the transmit power of all nodes is continuously adjustable and the maximum transmit power of the nodes can vary; (4) the network layer can obtain global information concerning the network; and (5) when all nodes have the maximum transmit power characteristics, the network topology graphGmax formed by default is connected (this must support bidirectional link communications).The operation of the COETC algorithm is divided into four phases: a neighbor discovery phase, a topology establishment phase, a power adjustment phase, and a topology maintenance phase.


### 5.1. Neighbor Discovery Phase

In this phase, each node needs to discover its local neighbor nodes and build a list of neighbor information through information interchanges. Each source nodei initializes its own transmit power to the maximum transmit power pimax, by broadcasting the “Hello” message and receiving ACK messages returned by the target nodes j. The source node obtains the neighbor node information by parsing the ACK message and storing the parsed information in a neighbor table Mmaxi, generating its own policy set through the information exchange nodes.The “Hello” message includes the source node’s ID, its current transmit powerpimax, and its remaining energy Eri. The ACK message includes the target node’s ID, its minimum power pijmin, and its remaining energy Erj that can ensure normal communication with the source node, thus ensuring normal communications among network nodes. The minimum power pijmin is calculated by the free space model following [25].


### 5.2. Topology Establishment Phase

To improve the efficiency of the algorithm, nodei first needs to sort the policy set Pi=p1,p2,⋯,pl in descending order based on the obtained minimum power pijmin, where l represents the number of candidate powers of node i, and simultaneously calculate and count the number of neighboring nodes in its current transmit power range. Then, the topology game process is launched according to the node ID order and the influence of the current power of the nodes on network connectivity is determined in turn.When the network is in an unconnected state under the current power, the connectivity factor is set to 0, and the utility function under the current power level is used. The value is recorded in the neighbor table and the node must return to the previous power level that can maintain connectivity. When the network is in the connected state under the current power, the utility value function under the current power level is recorded in the neighbor table and then sequentially decreased. The low power level and the network connectivity under the current node power are determined, thereby finding the optimal power combination that satisfies the network connectivity conditions.


### 5.3. Power Adjustment Phase

After the topology establishment phase is completed, the utility values of the respective power levels satisfying the network connectivity condition are stored in the node’s neighbor table. Then, the node selects the power level by comparing the size of the utility value. To ensure that the game converges to the Nash equilibrium, the algorithm uses a better response strategy update scheme [26] to perform power adjustment. This scheme can ensure that the supermodular game with limited tactical space will converge to a pure strategy Nash equilibrium point.For any nodei, given the power p−i of the other participants, the preferred response of participant i is rip−i=minpimax,pi∗, where pi∗=argminpi∈Piuipi,p−i. During the game process, the node chooses a power level lower than the current transmitting power to communicate. Then, it observes whether the corresponding comprehensive utility function value increases. If it does increase, that power level is more suitable for use as the transmit power; otherwise, the node uses the current transmitting power to determine its maximum utility value.When the transmit power of a node changes, its communication radius, neighboring node set, and its related links will also change, which changes the network topology. As shown in Figure1, when the transmit power of node j increases, a new node i may be included in its communication range. Then, the nearest neighbor node of node j is changed from the original node k to the current node i. Therefore, node i can reduce its transmit power appropriately while still guaranteeing full network connectivity.Figure 1
Diagram of power adaptation. Three nodes adjust power for optimal topology connectivity.


### 5.4. Topology Maintenance Phase

After the topology is adjusted, the nodes in the network operate at optimal power. However, as the running time of the network increases, the difference in the amount of data processed by the nodes will become increasingly obvious. Sudden occurrences may also affect network operation. Therefore, the network topology needs to be dynamically adjusted to adapt to these changes.When the reduction in the energy level of nodei exceeds a set threshold (i.e., 10% of the initial energy of the node), the topology maintenance request message is broadcast using the maximum power pimax and the neighbor table is updated with the messages returned by each neighbor node. Any neighbor node that does not return the message is marked as dead. The node i replays the game according to the latest information obtained and selects the power pi∗ that obtains the maximum utility value in the current state as its transmission power and determines the connectivity. When the network is in the connected state, the node continues to use pi∗ for communication. When the network is in an unconnected state, the node needs to clear the local neighbor table and broadcast the topology reconstruction message at the maximum power pimax. When a surviving node in the network receives a message, the node enters the topology reconstruction phase, that is, the neighbor discovery phase is reexecuted. The pseudocode for the main process of the COETC algorithm is shown in Algorithm 1.Algorithm 1: COETC algorithm.
Neighbor discovery
1: Nodei broadcasts “Hello” message at pimax
2: Determine the neighbor setMmaxi
3: Determine the minimum powerpijmin
Topology establishment
1:Pi=p1,p2,⋯,pl in descending sort order
2: Generate the initial network topologyGmax
Power adaptation
1:while pi is not NE do
2:for i=1,i≤N,i++do
3:   choose power according topi∗=argminpi∈Piuipi,p−i
4:if ui∗pi∗,p−i≥uipi,p−ipi∗then
5:if pi∗NE then
6:pi=pi∗, update pi
7:end if
8:end if
9:end for
10:  Broadcast a “Hello” message including the new power settingpi at pimax
11:end while
Topology maintenance
Periodically re-execute the power adjustment phase


### 5.5. Algorithm Analysis

Theorem 4.
If the network topologyGmax constructed with the maximum power between nodes is connected, then the COETC algorithm will converge to a Nash equilibrium state that guarantees the connectivity characteristics of the network.Proof 2.
From Theorem3, the game model of the COETC algorithm belongs to the supermodular game. The study in [24] proves that a supermodular game with a finite strategy space can converge to a pure strategy Nash equilibrium point when it adopts a better response strategy. In the COETC algorithm proposed in this paper, the node continuously increases its utility value by adjusting the policy selection until the policy selection of all nodes no longer changes, that is, the network reaches a Nash equilibrium. This paper uses the counterevidence method: it assumes that the node can obtain a larger utility value at a lower power qi<pi (while the remaining nodes are still at the power p−i) until the network reaches an unconnected state, i.e.,
(11)uipi,p−i=αpimax−mpipi+EriE0i+βmpi∑j≠iErjE0j−mpipi∑j≠ipj,uiqi,p−i=−mpiqi∑j≠ipj.
In this paper, the network connectivity is defined as a node being able to communicate with other nodes through a two-way link; obviously, the inequalityupi,p−i<uqi,p−i is not tenable, and the assumption is inconsistent. Thus, we can conclude that the COETC algorithm constructs a connected network topology.


## 5.1. Neighbor Discovery Phase

In this phase, each node needs to discover its local neighbor nodes and build a list of neighbor information through information interchanges. Each source nodei initializes its own transmit power to the maximum transmit power pimax, by broadcasting the “Hello” message and receiving ACK messages returned by the target nodes j. The source node obtains the neighbor node information by parsing the ACK message and storing the parsed information in a neighbor table Mmaxi, generating its own policy set through the information exchange nodes.The “Hello” message includes the source node’s ID, its current transmit powerpimax, and its remaining energy Eri. The ACK message includes the target node’s ID, its minimum power pijmin, and its remaining energy Erj that can ensure normal communication with the source node, thus ensuring normal communications among network nodes. The minimum power pijmin is calculated by the free space model following [25].


## 5.2. Topology Establishment Phase

To improve the efficiency of the algorithm, nodei first needs to sort the policy set Pi=p1,p2,⋯,pl in descending order based on the obtained minimum power pijmin, where l represents the number of candidate powers of node i, and simultaneously calculate and count the number of neighboring nodes in its current transmit power range. Then, the topology game process is launched according to the node ID order and the influence of the current power of the nodes on network connectivity is determined in turn.When the network is in an unconnected state under the current power, the connectivity factor is set to 0, and the utility function under the current power level is used. The value is recorded in the neighbor table and the node must return to the previous power level that can maintain connectivity. When the network is in the connected state under the current power, the utility value function under the current power level is recorded in the neighbor table and then sequentially decreased. The low power level and the network connectivity under the current node power are determined, thereby finding the optimal power combination that satisfies the network connectivity conditions.


## 5.3. Power Adjustment Phase

After the topology establishment phase is completed, the utility values of the respective power levels satisfying the network connectivity condition are stored in the node’s neighbor table. Then, the node selects the power level by comparing the size of the utility value. To ensure that the game converges to the Nash equilibrium, the algorithm uses a better response strategy update scheme [26] to perform power adjustment. This scheme can ensure that the supermodular game with limited tactical space will converge to a pure strategy Nash equilibrium point.For any nodei, given the power p−i of the other participants, the preferred response of participant i is rip−i=minpimax,pi∗, where pi∗=argminpi∈Piuipi,p−i. During the game process, the node chooses a power level lower than the current transmitting power to communicate. Then, it observes whether the corresponding comprehensive utility function value increases. If it does increase, that power level is more suitable for use as the transmit power; otherwise, the node uses the current transmitting power to determine its maximum utility value.When the transmit power of a node changes, its communication radius, neighboring node set, and its related links will also change, which changes the network topology. As shown in Figure1, when the transmit power of node j increases, a new node i may be included in its communication range. Then, the nearest neighbor node of node j is changed from the original node k to the current node i. Therefore, node i can reduce its transmit power appropriately while still guaranteeing full network connectivity.Figure 1
Diagram of power adaptation. Three nodes adjust power for optimal topology connectivity.


## 5.4. Topology Maintenance Phase

After the topology is adjusted, the nodes in the network operate at optimal power. However, as the running time of the network increases, the difference in the amount of data processed by the nodes will become increasingly obvious. Sudden occurrences may also affect network operation. Therefore, the network topology needs to be dynamically adjusted to adapt to these changes.When the reduction in the energy level of nodei exceeds a set threshold (i.e., 10% of the initial energy of the node), the topology maintenance request message is broadcast using the maximum power pimax and the neighbor table is updated with the messages returned by each neighbor node. Any neighbor node that does not return the message is marked as dead. The node i replays the game according to the latest information obtained and selects the power pi∗ that obtains the maximum utility value in the current state as its transmission power and determines the connectivity. When the network is in the connected state, the node continues to use pi∗ for communication. When the network is in an unconnected state, the node needs to clear the local neighbor table and broadcast the topology reconstruction message at the maximum power pimax. When a surviving node in the network receives a message, the node enters the topology reconstruction phase, that is, the neighbor discovery phase is reexecuted. The pseudocode for the main process of the COETC algorithm is shown in Algorithm 1.Algorithm 1: COETC algorithm.
Neighbor discovery
1: Nodei broadcasts “Hello” message at pimax
2: Determine the neighbor setMmaxi
3: Determine the minimum powerpijmin
Topology establishment
1:Pi=p1,p2,⋯,pl in descending sort order
2: Generate the initial network topologyGmax
Power adaptation
1:while pi is not NE do
2:for i=1,i≤N,i++do
3:   choose power according topi∗=argminpi∈Piuipi,p−i
4:if ui∗pi∗,p−i≥uipi,p−ipi∗then
5:if pi∗NE then
6:pi=pi∗, update pi
7:end if
8:end if
9:end for
10:  Broadcast a “Hello” message including the new power settingpi at pimax
11:end while
Topology maintenance
Periodically re-execute the power adjustment phase


## 5.5. Algorithm Analysis

Theorem 4.
If the network topologyGmax constructed with the maximum power between nodes is connected, then the COETC algorithm will converge to a Nash equilibrium state that guarantees the connectivity characteristics of the network.Proof 2.
From Theorem3, the game model of the COETC algorithm belongs to the supermodular game. The study in [24] proves that a supermodular game with a finite strategy space can converge to a pure strategy Nash equilibrium point when it adopts a better response strategy. In the COETC algorithm proposed in this paper, the node continuously increases its utility value by adjusting the policy selection until the policy selection of all nodes no longer changes, that is, the network reaches a Nash equilibrium. This paper uses the counterevidence method: it assumes that the node can obtain a larger utility value at a lower power qi<pi (while the remaining nodes are still at the power p−i) until the network reaches an unconnected state, i.e.,
(11)uipi,p−i=αpimax−mpipi+EriE0i+βmpi∑j≠iErjE0j−mpipi∑j≠ipj,uiqi,p−i=−mpiqi∑j≠ipj.
In this paper, the network connectivity is defined as a node being able to communicate with other nodes through a two-way link; obviously, the inequalityupi,p−i<uqi,p−i is not tenable, and the assumption is inconsistent. Thus, we can conclude that the COETC algorithm constructs a connected network topology.


## 6. Simulation Results Analysis

In this paper, the MATLAB R2016a simulation software is used to simulate the topology control algorithm COETC based on a supermodular game. The distributed optimal response control algorithm (DIA) proposed in [12], a topology control game algorithm MLPT based on link power consumption from [13], and a distributed energy balance topology control algorithm DEBA from [17] are used as comparisons to the COETC algorithm. All the simulation experiments assume that the nodes are randomly scattered and cannot be moved. The specific simulation parameters are set as shown in Table 1.Table 1
Specific parameter settings during the experiment.
Parameter name
Parameter size
Monitoring area
150m×150m
Communication radius
50 m
Node initial energy
50 J
Wavelengthλ
0.1224 m
Receiving threshold
7×10−10W
Transmit antenna gainGt
1
Receive antenna gainGr
1
System lossL
1We randomly assigned 50 nodes in the monitoring area. In the experiment, we need to determine the weight values for factorα and β in the COETC algorithm. For convenience, this paper sets β=1 [12, 17] and then observes the influence of the two weighting factors on network topology performance as the value of α changes. The values are determined from the average transmit power of nodes, the average residual energy of adjacent nodes, the average node degree, and the average hop number of the shortest path between nodes.In our experiments,α is a discrete value from 0.2 to 6. For the clarity of the illustration, we show the trend of change of α=0.2,0.6,2,6 in the figure. As Figure 2(a) shows, the average transmission power of a node decreases as α increases. Figure 2(b) shows that the average residual energy of adjacent nodes decreases as α increases. In Figure 2(c), the average node degree of the network decreases as α increases, and Figure 2(d) shows the average hop count between nodes, which generally increases as α increases. The changes after α≥2 tended to stabilize. According to the characteristics of the wireless sensor network topology [27], when the transmit power of the nodes in the network is low and there are moderate node degrees and average hop counts, the structure of the network topology can be considered perfect. When α≥2, the impact on network performance has become similar; thus, for the convenience of calculation, the value of α was taken as the intermediate value between 2 and 6. Therefore, the combination of node computing capability and network performance is considered; in this paper, parameter α is set to 4 and parameter β to 1.Figure 2
The impact ofλ on network performance when β=1.
(a)
The average transmit power of the node
(b)
Average residual energy of adjacent nodes
(c)
Average node degree
(d)
Average hop number between two nodesTo visually compare the topologies of the four algorithms DIA, MLPT, DEBA, and COETC, 50 nodes are randomly scattered in a monitoring area of150m×150m, generating the network topology diagram shown in Figure 3. It can be seen from the figure that the network topology generated by the DIA algorithm contains nodes with less residual energy and heavy loads. These nodes may die while the remaining nodes still possess residual energy, which affects network connectivity and robustness. The network topology constructed by the DEBA algorithm has a higher node degree, which leads to higher energy consumption. The network topology constructed by the MLPT and COETC algorithms both have lower node degrees, but MLPT has some very long single-links, which reduces robustness, and the number of connected nodes per link in COETC topology is more uniform than in MLPT. Therefore, the COETC algorithm has better network connectivity and robustness, which effectively balances node loads.Figure 3
Network topology comparison chart.
(a)
DIA algorithm
(b)
MLPT algorithm
(c)
DEBA algorithm
(d)
COETC algorithmFigure4 shows a comparison of the survival time obtained by running the four algorithms. In this paper, we define the network lifetime as the time when 60% of the nodes in the network die. For all the algorithms, the network lifetime decreases as the number of nodes increase, but the lifetime of the network constructed by the COETC algorithm is always the longest. Because the COETC algorithm considers node degree and residual energy balance in the design of utility function, it can dynamically adjust the network topology based on node residual energy and actively encourage nodes with more energy to participate in network operation, which effectively balances network energy consumption. Due to this increased energy efficiency, the survival time for networks built using COETC is substantially longer than for networks built using the DIA, MLPT, and DEBA algorithms.Figure 4
Network survival time. Comparison of the survival time of four algorithms under a different number of nodes.Figure5 shows a comparison of node transmission power. As the graph shows, the average transmit power decreases as the number of nodes increases. The COETC algorithm generates the lowest transmit power in the network topology and can obtain the lowest transmitting power while ensuring network connectivity and robustness. Moreover, it results in better energy efficiency than do the network topologies constructed by the DIA, MLPT, and DEBA algorithms.Figure 5
Node average transmit power. Comparison of average transmit power of nodes in four algorithms with different number of nodes.Figure6 shows a comparison of average node degree, showing that the node degree of the network topology generated by the COETC algorithm is slightly higher than that of the DIA algorithm but slightly below that of the MLPT and DEBA algorithms. The COETC algorithm considers the node degree and the residual energy of the neighbor nodes when designing the utility function. Nodes with more residual energy will increase their transmit power to balance the network energy consumption. Therefore, COETC results in a node degree slightly higher than that of the DIA algorithm. Compared with the DIA, MLPT, and DEBA algorithms, the COETC algorithm has a moderate node degree, better network robustness, and higher energy efficiency.Figure 6
Average node degree. Comparison of average node degrees of four algorithms with a different number of nodes.Figure7 shows that the average hop number of the COETC algorithm is higher than that of the MLPT algorithm but lower than that of the DIA and DEBA algorithms. The node transmit power of the MLPT algorithm is high, and its communication coverage is wide. Therefore, the number of forwarding nodes must be relatively small. However, the COETC algorithm uses a lower transmit power but still obtains a good link hop value. This result occurs because the COETC algorithm constructs a superior network topology structure compared to the other three algorithms.Figure 7
Average hop count of the shortest path. Comparison of average hop counts of the shortest paths of four algorithms with a different number of nodes.To compare the energy balance of the four algorithms, the standard deviation of the node residual energy at a certain time is obtained for each algorithm, as shown in Figure8. The graph shows that the residual energy standard deviation of the COETC algorithm is lower than that of the DIA, MLPT, and DEBA algorithms, and its upward trend is slow. The node residual energy standard deviation of the MLPT algorithm increases the fastest, which indicates that its node transmit power is high and that it neglects energy efficiency in the network. The trends in DIA and DEBA algorithms are more pronounced than the COETC algorithm, which indicates that although DIA and DEBA consider energy efficiency, they do not fully maintain energy balance. The COETC algorithm not only considers the residual energy of the node but also considers the residual energy of the neighboring nodes, which effectively balances the network energy consumption, improves the energy efficiency, and enhances the network performance.Figure 8
Standard deviation of node residual energy. Comparison of the residual energy variance of nodes in four algorithms.


## 7. Conclusions

To accurately describe the game behavior between nodes and to obtain an optimized network topology that improves network operational efficiency, by combining game theory and the concept of a supermodular game, this paper integrates a variety of performance parameters across the protocol layer to design a utility function that considers network performance comprehensively. First, we constructed a new topological game model and provided a theoretical proof. The game model belongs to the supermodular game family, in which a pure strategy Nash equilibrium exists. Then, we proposed a cross-layer optimized WSN energy-balance equilibrium game algorithm (COETG). Through simulation experiments, we verified that the COETG algorithm can reduce the node transmit power and form an optimized network topology while ensuring network connectivity and robustness, balancing network energy consumption, and improving network energy efficiency to effectively prolong network lifetime.Future work involves optimizing the algorithm for real wireless communication situations by balancing energy consumption and topology control of WSNs in real environments.



---

*Source: 6963290-2019-11-05.xml*