Sage Journals: Discover world-class research

Abstract

The ongoing development of wireless sensor networks has been greatly restricted because of scarce spectrum resources, limited battery power, and ineffective topologic structures. Thus, how to construct a suitable topological structure and allocate the appropriate node channels has become an urgent problem. In this study, we built a game model that took into account the influence of channel allocation and topology structure on network performance. The game model considered the nodes in wireless sensor networks to be players and took transmitting power, node channels, and node rest energy into account to establish the income function. Then, the model certified that it has Nash equilibrium. Next, we propose an energy-optimized game algorithm joint topology and channel for wireless sensor network (CETGA) in accordance with the game model. The CETGA algorithm improved each node’s income by changing the transmitting power and node channel gradually, assuming that the network retained connectivity. Then, we demonstrated that the algorithm could converge to a Pareto optimal. Finally, we used MATLAB software to verify the simulation. The results show that the topology created by CETGA is with low interference and long lifetime. In addition, the nodes’ average residual energy is more balanced and the network robustness and real time are improved.

Keywords

Channel energy game theory topologic structure wireless sensor networks

Introduction

Lots of tiny sensor nodes communicate with each other and constitute a multihop self-organizing network which is named wireless sensor network (WSN).¹ WSN is widely used, not only to measure various physical parameters, but also in many monitoring fields,^2,3 such as agricultural surveying,⁴ smart traffic monitoring,⁵ environmental monitoring,⁶ medical applications,⁷ and many other fields. The topological structure of a WSN greatly influences the reduction of interference and energy consumption, the enhancement of network robustness in real time, and the prolonging of the network’s lifetime.⁸ In addition, channel allocation (CA) provides the foundation for further reducing interference and increasing network capacity.⁹ Therefore, an urgent problem for WSN has become how to design a proper topological control algorithm to improve network reliability and many other issues based on network connectivity.

Currently, the two types of WSNs, single channel and multichannel, influence its topology control.

In a single-channel WSN, power control is the main method and is likely to reduce transmitting power to prolong the network’s lifetime. Basing their design on the local minimum spanning tree, Li et al.¹⁰ proposed a local minimum spanning tree algorithm to devise a connective topology. But the network’s robustness was poor because the structure was sparse. Zhou et al.¹¹ proposed a control algorithm for network topological connection optimization based on network efficiency and average connection degree to increase the network’s throughput. But the algorithm is not suitable for a WSN because the node energy is limited. Li et al.¹² provided a distributed topology control algorithm that considered the transmitting and receiving powers of nodes synthetically. The algorithm provided a method to extend the network life cycle by analyzing the effects of node communication distance, circuit loss, and node load on the network. Chen et al.¹³ constructed a load balancing evaluation mode by researching the relationship between neighbor-residual energy, transmission power, and load. And then proposed a distributed topology control algorithm to show that the model can balance network load and energy consumption.

However, limited spectrum resources have greatly restricted WSN’s further application. Thus, the combination of multichannel technology and topology control is utilized to optimize the performance In Thomas et al.,¹⁴ the algorithm was divided into two parts: power control was used to construct the topology structure, and CA was used to optimize network performance. But the method was just a simple superposition of the two parts and did not take into account the internal relations between them, so the topology structure obtained did not result in the best performance. Li et al.¹⁵ used dynamic adjustment of power and channel to increase antidisturbance ability of the network, which improved throughput and enhanced stability. The paper explored the combined optimization of power and channel, however the topology was dynamic. Because the consumption of node energy was large, that method is not suited for WSN, whose available energy is limited. Hao et al.¹⁶ proposed a distributed topology control and CA algorithm to establish an optimized network. The network can possess the lower inference and many other attractive network performances such as the stronger robustness. But the physical interference model is used in their model, which is too complex to quickly finish the calculation when the node number is much large. By studying the relationship between k-connected logical topology and the maximum number of assigned channels, Bao et al.¹⁷ presented the lower and upper bounds of the maximum allowable number of assigned channels for k-connected logical topology and a static channel assignment algorithm according to minimum spanning tree search. Derdouri et al.¹⁸ studied multicast features in wireless mesh networks by taking advantage of shared links to reach simultaneously multiple users and then evaluate the performance of two algorithms, one named Node Joining the Multicast tree and the other named Node Disjoining the Multicast tree to improve the throughput, delay, and robustness.

Basing our work on the analysis above, we first established an energy-optimized game model joint topology and channel for a WSN. Then, we designed an energy-optimized game algorithm joint topology and channel Joint channel and energy topology game algorithm, (CETGA) based on the model. The unique features are as follows:

The CETGA takes node energy consumption and network interference into account to formulate the game model’s utility function. In addition, if a node’s residual energy decreases, the node is more likely to retain its transmitting power to increase the utility value.

In the CETGA, a node, whose residual energy is low, is more likely to choose the minimum power to reduce consumption itself. Meanwhile, the immediately adjacent nodes, whose residual energy is higher, must use more power to keep the network connected. Thus, the energy consumption is balanced.

In the CETGA, every node adaptively adjusts its channel when the power changes. Then, the network is settled finally.

Establishment and analysis of the model

In a WSN, sensor nodes consume energy when they communicate with each other. Because the energy of nodes is limited, most nodes are likely to be “selfish.” In other words, a sensor node is inclined to optimize its own income as much as possible instead of collaborating with other nodes to improve the performance of the entire network. The status of the WSN completely matches the application of game theory. Thus, how to determine the network structure of WSN could be attributed to the optimal solution for a combinatorial algorithm based on game theory.^19–21 In section “The game model,” a CETGA for a WSN is established.

The game model

To establish a game model for a WSN, the definition of node interference, named the interference model, which is based on the neighbor node number,²² is as follows.

Definition 1 (node interference)

The interference $I_{k}^{(c)} (p_{k}^{(c)})$ of any node k using channel c is the sum of node numbers. A node’s number contains two parts: one is the interference generated by node k (i.e. the node number using channel $c$ contained in the scope of node $k$ using $p_{k}^{(c)}$ ), the other is the interference suffered by $k$ (i.e. the times $k$ contained by any other node with $c$ ).

According to Fudenberg and Tirole,²³ a game model comprises three factors: player set, policy set, and income function. Here, players are the decision-makers in the gaming process, while policy set is the collection of all policies. Income function is the income of each player when the policy changes.

In our model, we designated an energy-optimized game model joint topology and channel as $G = {N, S, u}$ , of which $N$ , $S$ , $u$ respectively represents the factor motioned in a game model. The player set shown as $N = {1, . . ., k, . . ., n}$ , $n$ is total number of all nodes and $k$ is any one node in WSN. In addition, we use $- k$ to denote nodes in WSN that are not $k$ . The policy set S is $S = (S_{k}, S_{- k})$ , where $S_{k}$ is the policy of $k$ and $S_{- k}$ is other node’s policy vectors instead of $k$ . The policy set of any node $k$ is $S_{k} = {(p_{k}, c_{k})}$ , $p_{k} \in A_{k}$ and $c_{k} \in C_{k}$ . Here, $p_{k}$ refers to node k’s transmitting power, $A_{k}$ is an ordered policy set, and $A_{k} = {p_{max} = p^{0}, p^{1}, p^{2}, . . ., p^{v} = p_{min}}$ , where $p^{v} < p^{v - 1}$ . $p_{min}$ is the minimum power, whereas $p_{max}$ is the maximum in WSN. $c_{k}$ is k’s channel, and $C_{k}$ is the policy set. Let $C_{k} = {1, 2, . . ., C}$ , where $C$ is the maximum channel number that can be available in our model and the channels that we use in this paper are all orthogonal channels. Any node k’s income under the policy combinations $(S_{k}, S_{- k})$ can be expressed as $u_{k} (S_{k}, S_{- k})$ , and the income function $u = {u_{1}, u_{2}, . . ., u_{n}}$ consists of all nodes’ incomes. The income function is as follows

\begin{matrix} u_{k} (p, c) = f_{k} (p, c) [α I_{k} (p_{max}) + β \frac{p_{max}}{E_{r} (k)}] \\ - α I_{k}^{(c)} (p_{k}^{(c)}) - β \frac{p_{k}}{E_{r} (k)} \end{matrix}

(1)

In equation (1), $f_{k} (p, c)$ is the connectivity of network and it is the monotonic increasing function of $p$ . If the transmitting power $p$ is large enough, the network is connected and $f_{k} (p, c) = 1$ , else $f_{k} (p, c) = 0$ . $p_{max}$ is the maximum transmitting power. Take Definition 1 as a reference, $I_{k} (p_{max})$ can be considered as node k’s interference using $p_{max}$ and it also comprises two parts: one is the number of nodes covered by $k$ using $p_{max}$ , and the other is the times that k contained by any other node with $p_{max}$ . Obviously, the inequality $I_{k} (p_{max}) \geq I_{k}^{(c)} (p_{k}^{(c)})$ always holds. $α$ and $β$ are non-negative weight factors. $E_{r} (k)$ is node k’s residual energy. $I_{k}^{(c)} (p_{k}^{(c)})$ refers to k’s interference value based on Definition 1. $p_{k}^{(c)}$ represents k’s present transmitting power at $c$ , here $p_{k} = p_{k}^{(c)}$ .

The income function can reflect many aspects of network performance; the major aspects are as follows:

Network connectivity is the basic requirement of the topology construction for WSNs. Information can be transmitted effectively in the network only if the conductivity of the WSN is guaranteed. In equation (1), $f_{k} (p, c)$ is the connectivity of the network. $f_{k} (p, c) = 1$ indicates that the network is connected; $f_{k} (p, c) = 0$ indicates that it is disconnected. If the network is disconnected, the value of u is negative because α and β are non-negative. In this way, the connectivity of WSN can be maintained during the process of building the topological structure.

For an energy-constrained WSN, the node’s energy supply is an important factor that affects the lifetime of the WSN. The lower the residual energy $E_{r} (k)$ of any node k is, the greater $1 / E_{r} (k)$ is. In this circumstance, the change of node k’s transmitting power $p_{k}$ has a greater effect on utility. In equation (1), the value of weight factor $β$ is non-negative. When the residual energy $E_{r} (k)$ is lower and the transmitting power $p_{k}$ is greater, the node k’s income of utility function becomes smaller. Thus, if node k’s residual energy is relatively lower, the node tends to choose lower transmission power to reduce its own energy consumption.

Network interference is an important indicator for evaluating the performance of a WSN. The amount of network interference directly affects the quality and efficiency of communication. In equation (1), $- α I_{k}^{(c)} (p_{k}^{(c)})$ refers to the node k’s interference. Because the weight factor $α$ is non-negative, the greater the network interference, the lower the node’s income value. Besides, based on the definition of $I_{k}^{(c)} (p_{k}^{(c)})$ and the illustration of $I_{k} (p_{max})$ , the inequality $I_{k} (p_{max}) \geq I_{k}^{(c)} (p_{k}^{(c)})$ set up forever.

Model analysis

Nash equilibrium (NE) is the solution of the game model and all players want to achieve this status. Its definition is given as follows.

Definition 2 (NE)

For $i \in N$ , $s_{i} \in S_{i}$ , the policy combination $s^{*} = {S_{1}^{*}, S_{2}^{*}, . . ., S_{n}^{*}}$ is an NE of $G = {N, S, u}$ if we have²³

u_{i} (s_{i}^{*}, s_{- i}^{*}) \geq u_{i} (s_{i}, s_{- i}^{*})

(2)

There are many ways to prove the existence of NE, and the ordinal potential game (OPG) is one of them.

Definition 3 (OPG)

When an ordinal potential function (OPF) $V : S \to R$ can be established by equation (3), $G = {N, S, u}$ is an OPG²⁴

V (s_{i}, s_{- i}) - V (t_{i}, s_{- i}) < 0 \Leftrightarrow u_{i} (s_{i}, s_{- i}) - u_{i} (t_{i}, s_{- i}) < 0

(3)

where $s_{- i} \in S_{- i}$ , $s_{i}, t_{i} \in S_{i}$ , and $i \in N$ .

From Monderer and Shapley,²⁴ if a model is found to be an OPG, there must be at least one NE. Thus, Lemma 1 is given first.

Lemma 1

For any node $k$ , if −k’s states stay the same, the change of k’s interference is the same as the sum of −k’s interference changes.

Proof

The change of k’s interference is $Δ I_{k} = I_{k}^{(c)} (p_{k}^{(c)}) - I_{k}^{(c')} (q_{k}^{(c')})$ .Based on Definition 1, the description is below.

The interference created by $k$ is the sum of j’s interference subjected by $k$ (here $j$ is the other node except $k$ ), while the interference subjected by $k$ is the sum of j’s interference created by $k$ . Thus, the interference change created by $k$ is the same as the sum of the interference change subjected by $j$ , and the interference change subjected by $k$ is the same as the sum of the interference change created by $j$ . Thus, equation (4) is always true

Δ I_{k} = \sum_{j \in N, j \neq k} Δ I_{j}

(4)

Theorem 1

The energy-optimized game model joint topology and channel $G = {N, S, u}$ is an OPG. Its OPF is

\begin{matrix} V (p, c) = \sum_{k \in N} f_{k} (p, c) [α I_{k} (p_{max}) + 2 β \frac{p_{max}}{E_{r} (k)}] \\ - α \sum_{k \in N} I_{k}^{(c)} (p_{k}^{(c)}) - 2 β \sum_{k \in N} \frac{p_{k}}{E_{r} (k)} \end{matrix}

(5)

Proof

Assume that −k’s states stay the same, k’s income change is shown in equation (6) if $k$ changes from $(p_{k}, c_{k})$ to $(q_{k}, {c_{k}}^{'})$

\begin{matrix} Δ u_{k} = u_{k} (p_{k}, c_{k}; p_{- k}, c_{- k}) - u_{k} (q_{k}, {c_{k}}^{'}; p_{- k}, c_{- k}) \\ = [f_{k} (p, c) - {f_{k}}^{'} (q, c^{'})] [α I_{k} (p_{max}) + β \frac{p_{max}}{E_{r} (k)}] \\ - α Δ I_{k} - β [\frac{p_{k} - q_{k}}{E_{r} (k)}] \end{matrix}

(6)

By this time, the change of $ordinal potential function$ V is

\begin{matrix} Δ V = V (p_{k}, c_{k}; p_{- k}, c_{- k}) - V (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = Δ u_{k} + β \sum_{k \in N} [(f_{k} (p, c) - {f'}_{k} (q, c')) \frac{p_{max}}{E_{r} (k)} - \frac{(p_{k} - q_{k})}{E_{r} (k)}] \\ - α \sum_{j \in N, j \neq k} Δ I_{j} \\ + \sum_{j \in N, j \neq k} [(f_{j} (p, c) - {f'}_{j} (q, c')) (α I_{j} (p_{max}) + \frac{β}{E_{r} (j)} p_{max})] \end{matrix}

(7)

$f$ is the monotonic increasing function of $p$ , and four situations are now discussed to prove Theorem 1.

(1) $f_{k} (p, c) = {f_{k}}^{'} (q, c^{'}) = 1$

\begin{matrix} Δ u_{k} = u_{k} (p_{k}, c_{k}; p_{- k}, c_{- k}) \\ - u_{k} (q_{k}, c'_{k}; p_{- k}, c_{- k}) = - α Δ I_{k} - β [\frac{p_{k} - q_{k}}{E_{r} (k)}] \end{matrix}

\begin{matrix} Δ V = V (p_{k}, c_{k}; p_{- k}, c_{- k}) - V (q_{k}, c'_{k}; p_{- k}, c_{- k}) \\ = Δ u_{k} - α \sum_{j \in N, j \neq k} Δ I_{j} - β \sum_{k \in N} [\frac{(p_{k} - q_{k})}{E_{r} (k)}] \end{matrix}

Because the power and channels of the nodes except k remain unchanged, the equation $\sum_{j \in N, j \neq k} [\frac{(p_{j} - q_{j})}{E_{r} (j)}] = 0$ always holds. Moreover, $Δ I_{k} = \sum_{j \in N, j \neq k} Δ I_{j}$ is true according to equation (4). So the equation above can be simplified as follows

Δ V = Δ u_{k} - α \sum_{j \in N, j \neq k} Δ I_{j} - β [\frac{(p_{k} - q_{k})}{E_{r} (k)}] = 2 Δ u_{k}

Thus, we can conclude that $Δ V = 2 Δ u_{k}$ . Clearly, we have $sgn (Δ V) = sgn (Δ u_{k})$ .

(2) $f_{k} (p, c) = f'_{k} (q, c^{'}) = 0$

\begin{matrix} Δ u_{k} = u_{k} (p_{k}, c_{k}; p_{- k}, c_{- k}) - u_{k} (q_{k}, c'_{k}; p_{- k}, c_{- k}) \\ = - α Δ I_{k} - β [\frac{p_{k} - q_{k}}{E_{r} (k)}] \end{matrix}

\begin{matrix} Δ V = V (p_{k}, c_{k}; p_{- k}, c_{- k}) - V (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = Δ u_{k} - β \sum_{k \in N} [\frac{(p_{k} - q_{k})}{E_{r} (k)}] - α \sum_{j \in N, j \neq k} Δ I_{j} \\ = Δ u_{k} - α \sum_{j \in N, j \neq k} Δ I_{j} - β [\frac{(p_{k} - q_{k})}{E_{r} (k)}] = 2 Δ u_{k} \end{matrix}

Thus, we can conclude that $Δ V = 2 Δ u_{k}$ . Clearly, we have $sgn (Δ V) = sgn (Δ u_{k})$ .

(3) $f_{k} (p, c) = 1$ and ${f_{k}}^{'} (q, c^{'}) = 0$

$f_{k} (p, c) = 1$ represents the network is connected when node $k$ uses transmission power $p$ . Since −k’s states stay the same, when k’s power changes from $p$ to $q$ , $f'_{k} (q, c^{'}) = 0$ (i.e. the network is no longer connected), which means that k’s power decreases, then we can get $p > q$

\begin{matrix} Δ u_{k} = u_{k} (p_{k}, c_{k}; p_{- k}, c_{- k}) - u_{k} (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = α I_{k} (p_{max}) + β \frac{p_{max}}{E_{r} (k)} \\ - α [I_{k}^{(c)} (p_{k}^{(c)}) - I_{k}^{(c')} (q_{k}^{(c')})] - β [\frac{p_{k} - q_{k}}{E_{r} (k)}] \\ = α [I_{k} (p_{max}) - I_{k}^{(c)} (p_{k}^{(c)}) + I_{k}^{(c')} (q_{k}^{(c')})] \\ + \frac{β}{E_{r} (k)} (p_{max} - p_{k} + q_{k}) \end{matrix}

$α$ and $β$ are non-negative. And the inequalities $I_{k} (p_{max}) \geq I_{k}^{(c)} (p_{k}^{(c)})$ and $p_{max} \geq p_{k}$ always stand up, then $Δ u_{k} > 0$

\begin{matrix} Δ V = V (p_{k}, c_{k}; p_{- k}, c_{- k}) - V (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = Δ u_{k} + β \sum_{k \in N} [\frac{p_{max}}{E_{r} (k)} - \frac{(p_{k} - q_{k})}{E_{r} (k)}] \\ - α \sum_{j \in N, j \neq k} Δ I_{j} + \sum_{j \in N, j \neq k} [α I (p_{max}) + \frac{β}{E_{r} (j)} p_{max}] \\ = Δ u_{k} + β \sum_{k \in N} [\frac{p_{max} - p_{k} + q_{k}}{E_{r} (k)}] + β \sum_{j \in N, j \neq k} [\frac{p_{max}}{E_{r} (j)}] \\ + α \sum_{j \in N, j \neq k} [I_{k} (p_{max}) - I_{k}^{(c)} (p_{k}^{(c)}) + I_{k}^{(c')} (q_{k}^{(c')})] \end{matrix}

So we can conclude that $Δ V > 0$ because $Δ u_{k} > 0$ . Clearly, we have $sgn (Δ V) = sgn (Δ u_{k})$ .

(4) $f_{k} (p, c) = 0$ and $f'_{k} (q, c^{'}) = 1$

$f_{k} (p, c) = 0$ represents the network is disconnected when node $k$ uses transmission power $p$ . Since −k’s states stay the same, when k’s power changes from $p$ to $q$ , $f'_{k} (q, c^{'}) = 1$ (i.e. the network is connected), which means that k’s power increases, then we can get $p < q$

\begin{matrix} Δ u_{k} = u_{k} (p_{k}, c_{k}; p_{- k}, c_{- k}) - u_{k} (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = - [α I_{k} (p_{max}) + β \frac{p_{max}}{E_{r} (k)}] - α Δ I_{k} - β [\frac{p_{k} - q_{k}}{E_{r} (k)}] \\ = - α [I_{k} (p_{max}) + I_{k}^{(c)} (p_{k}^{(c)}) - I_{k}^{(c')} (q_{k}^{(c')})] \\ - \frac{β}{E_{r} (k)} (p_{max} + p_{k} - q_{k}) \end{matrix}

$α$ and $β$ are non-negative. And the inequalities $I_{k} (p_{max}) \geq I_{k}^{(c)} (p_{k}^{(c)})$ and $p_{max} \geq p_{k}$ always stand up, then $Δ u_{k} < 0$

\begin{matrix} Δ V = V (p_{k}, c_{k}; p_{- k}, c_{- k}) - V (q_{k}, {c'}_{k}; p_{- k}, c_{- k}) \\ = Δ u_{k} - β \sum_{k \in N} [\frac{p_{max}}{E_{r} (k)} + \frac{(p_{k} - q_{k})}{E_{r} (k)}] \\ - α \sum_{j \in N, j \neq k} Δ I_{j} - \sum_{j \in N, j \neq k} [α I_{j} (p_{max}) + \frac{β}{E_{r} (j)} p_{max}] \\ = Δ u_{k} - β \sum_{k \in N} [\frac{p_{max} + p_{k} - q_{k}}{E_{r} (k)}] - β \sum_{j \in N, j \neq k} [\frac{p_{max}}{E_{r} (j)}] \\ - α \sum_{j \in N, j \neq k} [I_{k} (p_{max}) + I_{k}^{(c)} (p_{k}^{(c)}) - I_{k}^{(c')} (q_{k}^{(c')})] \end{matrix}

So we can conclude that $Δ V < 0$ because $Δ u_{k} < 0$ . Clearly, we have $sgn (Δ V) = sgn (Δ u_{k})$ .

In conclusion, $sgn (Δ V) = sgn (Δ u_{k})$ . So the energy-optimized game model joint topology and channel $G = {N, S, u}$ is OPG.

Theorem 2

An NE must exist in CETGA $G = {N, S, u}$ .

Proof

Since CETGA $G = {N, S, u}$ is an OPG, the policy combination which can maximize its OPF is an NE.

In $G = {N, S, u}$ , the policy combination is limited, so there must exist one policy which can make the OPF V maximum. That is, $G = {N, S, u}$ has an NE.

CETGA

Considering the relation between topology and channel, a CETGA is established to solve the model and this algorithm considers not only the node residual energy but also the convergence.

CETGA algorithm

In CETGA, each node first gathers other nodes’ information in its achievable region, and then decides its policy. The process is as follows:

Let all nodes’ power be the maximum power and their channel the same channel $c^{(0)}$ .

$m = 0$ , $round = 0$ .

k’s current power is $p_{k} = p^{(m)} \in A_{k}$ and current channel is $c_{k} = c^{(round)} \in C_{k}$ .

Based on equation (1), any node k’s income value $u_{k}$ is obtained. Judge whether every node reach an NE. In other words, if all nodes’ income values are the same as that in previous cycle, CETGA ends, or it goes to (5).

$m = m + 1$

$k = 1$

Judge whether the network is connected: if it is, CETGA goes to (8); if not, $k$ remains its power and channel in last cycle, that is, $p_{k} = p^{(m - 1)}$ , $c_{k} = c^{(round - 1)}$ .

At present, k’s income is $u_{k}^{(m)} = max (u_{k} (p^{(m)}, 1), . . ., u_{k} (p^{(m)}, C))$ when $p_{k} = p^{(m)}$ . Then k’s power would be $p_{k}^{*} = \arg max (u_{k}^{(m)}, u_{k}^{(m - 1)}, . . ., u_{k}^{(0)})$ and channel be $c_{k}^{*} = \arg max (u_{k} (p^{*}, 1), . . ., u_{k} (p^{*}, C))$

If $k < n$ , $k = k + 1$ , CETGA turns to (7). If $k \geq n$ , $round = round + 1$ and CETGA turns to (4).

The flow diagram of algorithm is shown as follows.

CETGA analysis

To energy-constrained WSNs, whether the algorithm can converge is a most important feature. Theorem 3 verifies the ability to converge.

Theorem 3

CETGA can converge to NE.

Proof

According to CETGA, every node in WSN reduces its power and chooses the best channel in each cycle. Thus, three possible situations should be discussed

p_{k}^{new} \neq p_{k}^{old}, c_{k}^{new} = c_{k}^{old};

p_{k}^{new} \neq p_{k}^{old}, c_{k}^{new} \neq c_{k}^{old};

p_{k}^{new} = p_{k}^{old}, c_{k}^{new} \neq c_{k}^{old} .

Among the situations mentioned above, we can easily conclude that $u_{k} (new) \geq u_{k} (old) \Rightarrow \sum_{j \in N, j \neq k} u_{j} (new) \geq \sum_{j \in N, j \neq k} u_{j} (old)$ . Because the function is monotonic and the power level and channel number are limited in the policy set, the CETGA can converge finally.

In a game model, the states of NE can be divided into three situations: none, one, or numerous. From Theorem 1, CETGA can converge to NE. But there is no guarantee that CETGA can converge to optimal NE. To achieve the optimal solution, another important concept is required.

Definition 4 (pareto optimality, PO)

A policy vector $s^{*}$ is PO if no such policy vector exists to make $u_{i} (s^{*}) \leq u_{i} (s)$ for any $i \in N$ , and $u_{j} (s^{*}) < u_{j} (s)$ for at least one $j \in N$ .²⁵

Theorem 4

CETGA can converge to PO.

Proof

Nodes in the network obtained by CETGA could be separated into two main categories: (1) nodes using minimum power are to maintain the network nonseparation and (2) nodes with non-minimum power are to guarantee network robustness and real time.

If k’s residual energy reduces, $k$ would increase its income by decreasing its power to the minimum power. In this case, the structure would not be connected if k’s power were continuously reduced after the algorithm ceased. At this time, if the network requires connectivity, nodes other than $k$ should increase their power but will decrease their incomes.

If a node k’s residual energy is relatively large, $k$ has a larger power to guarantee the income itself. Right now, no matter reduce k’s power or change others’ station will decrease k’s income.

Overall, no one can increase its own income without decreasing that of others. Based on Definition 4, CETGA can converge to PO.

Simulation verification

The network performance is studied by MATLAB. Assuming that nodes’ residual energy in WSN is subject to Poisson distribution. Every node’s maximal transmission range is $d_{max} = 150 m$ and the power threshold is $p_{th} = 7 \times 10^{- 10} w$ .

Weight value determination

In equation (1), $α$ and $β$ are unknown. Thus, we studied the influence of weight value change on network performance. We placed 30 nodes in the $300 m \times 300 m$ region randomly. Given $β = 1$ , Figure 1 shows the network performance when $α$ is 0.1, 0.5, 1, 3, and 5 separately.

Figure 1.

The flow diagram of algorithm.

From Figure 2, when $α = 0.1$ or $α = 0.5$ , it is easier to waste node energy during information transmission because the average transmission power is higher. At the same time, the average interference of nodes is greater as well. Thus, transmitting information affects each node, which increases the packet loss rate and reduces the transmission accuracy of the network. Moreover, the greater channel variance represents an unbalanced CA.

Figure 2.

Performance influence of $α$ when $β = 1$ . Part a and b are non-negative weight factors.

When $α = 3$ or $α = 5$ , the power reduces, so is the average residual energy. Then, the network robustness is relatively poor and once a node dies, the whole network is paralyzed. What is more, the network real time is reduced. That augments the forward number during information transmission, which increases the node energy consumption to a certain degree.

In conclusion, decide that the weight value as $α = 1$ and $β = 1$ .

Network structure

Randomly selected 30 nodes to place in a $300 m \times 300 m$ region and assumed that the maximum channel number was 5. Then, we compared the CETGA with a combination of the distance to ideal control (DIA) topology control algorithm²⁶ and the CA algorithm.²⁷

In Figure 3, the different colors indicate that the nodes used different orthogonal channels. In each node mark (x, y), x is the node number and y is the residual energy of the node x.

Figure 3.

Network structure comparison: (a) DIA + CA and (b) CETGA.

In Figure 3(a), the topology of DIA + CA is relatively simple. One or more nodes in the WSN undertook too many forwarding tasks; for example, nodes 3, 5, and 11. Because the algorithm did not take node energy into consideration, some nodes with lower residual energy were placed into the forward position and died prematurely, which would reduce the network’s lifetime. In Figure 3(b), at the cost of improving node transmission power appropriately, some nodes added other transmission paths to reduce forward tasking and enhance the network’s robustness. In this way, the real-time performance was improved and the network’s lifetime was prolonged.

Topology performance

We raised 20–40 nodes in $300 m \times 300 m$ , and let the maximum number of orthogonal channel to be 5. Figure 4 compares the performances of the CETGA and the DIA + CA.

Figure 4.

Comparison of performances with an increased number of nodes. The red line CETGA is the optimization algorithm that mentioned in this paper while the green one DIA+CA is the contrast algorithm. The comparison of performances between the two algorithm is shown in page 8, Topology performance.

The average transmission power is the mean value of nodes’s transmission power in the network, and the less the average transmission power is,the less energy consumption will be. Then the average node degree directly affects the robustness performance of the network. As shown in Figure 4(a) and (b), the topology obtained by the CETGA had a slightly higher power and node degree than those of DIA + CA. This clearly shows that the proposed algorithm can create a topology structure that can reduce node power and energy consumption as well as enhance robustness and real-time performance based on guaranteeing network connectivity.

The average node interference represents the degree of interaction between nodes in the transmission process and the average residual energy within the node transmission range directly affects the lifetime of the network. In Figure 4(c) and (d), the average node interference in the CETGA’s topology was less and the average residual energy within the node transmission range was greater than those of the DIA + CA. Thus, the CETGA can reduce inference and extend life of WSN.

The channel variance is the level of equalization using the channel. In Figure 4(e), the relatively small channel variance further illustrates the superiority of the proposed algorithm.

The average-hop of the shortest path between two nodes represents the real-time performance of network transmission. In Figure 4(f), the topology obtained by CETGA has better real-time performance. Moreover, the algorithm can reduce network energy consumption by reducing the number of forwarding tasks.

Conclusion

Basing our work on game theory, we studied the problem of topology and channel. We first built an energy-optimized game model joint topology and channel. We then designed a utility function considering node transmission power, node channels, and residual energy. The proposed model was determined to be an OPG with an NE.

Second, in accordance with the model we designed an energy-optimized game algorithm joint topology and channel (CETGA). The algorithm increased the node income by gradually reducing the node transmission power and adjusting the node channel. The algorithm could then be certified to converge to Pareto optimality in guaranteeing network connectivity.

Finally, MATLAB was used to make simulation. Simulation result verified that the topology obtained by the CETGA could result in a more balanced structure and better robustness and real-time performance. Moreover, the average node interference is relatively small, which can ensure the accuracy of the information transmission. In addition, the average residual energy of the nodes is higher, which can effectively prolong the lifetime of the network.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Major Program of the National Natural Science Foundation of China (No. 11790282), the Young Top-Notch Talents Program of Higher School in Hebei Province (No. BJ2019035), the Local science and technology development fund projects guided by the central government (No. 206Z1901G), the Preferred Program of Hebei Postdoctoral Research (No. B2019003017), National Natural Science Foundation of China (No. 11702179,51605315), and Natural Science Foundation of Hebei Province (No. E2018210052).

ORCID iD

Mei-Qi Wang

Data availability

The position of sensor nodes is scattered randomly. According to CETGA algorithm, the randomly distributed sensor nodes can constitute a network topology structure which has better performances.

References

Sun

. Wireless sensor network. Beijing, China: Tsinghua University Press, 2004.

Song

Luo

. Redundant path control method for wireless sensor network based on node health degree. Acta Phys Sin 2014; 63(12): 387–399.

Liu

. Distributed power control mechanism based on utility model in wireless sensor networks. Chin J Electron 2016; (2): 301–307.

Naseer Sabri

Aljunid

Ahmad

, et al. Performance evaluation of wireless sensor network channel in agricultural application. Am J Appl Sci 2013; 9(1): 141–151.

Liu

Zhang

. Research on urban intelligent traffic monitoring system based on wireless sensors and networks. In: The 2nd national conference on information technology and computer science, Shanghai, China, 21 March 2015.

Al-Turjman

Hassaneinb

Ibnkahlac

. Towards prolonged lifetime for deployed WSNs in outdoor environment monitoring. Ad Hoc Netw 2015; 24: 172–185.

Zhang

. The research and application on security of wireless sensor network in the medical. MS Thesis, Liaoning University, Shenyang, China, 2015.

Zhang

. Research on topology control for wireless sensor networks. PhD Dissertation, University of Electronic Science and Technology of China, Chengdu, China, 2013.

Zhang

Huang

Zhang

. Research on channel assignment algorithm for wireless mesh networks based on connected low interference. J Univ Electron Sci Tech China 2014; 43(6): 817–822.

10.

Hou

Sba

. Design and analysis of an MST-based topology control algorithm. IEEE T Wirel Commun 2005; 4(3): 1195–1206.

11.

Zhou

Yang

Zhang

, et al. Topology connection optimization control method for complex network system. Acta Phys Sin 2013; 15(9): 150201.

12.

Wang

. A topology control algorithm for maximizing the lifetime of Hoc Ad networks. J Comp Res Dev 2013; 50(3): 461–471.

13.

Chen

Yao

Liu

, et al. Distributed topology control algorithm based on load balancing evaluation model in wireless sensor networks. Wireless Pers Commun 2019; 109(4): 2607–2625.

14.

Thomas

Komali

MacKenzie

, et al. Joint power and channel minimization in topology control: a cognitive network approach. In: International conference on communications, Glasgow, 24–28 June 2007, pp. 6538–6543. New York: IEEE.

15.

Liu

. Capacity-based channel assignment scheme in multi-radio multi-channel wireless mesh networks. J Electron 2015; 24(2): 419–425.

16.

Hao

Wang

Hou

, et al. Distributed topology control and channel allocation algorithm for energy efficiency in wireless sensor network: from a game perspective. Wireless Pers Commun 2015; 80(4): 1557–1577.

17.

Bao

Tan

Nie

, et al. Design of logical topology with K-connected constraints and channel assignment for multi-radio wireless mesh networks. Int J Commun Syst 2017; 30(1): e2914.

18.

Derdouri

Pham

Zouaoui

EMEA

, et al. Performance analysis of self-organised multicast group in multi-radio multi-channel wireless mesh networks. IET Commun 2020; 14(4): 693–702.

19.

Feng

Peng-Cheng

. A topology control algorithm for wireless sensor networks based on the potential game theory. Acta Phys Sin 2016; 65(2): 028401.

20.

Tan

Liu

Han

, et al. Energy harvesting aware topology control with power adaptation in wireless sensor networks. In: IEEE wireless communications and networking conference (WCNC), Istanbul, Turkey, 6–9 April 2014, p. 2722–2727. New York: IEEE.

21.

Argento

Cesana

Gatti

, et al. A game theoretical study of access point association in wireless mesh networks. Comp Commun 2012; 35(5): 541–553.

22.

Liu

. Research of the power control based on the region physical interference model in the wireless mesh networks. MS Thesis, Jilin University, Changchun, China, 2014.

23.

Fudenberg

Tirole

. Game theory. Cambridge, MA: The MIT Press, 1991.

24.

Monderer

Shapley

. Potential games. Game Econ Behav 1996; 14: 124–143.

25.

Chen

Fan

, et al. Multi-channel assignment in wireless sensor networks: a game theoretic approach. In: Proceedings of IEEE INFOCOM, 14–19 March 2010, San Diego, CA, pp. 1–9. New York: IEEE.

26.

Komali

. Game-theoretic analysis of topology control. PhD Dissertation, Virginia Polytechnic Institute and State University, Blacksburg, VA, 2008.

27.

Incel

van Hoesel

Jansen

, et al. MC-LMAC: a multi-channel MAC protocol for wireless sensor networks. Ad Hoc Netw 2011(9): 73–94.

An energy-optimized game algorithm for wireless sensor networks

Abstract

Keywords

Introduction

Establishment and analysis of the model

The game model

Definition 1 (node interference)

Model analysis

Definition 2 (NE)

Definition 3 (OPG)

Lemma 1

Proof

Theorem 1

Proof

Theorem 2

Proof

CETGA

CETGA algorithm

CETGA analysis

Theorem 3

Proof

Definition 4 (pareto optimality, PO)

Theorem 4

Proof

Simulation verification

Weight value determination

Network structure

Topology performance

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

Data availability

References