1 Introduction

Wireless sensor network (WSN) is a self-organizing communication network with multi-hop feature, which consists of numerous tiny sensor nodes spread in monitoring area [1]. WSN is widely used in many fields such as medical treatment, military affairs and environmental monitoring because of the low cost, wide covered area and many other features [2]. Consequently, researches on wireless sensor network have become a hot issue nowadays [3].

Topological structure of networks, acting as the supporting framework of WSN [4], has a great influence on reducing the network interference, enhancing the network robustness, prolonging the network lifetime etc. Therefore, how to construct a proper topological structure is very important to WSN.

The topological structure is usually resulted from topology control algorithms. In recent years, researchers have proposed many topology control algorithms for wireless networks to alleviate the interference and balance the energy consumption [5–7], but most of them, such as EEDAT [8] and DIA [9], reduce the interference and energy consumption by decreasing the node transmission power. Such as been shown in Fig. 1a, any node would use the minimum transmitting power to guarantee the network connectivity. Since the transmitting power is in proportion to the Euclidean distance, we can use the distance between nodes to represent the power. For example, the node 1 whose residual energy is 32 will choose its nearest node (node 2) to be its director neighbor in Fig. 1a. Thus, the topology can reduce the interference and energy consumption. But these algorithms don’t consider the residual energy and can not balance the energy consumption. From Fig. 1a, we can see that node 2 and node 5 are both with less residual energy and they undertake the responsibility of retransmission for other nodes. Therefore, it is likely to run out of the energy of these two nodes and shorten the network lifetime. In order to reduce and balance the node energy consumption, the topology control algorithms should consider the residual energy of each node and avoid the nodes that with less energy from dying too early. In Fig. 1b, node 2 has the less residual energy and will choose its nearest node 3 to transmit. When it comes to node 1, it will concern its neighbor’s energy to decide the transmission power to ensure the network connectivity since node 1’s residual energy is relatively large. Then the topology in Fig. 1b can balance the energy consumption and prolong the network lifetime compared to Fig. 1a.

Fig. 1
figure 1

Comparison figure of different topology algorithms (the first letter \(x\) in \((x,y)\) represents the node number while the last letter \(y\) indicates the node residual energy). a Topology control without residual energy. b Topology control with residual energy

Full size image

Although the topology control can improve certain network performance, the only topology control is not enough to alleviate the interference [10–12]. For example, Fig. 2a is the topology after topology control algorithm. If the two links which are colored green are transmitting message at the same time in Fig. 2a, they may interfere each other because the nodes of these two links have the very close position. For the sake of getting a better network performance, we need the channel allocation method to be introduced into this topology just like Fig. 2b. In Fig. 2b, the link 2–3 will choose channel 1 to transmit while the link 5–6 will select channel 2. Here, the red color is shown as channel 1 and the blue color represents channel 2. By making the links that are interfering each other as well as transmitting simultaneously use the different channels, the interference of the WSN would be further alleviated in Fig. 2b.

Fig. 2
figure 2

Comparison figure of single channel and multi-channel. a Topology without channel allocation. b Topology with channel allocation

Full size image

From the above analysis, we can conclude that channel allocation can alleviate interference [13–15]. However, it will do little good to strengthen the network performance without topology control. For instance, the topology in Fig. 3a is the channel allocation result without topology control. As shown in Fig. 3a, nodes in the network will use the maximum power to construct the topology structure. Besides, the link 1–2 and link 4–5 use the same channel while the link 5–6 uses another channel. From Fig. 3a, the link 1–2 will suffer interference from link 4–5 because the transmitting power of node 4 and node 5 is too large. Thus, just as shown in Fig. 3b, we need the topology control to choose the appropriate power for nodes and the channel allocation to alleviate the network interference. From Fig. 3b, the interference is reduced since the transmitting power of nodes decrease and the node channel is allocated. So the combination of topology control and channel allocation brings a better performance to the wireless sensor network.

Fig. 3
figure 3

Comparison figure of channel allocation under different topology controls. a Channel allocation without topology control. b Channel allocation with topology control

Full size image

According to the above analysis, we design a Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) for energy efficiency in WSN. DTCCAA has fully considered the interactions between topology and channel allocation: On one hand, node channel is affected by topology control. The different topology structure will cause lots differences of the optimal channel allocation. On the other hand, the result of topology is closely related to network channel station. Besides, DTCCAA takes the node power, interference and residual energy into consideration as well. In DTCCAA, the node with less residual energy prefers to choose the nearest node to be its neighbor to ensure the network connectivity while other nodes select transmitting power by considering some other properties. Thus, DTCCAA can alleviate the interference and balance the energy consumption as well as enhance the robustness on the premise of guaranteeing the network connectivity.

The paper is organized as follows. In Sect. 2, we will review the relevant work. Section 3 presents a Distributed Topology Control and Channel Allocation Game Model for energy efficiency in WSN and gives the game-theoretic analysis of this model. On the basis of the model, we propose a Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) and then analyze its characteristic in Sect. 4. In Sect. 5, we evaluate the effectiveness of DTCCAA through simulations. Finally, Sect. 6 presents the concluding remarks.

2 Related Works

Topology control is one of the most fundamental problems in wireless sensor networks. It is very important for prolonging the network lifetime, reducing the node interference and increasing the network capacity, among other things [16]. Currently, the researches on topology control of WSN can be divided into two groups: the single channel and the muti-channel.

In single channel wireless network, the topology control is mainly centralized on the power control. Its basic theory is to prolong the network lifetime by decreasing the transmitting power of nodes in WSN.

CHEN [8] and other authors advanced a topology control algorithm (EEDAT) which can collect the data accurately to gain the bi-directed topology. The topology structure has great connectivity. But the obtained topology is with the tree structure, so the robustness and real-time is relatively weak. LMA and LMN [17] put forward by Kubisch are the algorithms based on the node degree. The basic idea is that every node adjusts its transmitting power dynamically to make its own node degree maintain in the given node degree bound. Thus, we can change the topology structure by choosing the different node degree bound to enhance the robustness and real-time. However, the algorithm is very difficult to guarantee the network connectivity generally. Li [18] raised a algorithm named Cone-Based Topology Control Algorithm (CBTC) which needed the nodes’ direction instead of their location to construct a topology. The basic idea is that any node \(u\) chooses the minimum power \(p_{u,\rho }\) to make sure that at least one neighbor exists in the cone which uses \(u\) as the center and \(\rho \) as the angle. Besides, the algorithm had been proved to guarantee the network connectivity when \(\rho \le 5 \pi /6\). Nevertheless, CBTC does not take the node residual energy into consideration. Hao [19] designed a topology control algorithm based on the game theory. The algorithm builds a game model taking the residual energy as the utility function. Through solving the model, a topology which can balance the energy consumption of nodes and guarantee the connectivity of network is obtained. EECA [20] reduced the energy consumption without significantly affecting the capacity or the network connectivity. Through electing coordinators from all nodes in the network depending on random back-off delay and rotating them in time, the algorithm shows that network connectivity and capacity are both preserved.

Nevertheless, with the development of WSN, the topology control with single channel has been unable to meet the requirement of the network performance. The finiteness of spectrum resources also limits the further application of WSN. Thus, for the purpose of alleviating the co-channel interference and improving the communication reliability, channel allocation technology is introduced into WSN combined with topology control technology to optimize the network performance.

Thomas [21] presented a cognitive network approach to achieving the objectives of power and spectrum management. He first used a pure power control game to minimize their transmitting power level and maintain the network connectivity and then utilize the channel control to minimize the total number of channel. In reference [22], the author constructed a topology to minimize maximum interference in wireless mesh network. He presented a graph-theoretic formulation while preserving connectivity from a single channel scenario. Then he designed a centralized channel assignment algorithm that greedily found low interference topologies. But both of them divided the problem into two phases: the power control part and the channel allocation apart. Then the two phases were simply combined without considering the internal connection (described in Sect. 1) between topology control and channel allocation. Thus, the topology structure obtained will probably not reach the best network performance. Therefore, the interaction between topology control and channel allocation should be considered carefully in WSN. Song [23] proposed a negotiation-based throughput maximization algorithm from a game theoretical perspective. The algorithm adjusts the operating channel and power level among access points automatically. The algorithm is proven to converge to the optimal channel and power assignment which leads to the maximum overall throughput. Liu [24] and other authors utilized the dynamic adjusting of the transmission power, the communication frequency and the interfaces to increase the multiplexing degrees of network space. Then, the anti-disturbance capability and the network throughput will be improved and the network stability will be enhanced. The two papers mentioned above are both considering the combined optimization of power and channel, but the topologies constructed by both of them are dynamic topology. Since the dynamic topology is changing via time, the nodes in the topology would be send as well as collect information all the time. So the energy consumption is very large, which is not suit for WSN which has limited energy. Gong [25] constructed a static topology structure by proposing a joint design of topology control and channel assignment for WSN to improve the PRR of each link in WSN. The algorithm first constructs a maximum PRR spanning tree, and then adjusts the transmitting power and channel of sensor nodes to further improve the PRR of links on the tree. In this way, the network throughput, energy efficiency and end-to-end packet delay will be significantly improved. However, the algorithm does not take the influence of the network performance and energy into account. Therefore, they are not suitable for WSN either.

Based on the above existing problems, we firstly formulate a Distributed Topology Control and Channel Allocation Game Model for WSN. Then we propose a Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) based on this model. Our approach is different from the above mentioned strategies with the following unique features:

  1. (1)

    The game model takes the network interference, connectivity and energy consumption into consideration. Besides, the utility function of the game model defines a relationship between transmitting power and node residual energy: the less a node’s residual energy is, the greater influence that from the transmitting power to utility function the node has.

  2. (2)

    In our algorithm, the nodes with less residual energy will use the minimum power to reduce their energy while other nodes will choose some available nodes with higher energy as their direct neighbors to balance the energy consumption according to the game model.

  3. (3)

    In DTCCAA, each node adaptively tunes its channel when the transmitting power changes by considering the interactions between topology control and channel allocation. Thus, the result of topology and channel is settled at the same time.

3 Distributed Topology Control and Channel Allocation Game Model

Game theory is a branch of applied mathematics and is a mathematical tool for analyzing the complex conflict between the rational and the intelligent entities. Hence, it is usually used to solve the problem of non-cooperative optimization [26]. Since the nodes in wireless sensor network take the maximization of their own utility as the target and choose the strategies to assemble non-cooperatively, the topology control issue of WSN can be abstracted as a combinatorial optimization problem. In this section, we construct a Distributed Topology Control and Channel Allocation Game Model for energy efficiency in WSN based on the related work of game theory. Then the game model is discussed in Sect. 3.2.

3.1 The Establishment of Model

Since the game model mainly includes 3 basic factors [27], we can indicate the Distributed Topology Control and Channel Allocation Game Model as \(G=\{N,S,u\}\) in WSN, where \(N\) is the player set, \(S\) is the strategy profile and \(u\) is the utility function. The specific illustration is shown as follows:

  1. (1)

    Player Set \(N\): Player refers to the specific decision-making body during the game process. In our model, player set can be expressed as \(N=\{1,{\ldots },k,{\ldots },n\}\), where \(n\) is the total number of nodes in WSN. \(k\) represents one node while \(-k\) donates other nodes in WSN except \(k\).

  2. (2)

    Strategy Profile S: Strategy profile is the space of all strategy vectors and it can be expressed as \(S=(S_{k},S_{-k})\) in our model, where \(S_{k}\) is the optional strategy of any node \(k\) and \(S_{-k}\) is the strategy vector of other nodes except \(k\). For any node \(k\), its strategy set is \(S_{k}=\{(p_{k},c_{k})\}\), where \(p_{k}\in A_{k}\) and \(c_{k}\in C_{k}\). Here, \(p_{k}\) is the transmitting power of node \(k\). \(A_{k}\) is an ordered strategy set which indicates the optional power set of node \(k\) and \(A_{k}=\{p_{max}=p^{0},\,p^{1},\,p^{2},{\ldots },p^{v}=p_{min}\}\), where \(p^{v}<p^{v-1}\). \(p_{min}\) is the minimum power in the network while \(p_{max}\) is the maximum power. \(c_{k}\) refers to the channel of node \(k\) and \(C_{k}\) is the strategy set of the available channel. We have that \(C_{k}=\{1,2,{\ldots },\hbox {C}\}\), where \(C\) is the maximal channel number that can be used in wireless sensor network.

  3. (3)

    Utility Function \(u\): Each player’s income \(u\) changes with the different strategy. In our model, \(u_{k}(S_{k},\,S_{-k})\) represents the income of node \(k\) under the strategy combination of \((S_{k},\,S_{-k})\). The utility function \(u=\{u_{1},\,u_{2},{\ldots },u_{n}\}\) of the game model consist of all the players’ income under different strategy combinations. The utility function in our paper is shown as follow,

    $$\begin{aligned} u_k (p,c)&= f_k (p,c)\left[ {\alpha n_{p_{\max } } +\alpha e^{1-{E_r (k)}/{E_0 (k)}}p_{\max } +\beta \overline{E_k (p_k )} } \right] \nonumber \\&-\alpha e^{1-{E_r (k)}/{E_0 (k)}}p_k -\alpha I_k^{(c)} (p_k^{(c)} ) \end{aligned}$$
    (1)

Here, \(f_{k}(p,c)\) is the connected factor. \(f_{k}(p,c)\)=1 is on be half of the connected network while \(f_{k}(p,c)=0\) stands for the disconnected one. \(n_{p_{\max }}\) is the sum of the node number that is covered by some node and the frequency that the node is covered by other nodes using the max power in wireless sensor network. \(\alpha ,\, \beta \) are non negative weight factors. \(\overline{E_k (p_k )}\) is the average value of \(E_{r}(j)/E_{0}(j)\), where \(j\) is the neighbor node of node \(k\) with the maximum power and \(E_{r}(j)\) is the residual energy of node \(j\) while \(E_{0}(j)\) is the initial energy of \(j\). \(p_{\max },\,p_k,\,p_k^{(c)} \) refer to the maximum transmitting power, the current transmitting power and the current transmitting power at channel \(c\) of the node \(k\) respectively. There we have \(p_k =p_k^{(c)} \). \(e^{1-{E_r (k)}/{E_0 (k)}}\) represents that the transmitting power of node \(k\) takes a more important place in utility function when its residual energy is smaller. \(I_k^{(c)} (p_k^{(c)})\) refers to the interference value of node \(k\) using channel \(c\). It is defined as the sum of node number that uses channel \(c\) as well as covered by node \(k\) using \(p_k^{(c)}\) and the frequency that the node \(k\) is covered by other nodes using channel \(c\) in the network. Thus we have the \(n_{p_{\max } } \ge I_k^{(c)} (p_k^{(c)} )\) always holds.

3.2 Game-Theoretic Analysis of Model

In game theory, Nash Equilibrium is the final result which is wanted to be reached. At the equilibrium state, all players don’t desire to deviate from this state initiatively. When it comes to the WSN, each node decides its strategy and all the strategies make up a strategy vector. The strategy vector will be the Nash Equilibrium state if it can maximize the utility function value. When the game achieves the Nash Equilibrium, the income of other nodes will suffer a loss if any node changes its strategy alone. The definition of Nash Equilibrium is given as follow.

Definition 1

(Nash Equilibrium) [27]: To any \(i\in N\) and \(s_{i}\in S_{i}\), the strategy combination \(s^{*}{ =\{s^{*}_{1}, s^{*} _{2},{\ldots }, s^{*} _{n}\}}\) is a Nash Equilibrium of game \(G=\{N,S,u\}\) if we have,

$$\begin{aligned} u_i (s_i^*, s_{-i})\ge u_i (s_i , s_{-i}) \end{aligned}$$
(2)

The existence of Nash Equilibrium is an important factor of game theory when solving the combinatorial optimization problem. For the moment, there are many methods to testify whether the Nash Equilibrium exists or not. Ordinal Potential Game is a kind of special game that guarantees the existence of Nash Equilibrium. The definition of Ordinal Potential Game is shown as follow.

Definition 2

(Ordinal Potential Game)[28]: Strategic game \(G=\{N,S,u\}\) is an OPG, if there is an Ordinal Potential Function (OPF) \(V:S\rightarrow {{\varvec{R}}}\), to satisfy

$$\begin{aligned} V(\hbox {s}_i ,\hbox {s}_{-i} )-V(t_i ,\hbox {s}_{-i} )<0\Leftrightarrow u_i (\hbox {s}_i ,\hbox {s}_{-i} )-u_i (t_i ,\hbox {s}_{-i} )<0 \end{aligned}$$
(3)

Where \(s_{-i}\in S_{-I}\) and \(s_{i},t_{i}\in S_{i}\) and \(i\in N\).

According to reference [28], at least one Nash Equilibrium would exist in the Ordinal Potential Game. Thus, the Distributed Topology Control and Channel Allocation Game Model of WSN mentioned in Sect. 3.1 must have more than one Nash Equilibrium if it can be proven as an Ordinal Potential Game. In order to simplify the proof procedure, we give Lemma 1 as follow.

Lemma 1

To any node \(k\) in WSN, the node \(k\)’s interference change is equal to the sum of all other nodes’ interference change if the state of other nodes except \(k\) remains unchanged.

Proof

The interference change of any node \(k\) in WSN can be described as \(\Delta I_{k}= I^{(c)}_{k}\left( p^{(c)}_{k}\right) - I^{(c')}_{k}\left( p^{(c')} _{k}{^\prime }\right) \). Since the interference \(I_{k}\) of node \(k\) consists of two parts: the interference generated by node \(k\) and the interference suffered by node \(k\). Obviously, the interference generated by node \(k\) is the total interference of other nodes suffered by node \(k\); the interference suffered by node \(k\) is the total interference of other nodes generated by node \(k\). Accordingly, the change in interference that generated by node \(k\) is equal to the total change in interference that suffers by all the other node \(j\) while the change in interference that suffer by node \(k\) is equal to the total change in interference that generated by all the other node \(j\). From the analysis we will get the identical equation as follow,

$$\begin{aligned} \Delta I_k =\sum _{j\in N,j\ne k} {\Delta I_j } \end{aligned}$$
(4)

\(\square \)

Theorem 1

The Distributed Topology Control and Channel Allocation Game Model \(G=\{N,S,u\}\) is an Ordinal Potential Game. Its ordinal potential function is given by (5).

$$\begin{aligned} V(p,c)&= \sum _{k\in N} {f_k (p,c)\left[ {\alpha n_{p_{\max } } +2\alpha e^{1-{E_r (k)}/{E_0 (k)}}p_{\max } +2\beta \overline{E_k (p_k )} } \right] } \nonumber \\&-2\alpha \sum _{k\in N} {\left[ {e^{1-{E_r (k)}/{E_0 (k)}}p_k } \right] } -\alpha \sum _{k\in N} {I_k^{(c)} (p_k^{(c)} )} \end{aligned}$$
(5)

Proof

When node \(k\) change its state from (\(p_{k},c_{k}\)) to \((p_{k}^{{\prime }},\,c_{k}^{{\prime }})\) as the states of other nodes remain unchanged, the utility change of node \(k\) is as follow,

$$\begin{aligned} \Delta u_k&= u_k (p_k ,c_k ;p_{-k} ,c_{-k} )-u_k ({p}'_k ,{c}'_k ;p_{-k} ,c_{-k} ) \nonumber \\&= \left[ {\alpha n_{p_{\max } } +\alpha e^{1-{E_r (k)}/{E_0 (k)}}p_{\max } } \right] \left[ {f_k (p_k ,c_k ;p_{-k} ,c_{-k} )-f_k^{\prime }({p}'_k ,{c}'_k ;p_{-k} ,c_{-k} )} \right] \nonumber \\&+\beta \left[ {f_k (p_k ,c_k ;p_{-k} ,c_{-k} )\overline{E_k (p_k )} -f_k^{\prime }({p}'_k ,{c}'_k ;p_{-k} ,c_{-k} )\overline{E_k (p_k ^{\prime })} } \right] \nonumber \\&-\alpha e^{1-{E_r (k)}/{E_0 (k)}}\left[ {p_k -p_k ^{\prime }} \right] -\alpha \left[ {I_k^{(c)} (p_k^{(c)} )-I_k^{({c}')} (p_k^{({c}')} {^{\prime }})} \right] \end{aligned}$$
(6)

At this moment, the difference value of Ordinal Potential Function \(V\) for the game mode is as follow,

$$\begin{aligned} \Delta V&= V(p_k ,c_k ;p_{-k} ,c_{-k} )-V({p}'_k ,{c}'_k ;p_{-k} ,c_{-k} ) \nonumber \\&= \Delta u_k \!+\!\sum _{j\in N,j\ne k} {\left[ {\left( {\alpha n_{p_{\max } } \!+\!\alpha e^{1-{E_r (k)}/{E_0 (k)}}p_{\max } \!+\!\beta \overline{E_j (p_j )} } \right) \left( {f_j (p,c)-f_j^{\prime }(p,c)} \right) } \right] } \nonumber \\&+\beta \sum _{k\in N} {\left[ {f_k (p_k ,c_k ;p_{-k} ,c_{-k} )\overline{E_k (p_k )} -f_k^{\prime }({p}'_k ,{c}'_k ;p_{-k} ,c_{-k} )\overline{E_k (p_k ^{\prime })} } \right] } \nonumber \\&-\alpha \sum _{j\in N,j\ne k} {\Delta I_j } \nonumber \\&+\alpha \sum _{k\in N} {\left[ {e^{1-{E_r (k)}/{E_0 (k)}}p_{\max } \left( {f_j (p,c)-f_j^{\prime }(p,c)} \right) } \right] } \nonumber \\&-\alpha \sum _{k\in N} {e^{1-{E_r (k)}/{E_0 (k)}}\left( {p_k -p_k ^{\prime }} \right) } \end{aligned}$$
(7)

Since \(f\) is the connected factor, \(f\) is related to the transmitting power \(p\) of WSN and the relationship between them is linear. That is to say, if the connected factor \(f\) increases, the transmitting power \(p\) of node will increase as well. Next, we will divide the problem into four parts to prove Theorem 2.

  1. 1.

    \(f_{k}(p,c)=f_{k}^{{\prime }}(p,c)=1;\)

    $$\begin{aligned} \Delta u_k&= \beta [\overline{E_k (p_k )} -\overline{E_k (p_k ^{\prime })} ]-\alpha e^{1-{E_r (k)}/{E_0 (k)}}(p_k -p_k ^{\prime })-\alpha \Delta I_k \end{aligned}$$
    (8)
    $$\begin{aligned} \Delta V&= \Delta u_k \!+\!\beta [\overline{E_k (p_k )} \!-\!\overline{E_k (p_k ^{\prime })} ]\!-\!\alpha e^{1-{E_r (k)}/{E_0 (k)}}(p_k -p_k ^{\prime })-\alpha \!\sum _{j\in N,j\ne k} {\Delta I_j }\qquad \end{aligned}$$
    (9)

    According to Eq. (4), \(\Delta I_k =\sum \nolimits _{j\in N,j\ne k} {\Delta I_j } \) is true. Thus, we can get the conclusion that \(\Delta V=2\triangle u_{k}\). Clearly, we have \(\hbox {sgn}(\Delta V)=\hbox {sgn}(\Delta u_{k})\).

  2. 2.

    \(f_{k}(p,c)=f_{k}^{{\prime }}(p,c)=0;\)

    $$\begin{aligned} \Delta u_k&= -\alpha e^{1-{E_r (k)}/{E_0 (k)}}(p_k -p_k ^{\prime })-\alpha \Delta I_k \end{aligned}$$
    (10)
    $$\begin{aligned} \Delta V&= \Delta u_k -\alpha e^{1-{E_r (k)}/{E_0 (k)}}(p_k -p_k ^{\prime })-\alpha \sum _{j\in N,j\ne k} {\Delta I_j } \end{aligned}$$
    (11)

    According to Eq. (4), \(\Delta I_k =\sum \nolimits _{j\in N,j\ne k} {\Delta I_j } \) is true. Thus, we can get the conclusion that \(\Delta V=2\triangle u_{k}\). Clearly, we have \(\hbox {sgn}(\Delta V)=\hbox {sgn}(\Delta u_{k})\).

  3. 3.

    \(f_{k}(p,c)=1, f_{k}^{{\prime }}(p,c)=0;\) Because \(f\) is the monotone-increasing function of the transmitting power \(p\) and \(f_{k}>f_{k}^{{\prime }}\) is held at the moment, we have the real function \(p>p^{{\prime }}\).

    $$\begin{aligned} \Delta u_k&= \alpha \left[ {n_{p_{\max } } -I_k^{(c)} (p_k^{(c)} )+I_k^{({c}')} (p_k^{({c}')} {^{\prime }})} \right] \nonumber \\&+\,\alpha e^{1-{E_r (k)}/{E_0 (k)}}\left[ {p_{\max } -p_k +p_k ^{\prime }} \right] +\beta \overline{E_k (p_k )} \end{aligned}$$
    (12)

    For any node \(k\in N\), the inequality \(n_{p_{\max } } \ge I_k^{(c)} (p_k^{(c)})\) and \(p_{\max } \ge p_k \) always hold. Besides, \(\alpha \) and \(\beta \) are non negative weight factors. So \(\Delta u_{k}>\)0 can be obtained here.

    $$\begin{aligned} \Delta V&= \Delta u_k +\beta \left( {\sum _{k\in N} {\overline{E_k (p_k )} } +\sum _{j\in N,j\ne k} {\overline{E_j (p_j )} } } \right) +\alpha \sum _{j\in N,j\ne k} {\left( {e^{1-{E_r (j)}/{E_0 (j)}}p_{\max } } \right) } \nonumber \\&+\,\alpha \sum _{j\in N,j\ne k} {\left( {n_{p_{\max } } -I_j^{(c)} (p_j^{(c)} )+I_j^{({c}')} (p_j^{({c}')} {^{\prime }})} \right) } \nonumber \\&+\,\alpha \sum _{k\in N} {\left[ {e^{1-{E_r (k)}/{E_0 (k)}}\left( {p_{\max } -p_k +p_k ^{\prime }} \right) } \right] } \end{aligned}$$
    (13)

    For any node \(k\in N\), the inequality \(n_{p_{\max } } \ge I_k^{(c)} (p_k^{(c)} )\) and \(p_{max}\ge p_{k}\) always hold. So we can get \(\Delta V>0\) since \(\Delta u_{k}>0\) is obtained above. Clearly, \(\hbox {sgn}(\Delta V)=\hbox {sgn}(\Delta u_{k})\) is tenable.

  4. 4.

    \(f_{k}(p,c)=0, f_{k}^{{\prime }}(p,c)=1\). Because \(f\) is the monotone-increasing function of the transmitting power \(p\) and \(f_{k}<f_{k}^{{\prime }}\) is held at the moment, we have the real function \(p<p^{{\prime }}\).

    $$\begin{aligned} \Delta u_k&= -\alpha \left[ {n_{p_{\max } } -I_k^{(c)} (p_k^{(c)} )+I_k^{({c}')} (p_k^{({c}')} {^{\prime }})} \right] \nonumber \\&-\alpha e^{1-{E_r (k)}/{E_0 (k)}}\left[ {p_{\max } -p_k +p_k ^{\prime }} \right] -\beta \overline{E_k (p_k ^{\prime })} \end{aligned}$$
    (14)

For any node \(k\in N\), the inequality \(n_{p_{\max } } \ge I_k^{(c)} (p_k^{(c)} )\) and \(p_{max}\ge p_{k}\) always hold. Besides, \(\alpha \) and \(\beta \) are non negative weight factors. So \(\Delta u_{k}<0\) can be obtained here.

$$\begin{aligned} \Delta V&= \Delta u_k -\beta \left( {\sum _{k\in N} {\overline{E_k (p_k ^{\prime })} } +\sum _{j\in N,j\ne k} {\overline{E_j (p_j )} } } \right) -\alpha \sum _{j\in N,j\ne k} {\left( {e^{1-{E_r (j)}/{E_0 (j)}}p_{\max } } \right) } \nonumber \\&-\alpha \sum _{j\in N,j\ne k} {\left( {n_{p_{\max } } -I_j^{(c)} (p_j^{(c)} )+I_j^{({c}')} (p_j^{({c}')} {^{\prime }})} \right) } \nonumber \\&-\alpha \sum _{k\in N} {e^{1-{E_r (k)}/{E_0 (k)}}\left( {p_{\max } -p_k +p_k ^{\prime }} \right) } \end{aligned}$$
(15)

For any node \(k\in N\), the inequality \(n_{p_{\max } } \ge I_k^{(c)} (p_k^{(c)} )\) and \(p_{max}\ge p_{k}\) always hold. So we can get \(\Delta V<0\) since \(\Delta u_{k}<0\) is obtained above. Clearly, \(\hbox {sgn}(\Delta V)=\hbox {sgn}(\Delta u_{k})\) is tenable.

In conclusion, it always has \(\hbox {sgn}(\Delta V)=\hbox {sgn}(\Delta u_{k})\) for any node \(k\in N \). Therefore, on the basis of the definition 2, the Distributed Topology Control and Channel Allocation Game Model \(G=\{N,S,u\}\) is an Ordinal Potential Game. \(\square \)

Theorem 2

Nash Equilibrium must be existed in the Distributed Topology Control and Channel Allocation Game Model \(G=\{N,S,u\}\).

Proof

It is shown in Theorem 1 that the Distributed Topology Control and Channel Allocation Game Model \(G=\{N,S,u\}\) is an Ordinal Potential Game. So the strategy combination that maximizes its ordinal potential function is the Nash Equilibrium of the game model. Moreover, since the strategy profile of the game is limited, a strategy combination must exist and make the ordinal potential function \(V\) reach to the maximum. In other words, Nash Equilibrium must exist in the game model \(G=\{N,S,u\}\). \(\square \)

4 Distributed Topology Control and Channel Allocation Algorithm (DTCCAA)

In this section, we propose a Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) which aims at solving the game model proposed in Sect. 3.1. DTCCAA not only considers the relationship between topology control and channel allocation but also takes the convergence into consideration during the design process of algorithm for WSN.

4.1 DTCCAA Algorithm

In DTCCAA algorithm, each node in WSN collects the information of other nodes that can be reached. The information includes the transmitting power, channel number and the residual energy. Then the nodes in WSN decide their strategy respectively according to the information collected above. The procedure of the proposed algorithm is given as follows:

  1. Step (1):

    Initialize the power of all nodes in WSN as the max transmitting power and the node channel as the same control channel \(c^{(0)}\);

  2. Step (2):

    \(m=0,\, round=0\);

  3. Step (3):

    the current power of node \(k\) is \(p_{k}=p^{(m)}\,\in A_{k}\) while the current channel is \(c_{k}=c^{(round)}\in C_{k}\);

  4. Step (4):

    the utility value \(u_{k }\) of each node can be obtained according to Eq. (1). Determine whether the power and channel of each node in WSN reaches Nash Equilibrium. That is to say, it will go to step (5) if the utility value of all nodes in WSN is not equal to that in last round. Otherwise, the algorithm terminates;

  5. Step (5):

    \(m=m+1\);

  6. Step (6):

    \(k=1\);

  7. Step (7):

    Determine whether the network connected or not when the transmitting power of node \(k\) is \(p_{k}=p^{(m)}\in A_{k}\): if disconnected, remain the last power and channel of node \(k\) unchanged, i.e. \(p_{k}=p^{(m-1)},\,c_{k}=c^{(round-1)}\); if connected, it would go to step (8);

  8. Step (8):

    The utility of node \(k\) is \(u^{(m)} _{k}=max\left( u_{k}\left( p^{(m)} ,1\right) ,{\ldots },u_{k}\left( p^{(m)},C\right) \right) \) when its power act as \(p_{k}=p^{(m)}\). Now the transmitting power of node \(k\) is \(p^{*}_{k}=argmax\left( u^{(m)} _{k},u^{(m-1)}_{ k}\right) \) while the node channel number is \(c^{*}_{k} =arg\,max(u_{k}(p^{*},1),{\ldots },u_{k}(p^{*},C))\);

  9. Step (9):

    If \(k<n,\,k=k+1\) and the algorithm returns to step (7); If \(k\ge n\), \(round=round+1\) and the algorithm returns to step (3).

In this algorithm, step (1) is the initialization process for WSN. At this moment, every node initializes its transmitting power to \(p_{max}\) and node channel to \(c^{(0)}\). Then each node \(k\) discovers its neighbors by broadcasting neighbor request messages at \(p_{max}\) and collects the responses provided by the receiver \(j\). The respond message includes the transmitting power, channel number and the residual energy of node \(j\). Upon received the messages successfully from the neighbors of node \(k\), the initial topology of our algorithm is obtained.

Next, we assume that the nodes in WSN have complete information about the entirety topology state information (e.g. network connectivity) and only one node can adapt its transmitting power as well as channel number at a time. The procedure from step (3) to step (9) is the iteration of the game and the iterative process allows the network topology to evolve dynamically. In this part, any node \(k\) in WSN firstly chooses the transmitting power level one level lower than its current power level [described as step (5)]. If the network is disconnected, node \(k\) will remain its current power level to ensure the network connectivity [shown in step (7)]. However, if the network is connected at the moment, the node \(k\) would choose the channel number one by one from the set \(C_{k}\) and then calculated the utility for all the status respectively. If the maximum utility after choosing the lower transmitting power level is larger than that of the current transmitting power level, the node \(k\) would choose the lower transmitting power level and the corresponding channel number which can maximize node \(k\)’s utility as its status. Otherwise, the current power and its corresponding channel number that can maximize node \(k\)’s utility will be the state of node \(k\) [described as step (8)].

4.2 The Analysis of Algorithm

The most important feature to an algorithm is the convergence. Because our algorithm will be used to solve the game model mentioned in Sect. 3.1, whether DTCCAA can converge to Nash Equilibrium or not becomes a significant issue. Next, we will give Theorem 3 to testify the convergence.

Theorem 3

the Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) for WSN must converge to Nash Equilibrium.

Every node reduces its power level and chooses the best channel in each round of DTCCAA. Then we can get 3 possible stations as follow.

  1. 1.

    \(p^{new}_{k}\,\ne \, p^{old}_{k}, c^{ new}_{k}= c^{old}_{k}\)

  2. 2.

    \(p^{new}_{k}\,\ne \, p^{old}_{k}, c^{new}_{k}\,\ne \, c^{old}_{k}\)

  3. 3.

    \(p^{new}_{k}= p^{old}_{k}, c^{new}_{k}\,\ne \, c^{old}_{k}\)

It is obvious that \(u_k (new)\ge u_k (old)\Rightarrow \sum \nolimits _{j\in N,j\ne k} {u_j (new)} \ge \sum \nolimits _{j\in N,j\ne k} {u_j (old)} \) in the stations mentioned above. Because the function is monotonic and the choice of power and channel is limited, DTCCAA must converge during the limited rounds.

It can be seen from Theorem 3 that DTCCAA algorithm is able to converge to Nash Equilibrium. But the analysis above can not guarantee that DTCCAA algorithm can converge to the best Nash Equilibrium since one or more Nash Equilibrium can be existed in an Ordinal Potential Game [28]. In WSN, if we can not get to the optimal result, it is still easy to shorten the network lifetime because of the unbalanced energy consumption and the larger network interference. For the sake of achieving the optimal solution for our model, another important concept, named Pareto Optimality, is needed in game theory. The definition of Pareto Optimality is given as follow.

Definition 3

(Pareto Optimality)[29]: A strategy vector \(s^{*}\) is Pareto Optimal if there does not exist a strategy vector \(s\in S\), such that \(u_{i}(s^{*})\le u_{i}(s)\) for any \(i\in N\) and \(u_{j}(s^{*})\le u_{j}(s)\) for at least one \(j\in N\).

Compared to Nash Equilibrium, Pareto Optimality is the best strategy combination of all the Nash Equilibriums. That is to say, Nash Equilibrium can be the local optimum while Pareto Optimality emphasizes the optimum of entirety. Thus, we can say that Nash Equilibrium is not necessarily Pareto optimal, but Pareto optimal must be Nash Equilibrium. In our model for WSN, the Pareto Optimality is wanted to optimize the network and the DTCCAA algorithm is required to converge to Pareto Optimality. We will give the Theorem 4 according to Theorem 3 and Definition 3.

Theorem 4

The Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) for WSN must converge to Pareto Optimality.

Proof

The nodes in WSN can be divided into two types during the DTCCAA: one refers to the nodes with the minimum transmission power level that ensures the network connectivity and the other one is the nodes with non minimum transmit power level. \(\square \)

If the residual energy of a node \(k\) itself is small, the node \(k\) will reduce its transmitting power as small as possible to increase its income. Thus, the power of \(k\) is the minimum transmitting power level that guarantees the network connectivity. If we continue to reduce the power of \(k\) after the algorithm ceases, the network mustn’t connected and the income of \(k\) must be reduced. If the connectivity of WSN is wanted at present, other nodes except \(k\) should increase their power which leads to the decrease of their incomes. When the residual energy of a node \(i\) in wireless sensor network is relatively large, the node \(i\) will keeps a larger power to ensure its own income. Either we reduce the transmitting power of node \(i\) itself or change the station of other nodes, the income of node \(i\) must be decreased.

In summary, there is no node in WSN can increase its own income without decrease other nodes’. Based on Definition 3, the Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) for WSN must converge to Pareto Optimality.

5 Simulation Experiment

In this section, we evaluate the performance of DTCCAA via simulations using MATLAB. The distribution range of the nodes in WSN is \(500\,\hbox {m}\times 500\,\hbox {m}\). Assume the residual energy of all nodes is tally with the Poisson distribution and its probability is 25. In our model, the maximal transmission range of every node is \(d_{max}=150\,\hbox {m}\).

The power threshold refers to the minimum power value that is needed for any node to receive the wireless signal. That is to say, if the power in the receiving terminal is less than \(p_{th}\), the receiving node can not get the signal and the transmitting procedure is failure. So we should ascertain the value of the power threshold.

The power threshold of a node is decided by its nature. At present, the received power threshold of most wireless devices is from \(-\)100dBm to 0dBm. The unit dBm can be changed into the unit mW. And the relationship between them is shown as follow,

$$\begin{aligned} A=10\times \lg \left( P \right) \end{aligned}$$
(16)

Here, the unit of \(A\) is dBm while the unit of \(P\) is mW. Thus, we can choose a class of node whose power threshold is -61dBm. Then according to formulation (16), we can get the power threshold of this class of node is \(7\times 10^{-7}\,\hbox {mW}\), which mean that the power threshold in our paper is \(p_{th}=7\times 10^{-10}\,\hbox {W}\).

5.1 The Analysis of Weight Value

From the utility function, we know that all parameters can be determined by the network structure except the two non negative weight values \(\alpha \) and \(\beta \). When the two weight values change, the performance of WSN will be changed as well. For the sake of getting better network performance, \(\alpha \) and \(\beta \) are wanted to be proper values. In order to ascertain their value, we study the influence of the network performance as the weight value change.

First of all, we place 50 wireless sensor nodes in the \(500\,\hbox {m}\times 500\hbox {m}\) region randomly. Then we assume that \(\beta =1\), the different aspects of topology are only related to the value of \(\alpha \) at this moment. so we do experiment to show the influence of \(\alpha \) on the network performance namely that the average transmission power, the average residual energy of nodes within each node’s transmission range, the average degree of nodes, the average interference of nodes, variance of channels and the average-hop of the shortest path between two nodes. The figures are shown as the Fig. 4.

Fig. 4
figure 4

The performance influence of \(\alpha \) when \(\beta =1\). a Average transmission power. b Average residual energy within node transmission range. c Average node degree. d Average node interference. e Variance of channels. f Average-hop of the shortest path betwen two nodes

Full size image

In Fig. 4, the deep blue line denotes the network performance when \(\alpha =0.05\) and \(\beta =1\) while the pink line denotes the network performance when \(\alpha =0.1\) and \(\beta =1\) (and by this analogy). According to the experiments, we can see that some network performances have presented different rules. As shown in Fig. 4a–d, when \(\beta =1\), the average transmission power, the average residual energy of nodes within each node’s transmission range, the average degree of nodes and the average interference of nodes decrease as \(\alpha \) increases. We can observe from Fig. 4f that the bigger \(\alpha \) is, the larger the average-hop of the shortest path between two nodes is. The law of channel variance is not obvious, but from Fig. 4e, the channel variance of all the \(\alpha \) value is relatively small.

When \(\beta =1\), if \(\alpha =0.05\) or \(\alpha =0.1\), the average transmission power, average interference of nodes and the channel variance is bigger. Thus, the transmission of WSN is of great probability to lose information because of the unbalanced channel allocation and the lifetime of network is cut down owing to the waste of energy. If \(\alpha =5\) or \(\alpha =10\), the average transmission power and average interference, as well as the channel variance is smaller. But the average residual energy of nodes is smaller and the robustness as well as the real-time of network is less nice since the average-hop of the shortest path between two nodes is bigger. If \(\alpha =0.5\), the average interference of nodes is bigger, which leads to the inaccurate transmission of information.

In conclusion, when choosing the weight value as \(\alpha =1\) and \(\beta =1\), the performance on every aspect of network is pretty good. Hence we set \(\alpha =1\) and \(\beta =1\) in the following simulations.

5.2 The Analysis of Topology Structure

We compare the DTCCAA with the combination of the topology control algorithm DIA [9] and the channel allocation algorithm CA [30]. DIA is to minimize the node transmission power while CA is to preserve the network connectivity. We randomly select 50 nodes to place in \(500\,\hbox {m}\times 500\,\hbox {m}\) region for \(\alpha =1\) and \(\beta =1\). When the maximal channel number is 5, the topological structures after running DTCCAA and \(\hbox {DIA}+\hbox {CA}\) are shown in Fig. 5.

Fig. 5
figure 5

Comparison figure of topological structures by the two algorithms. a \(\hbox {DIA}+\hbox {CA}\). b DTCCAA

Full size image

Figure 5a is the topology of algorithm \(\hbox {DIA}+\hbox {CA}\). The nodes with circles are the bottleneck nodes. Here, the bottleneck nodes refer to the isolated nodes which connect the two or more areas. Thus, the bottleneck nodes are more likely to run out of the energy because of the excess of forwarding tasks. From Fig. 5a, too much retransmission tasks can accelerate the death of bottleneck nodes and shorten the lifetime of network due to the fact that DIA does not consider the energy problem. In Fig. 5b, algorithm DTCCAA takes the node’s own residual energy and its neighbor’s into account to reduce the retransmission task of bottleneck nodes. Then DTCCAA balances the transmission path of the wireless information and prolongs the lifetime of WSN through adding the other transmission paths.

5.3 The Analysis of Network Performance

We make the maximal channel number unchanged and vary the total number of nodes in the region \(500\,\hbox {m}\times 500\,\hbox {m}\) from 30 to 50. When the maximal channel number is 5, the comparison of performance analysis between DTCCAA and \(\hbox {DIA}+\hbox {CA}\) is shown as Fig. 6.

Fig. 6
figure 6

Comparison of performances with the increasing of nodes in total. a Average transmission power. b Average node degree. c Average node interference. d Average residual energy within node transmission range. e variance of channels. f average-hop of the shortest path between two nodes

Full size image

From Fig. 6a, b, when the maximal channel number in network remain unchanged, the average transmission power and the average degree of nodes are decreasing as the total number of nodes increase. Besides, the node power is not much bigger than that of DIA, which illustrates that the topology obtained by DTCCAA can reduce node transmission power as well as enhance the network robustness on the basis of ensuring the connectivity. It can be seen from Fig. 6c, d that the topology got by DTCCAA has lower average node interference and bigger average residual energy than that of DIA + CA. In other words, DTCCAA can better reduce interference and balance the network performance as well as prolong the network lifetime. Channel variance represents the equilibrium properties of channels when running an algorithm. The smaller the channel variance is, the more balance the channels are. Figure 6e shows that the channel variance of DTCCAA is smaller than DIA + CA. So it indicates the superiority further. In Fig. 6f, the topology after implementing DTCCAA has a less average-hop of the shortest path between two nodes. Hence, the real-time is much better and it can reduce the energy consumption of nodes from the perspective of the forwarding number.

Then we randomly put 50 nodes in \(500\,\hbox {m}\times 500\,\hbox {m}\) and vary the total number of channel from 4 to 8. The comparison of performance analysis between DTCCAA and DIA + CA is shown as Fig. 7.

Fig. 7
figure 7

Comparison of performances with the increasing of channels in total. a Average transmission power. b Average node degree. c Average node interference. d Average residual energy within node transmission range. e Variance of channels. f Average-hop of the shortest path between two nodes

Full size image

As shown in Fig. 7a, when the total node number in network is invariant, the average power of DTCCAA is slightly bigger than DIA + CA. The average node degree of network is shown as Fig. 7b at the moment. With the increasing of the total channel, the average interference of node in WSN is decreasing and the average interference of DTCCAA is less than DIA + CA clearly shown in Fig. 7c. Figure 7d indicates that DTCCAA can get a larger average residual energy than DIA + CA. Besides, DTCCAA prolongs the lifetime of network. From Fig. 7e, the channel variance of DTCCAA is small and the channel allocation station is nice. In Fig. 7f, the average-hop of the shortest path between two nodes after running DTCCAA is small. It will enhance the real-time and lower the energy consumption brought by retransmission in WSN.

6 Conclusion

According to the characteristics of WSN, we firstly design a game model which fully takes the network interference, connectivity and energy consumption into consideration. The model studies the internal relationship between topology control and channel allocation of WSN and defines a relationship between transmitting power and node residual energy. Then we prove that the model is able to guarantee the existence of Nash Equilibrium. Secondly, we develop a Distributed Topology Control and Channel Allocation Algorithm (DTCCAA) based on the model. The algorithm increases the node income in wireless sensor network by reducing the node transmission power gradually as well as adjusting the node channel. Then it is attested that the algorithm can ensure the network connectivity and converge to the Pareto Optimality. Thirdly, we give the simulation to the algorithm and the results show that DTCCAA can get a topology with low transmitting power and low average interference, which will enhance the communication quality as well as reduce the energy consumption. Besides, DTCCAA balances the energy consumption of every node through selecting different direct neighbors. Thus, the death of network caused by the energy exhaustion of some nodes can be avoided. Moreover, the equilibrium of topology, the final station of channel allocation and the robustness as well as the real-time is properly better than that of DIA + CA no matter how the total number of nodes or channels change.