Algebraic connectivity aided energy-efficient topology control in selfish ad hoc networks

Abstract

Topology control is a technique to assign per-node’s transmit parameters so as to get the network topology with the best possible network performance given some optimization criteria, such as energy-efficient connectivity. In this paper, we investigate energy-efficient topology control for wireless ad-hoc networks in the presence of selfish nodes. A non-cooperative game aided topology control approach is developed for minimizing the potential transmit power, whilst maintaining the network connectivity. The utility function is conceived by virtue of algebraic connectivity, which is a fine metric to measure the connectivity redundancy of a network. We prove the existence of Nash Equilibrium (NE) and demonstrate that the NE is Pareto optimal as well. Specifically, two fully distributed topology controls—algebraic connectivity-based Max-Improvement (ACMI) algorithm and $\delta$-Improvement (ACDI) algorithm—are proposed to find the NE topologies. Both ACMI and ACDI can easily construct the stable topologies with a low information-overhead of the order O(n), where n is the number of nodes. Simulations demonstrate that our algorithms observably eliminate the redundancy of the maximum power topology and embrace several other attractive topological features.

1 Introduction

Topology control becomes a prevalent technique to assign per-node’s transmit parameters, such that the topology has the best possible network performance, such as energy-efficient connectivity. It plays an important role in managing the complexity of large-scale systems through self-organizing capabilities. Involving selfish nodes whose actions are to optimize their own objectives, topology control then turns into an intractable topic. A challenge of topology design is that individual nodes selfishly act in their self-interests with having access to local network information, whereas the objective to guarantee the energy-efficient connectivity is typically a global property of the network.

Up to now, various topology control approaches have been proposed to construct energy-efficiently connected topologies, such as relay region method [1], localized minimum spanning tree [2], directed local spanning subgraph [3]. A comprehensive survey of topology control can be found in [4, 5]. However, these schemes are based on a hidden assumption that network nodes are altruistic, and they cooperate faithfully with each other to achieve the desired global objective. Actually, this assumption does not hold in general, since network nodes in most scenarios act selfishly and are competing with each other in pursuit of both energy-efficiency and network connectivity. It is intuitive that the actions of a node, in response to other nodes’ actions, would focus on minimizing its individual energy consumption in constructing a connected network, perhaps at the sacrifice of some other nodes’, or even the whole network’s, resources. Game theory provides a powerful tool to describe the phenomenon of competition and cooperation between intelligent rational decision-makers [6, 7]. The research efforts to address topology control in the presence of selfish nodes have been firstly made in [8]. Komali et al. [9, 10] formulated the topology control as non-cooperative potential games, which guarantee the existence of at least one Nash Equilibrium (NE). However, the game-based approaches in [9] require excessively large information-overhead, and the approach in [10], due to the fact that all nodes’ preferences are maintaining the number of their k-hop neighbors¹, is low efficient for nodes to adapt the power levels when $k>1$, and even unfeasible for $k=1$.

The focus of our work is on distributed topological decision from each selfish node’s perspective with the network-wide goal to minimize the potential transmit powers at nodes, whilst maintaining the connectivity of the network. To this end, we investigate an energy-efficient topology control for wireless selfish ad hoc networks with the aid of the non-cooperative game approach. The work in this paper is inspired by some of the contributions in [9]. We conceive a more practical utility function, which characterizes the real interests of nodes in pursuit of both energy-efficiency and network connectivity by virtue of the algebraic connectivity. The existence of NE is proved in our theoretic analysis. The features of the algebraic connectivity allow us to design two fully distributed topology control algorithms—algebraic connectivity-based Max-Improvement (ACMI) algorithm and $\delta$-Improvement (ACDI) algorithm—for iterating elegant solutions, i.e., energy-efficient network topologies. Simulations demonstrate that our algorithms also capture the tradeoffs between energy efficiency and connectivity redundancy, which is flexible for the network design.

The rest of the paper is organized as follows: in Sect. 2, we introduce some preliminaries including the key concepts and properties of game theory and algebraic connectivity theory. Section 3 presents our system model, assumptions and definitions. The game formulation and theoretic analysis are provided in Sect. 4 and the game-based TC algorithms are proposed in Sect. 5. We conduct some simulations to illustrate our algorithms in Sect. 6, and conclude the paper in Sect. 7.

2 Preliminaries

In this section, we present a brief overview of important concepts together with the lemmas of the non-cooperative game theory as well as the algebraic connectivity theory.

2.1 Non-cooperative game theory

Non-cooperative game theory provides analytical tools and techniques to analyze interactive decision making situation. A formal representation of non-cooperative game is given by $\varGamma =\langle {\mathcal {N}},{\mathcal {S}},\{u_i\}\rangle$, where ${\mathcal {N}}=\{1,2,\ldots ,n\}$ is the set of players with n the number of players in the game, ${\mathcal {S}}={\mathcal {S}}_1\times {\mathcal {S}}_2\times \cdots \times {\mathcal {S}}_n$ is the Cartesian product of the strategy sets ${\mathcal {S}}_i$ for all $i\in {\mathcal {N}}$, and $u_i$ is the utility function $u_i:{\mathcal {S}}\rightarrow {\mathbb {R}}$ (${\mathbb {R}}$ is the set of real numbers) that the ith player desires to maximize. For each player i, the utility function is not only dependent on the strategy $s_i\in {\mathcal {S}}_i$ that it has selected, but also the decisions made by other players, represented by $s_{-i}$. Define the best response of a player as a strategy that maximizes its utility function for some given strategies of the other players. Mathematically, the strategy $s_i$ is said to be the best response to some fixed $s_{-i}$, if it satisfies the following inequality

$$\begin{aligned} u_i (s_i,s_{-i})\ge u_i (s_i^{\prime },s_{-i}),\,\forall s_i^{\prime }i\in {\mathcal {S}}_i. \end{aligned}$$

(1)

A desired stable solution in non-cooperative game theory is Nash Equilibrium in which no player may improve its utility function by unilaterally deviating from it.

Definition 1

A strategy tuple $\mathbf{s }^*=(s_{1}^{*},s_{2}^{*},\ldots ,s_{n}^{*})$ is a Nash Equilibrium, if $s_i^*$ is the best response to $s_{-i}^{*}$ for every player i. Formally, the strategy tuple $\mathbf{s }^*$ is an NE if $u_i(\mathbf{s }^*)\ge u_i(s_i,s_{-i}^{*})$ for $\forall i\in {\mathcal {N}}$ and $\forall s_i\in {\mathcal {S}}_i$.

A game may possess a large amount of NEs or none at all. Thus, it is of interest to design the utility function in a way such that the game has at least one NE point. Fortunately, a kind of games called potential games with compact strategy spaces are known to possess at least one NE [11].

Definition 2

A strategic game $\varGamma =\langle {\mathcal {N}},{\mathcal {S}},\{u_i\}\rangle$ is an ordinal potential game (OPG) if there exists a function $V:{\mathcal {S}}\rightarrow {\mathbb {R}}$ such that $\forall i\in {\mathcal {N}},\,\forall p_{-i}\in {\mathcal {S}}_{-i}$, and for all $p_i, q_i\in {\mathcal {S}}_i$

$$\begin{aligned}&V(p_i,p_{-i})-V(q_i,p_{-i})>0\Leftrightarrow \\&u_i(p_i,p_{-i})-u_i(q_i,p_{-i})>0. \end{aligned}$$

V is called the ordinal potential function (OPF) of $\varGamma$ in the following.

The following lemma (see [11] for the proof) establishes how NE points of the game can be identified:

Lemma 1

Let $\varGamma$ be an OPG and V be its corresponding OPF. If $\mathbf{p }\in {\mathcal {S}}$ maximizes V, then it is an NE.

Thus, potential function maximizers form a subset of the NE of a potential game.

Another interesting concept is Pareto optimal: if there is no other outcomes that make every player at least at well off while making at least one player better off. Mathematically, we say that a strategy tuple $\mathbf{p }=(p_1,p_2,\ldots ,p_n)$ is Pareto optimal if and only if there exists no other strategy tuple $\mathbf{q }=(q_1,q_2,\ldots ,q_n)$ such that $u_i(\mathbf{q })\ge u_i(\mathbf{p })$ for $\forall i\in {\mathcal {N}}$ and for some $k\in {\mathcal {N}}$, $u_k(\mathbf{q })>u_k(\mathbf{p })$.

2.2 Algebraic connectivity theory

In this subsection, we summarize some key notations from the field of algebraic connectivity theory based on which the nodes can learn some crucial knowledge about the network topology or its topology-related properties. Let ${\mathcal {G}}({\mathcal {V}},{\mathcal {E}})$ be an undirected graph, where ${\mathcal {V}}=\{1,2,\ldots ,n\}$ denotes the set of nodes and ${\mathcal {E}}\subset {\mathcal {V}}\times {\mathcal {V}}$ is the link set. A graph is said to be connected, if for every pair of nodes, there exists a path—a collection of contiguous links—between them. The structure of the graph can be described by a symmetric $n\times n$ adjacency matrix $A=(a_{ij})$, whose entries $a_{ij}$ are either one or zero, depending on whether there is a link between nodes i and j or not. Let ${\mathcal {N}}_i$ be the neighboring nodes (or neighbors) of node i, i.e., the set of nodes that can directly exchange information with node i. The degree matrix of the graph is a diagonal matrix defined as

$$\begin{aligned} D={\text{diag}}\left( \left\{ |{\mathcal {N}}_1|,|{\mathcal {N}}_2|,\ldots ,|{\mathcal {N}}_n|\right\} \right) , \end{aligned}$$

where $|{\mathcal {N}}_i|$ is the degree of node i, i.e., $|{\mathcal {N}}_i|=\sum_{j=1}^{n}a_{ij}$. The matrix $L=D-A$ is called the Laplacian matrix. All eigenvalues of L are called the Laplacian eigenvalues that can be arranged in an increasing order

$$\begin{aligned} \lambda_1\le \lambda_2\le \cdots \le \lambda_n. \end{aligned}$$

The Laplacian matrix L is an important matrix in graph theory with several interesting properties. It is a symmetric positive semi-definite matrix, and by definition it has a zero eigenvalue $\lambda_1=0$. The multiplicity of the value 0 as an eigenvalue of L is equal to the number of connected components of ${\mathcal {G}}$. Consequently, $\lambda_2=\lambda_2({\mathcal {G}})$ is strictly greater than 0 if and only if ${\mathcal {G}}$ is a connected graph. The quantity $\lambda_2$ is known as the algebraic connectivity of the graph.

The features of algebraic connectivity have been exploited to make certain topology-related decisions, such as consensus problem [12], backbone network construction [13], base station or cluster head selection [14] and connectivity maintenance [15]. Some basic characteristics of algebraic connectivity which can be found in [16, 17] are stated here.

Lemma 2

For ${\mathcal {G}}_1({\mathcal {V}},{\mathcal {E}}_1)$ and ${\mathcal {G}}_2({\mathcal {V}},{\mathcal {E}}_2)$, if ${\mathcal {E}}_1\subset {\mathcal {E}}_2$, i.e., ${\mathcal {G}}_1$ is obtained from ${\mathcal {G}}_2$ by deleting some edges, we have $\lambda_2({\mathcal {G}}_1)\le \lambda_2({\mathcal {G}}_2)$.

Lemma 3

For any undirected graph ${\mathcal {G}}$, the value of algebraic connectivity $\lambda_2({\mathcal {G}})$ is upper bounded by the node connectivity, which is equal to the minimum number of nodes whose deletion from ${\mathcal {G}}$ causes the graph to be disconnected.

As the algebraic connectivity $\lambda_2({\mathcal {G}})$ does not drop when the number of links increases from Lemma 2, and it has a continuous value as well as a closely relationship with the conventional connectivity measure, it could serve as a fine metric to measure the connectivity redundancy of network ${\mathcal {G}}$. In this paper we propose to use the algebraic connectivity as a parameter to provide a methodology for topology control.

3 System model

Consider an ad hoc network ${\mathcal {G}}({\mathcal {V}},{\mathcal {E}})$, where ${\mathcal {V}}$ denotes the set of nodes and ${\mathcal {E}}$ is the set of links connecting nodes together. In order to communicate with node j, node i should use a transmit power $p_{i}$, such that the received signal strength at j is above a threshold. That is, when a packet is transmitted by node i at transmit power $p_{i}$, it can be detected and correctly decoded if the received power by node j is greater than a common signal capture threshold pth

$$\begin{aligned} p_{i}\cdot G_{ij}\ge p^{th}, \end{aligned}$$

(2)

where $G_{ij}$ is the propagation factor which depends on the propagation channel model, including the antenna gains at both i and j, the distance between two nodes and the path loss factor. We assume that $G_{ij}$ is a symmetric function, i.e., $G_{ij}=G_{ji}$. In the free space propagation model, as an example, the propagation factor $G_{ij}$ from node i to j should be satisfied $G_{ij}=Cd_{ij}^{-\alpha }$, where C is a constant, $d_{ij}$ is the distance between nodes i and j, and $\alpha$ is the path loss factor typically in the range $2\le \alpha \le 6$. We do not consider unidirectional links, given that the vast majority of channel access and routing protocols use only bidirectional links for their operations. Hence, we refer to undirected graph for the rest of this paper, that is, all links in the network ${\mathcal {G}}$ are bidirectional. Mathematically, a bidirectional link $e_{ij}\in {\mathcal {E}}$ between nodes i and j exists if and only if

$$\begin{aligned} \min \{p_{i},p_{j}\}\ge p^{th}/G_{ij}. \end{aligned}$$

We denote $w(i,j)\triangleq p^{th}/G_{ij}$ the minimum transmit power which supports a connection from node i to j. Clearly, we have $w(i,j)=w(j,i)$.

Let $p_{i}^{\max }$ be the maximum power value that can be used by node i to transmit packets. We define the maximum power network ${\mathcal {G}}_{\max }({\mathcal {V}},{\mathcal {E}}_{\max })$ which is induced all nodes transmitting at their maximum powers as

$$\begin{aligned} {\mathcal {E}}_{\max }=\left\{ e_{ij}|\mathbf{p }=\left( p_{1}^{\max },\ldots ,p_{n}^{\max }\right) \right\} . \end{aligned}$$

We assume that ${\mathcal {G}}_{\max }$ is a connected network with amount of superfluous links. If so, it is necessary to introduce topology control for constructing an energy-efficiently connected network.

4 Game formulation and analysis

4.1 Game formulation

Nodes in a wireless network are envisioned to be endowed with some autonomic functions, such as regulating their transmit powers, for network operation according to their self-interests. We focus our attention on topology control from each individual node’s perspective in which nodes act selfishly to minimize their own energy consumption in constructing a connected network. Each node’s power regulation could potentially affect the performance of the other nodes and thereby influence their decisions. Figure 1 sketches the interaction among three nodes in the topology control process. In this example, these three nodes constituting a network in Fig. 1a can communicate with each other directly. In Fig. 1b, as node B decreases its power level and breaks the link $e_{AB}$ with node A selfishly, nodes A and C cannot lower their power levels further without disconnecting the network.

Fig. 1

Example of the interaction among nodes in topology control process

In such a scenario, we formally describe the topology control process as a noncooperative game $\varGamma =\langle {\mathcal {V}},{\mathcal {S}},\{u_i\}\rangle$, where individual nodes form the player set ${\mathcal {V}}$. For node $i\in {\mathcal {V}}$, the transmit power $p_i\in {\mathcal {S}}_i$ is regarded as its strategy. Then the individual powers can be collected into a power vector $\mathbf{p }=(p_1,p_2,\ldots ,p_n)$, called power profile, which forms the strategy space ${\mathcal {S}}$ for the game. The strategy space ${\mathcal {S}}$ can be also obtained by the Cartesian product of all ${\mathcal {S}}_i\,(1\le i\le n)$, where ${\mathcal {S}}_i=[0,p_{i}^{\max }]$ is the set of powers that can be selected by node i. Each power profile $\mathbf{p }$ induces a topology graph ${\mathcal {G}}_{\mathbf{p }}({\mathcal {V}}, {\mathcal {E}}_{\mathbf{p }})$. Obviously, we have ${\mathcal {E}}_{\mathbf{p }}\subset {\mathcal {E}}_{\max }$.

Every node can benefit from connecting to other nodes in network ${\mathcal {G}}$, such as deliver a service packet, but it also incurs an energy cost in the establishment of ${\mathcal {G}}$. Each node’s preference can be represented by a utility function

$$\begin{aligned} u_i(\mathbf{p })=\varphi_i({\mathcal {G}}_{\mathbf{p }}) -c_i({\mathcal {G}}_{\mathbf{p }}), \end{aligned}$$

(3)

where $\varphi_i$ represents the benefit that node i derives from the network ${\mathcal {G}}_{\mathbf{p }}$, and $c_i$ is the energy consumption of node i for the efforts to construct such a network ${\mathcal {G}}_{\mathbf{p }}$. Let $\lambda_2({\mathcal {G}}_{\mathbf{p }})$ denote the algebraic connectivity of the topology graph ${\mathcal {G}}_{\mathbf{p }}$. Note that the network is connected if and only if $\lambda_2({\mathcal {G}}_{\mathbf{p }})>0$. We define a specific utility function by

$$\begin{aligned} u_i(\mathbf{p })=M_i h_{\varLambda }(\mathbf{p })-p_i, \end{aligned}$$

(4)

where $h_{\varLambda }(\mathbf{p })$ is the characteristic function of strategy profile set $\varLambda =\{\mathbf{p }:\lambda_2({\mathcal {G}}_{\mathbf{p }})\ge \epsilon \}$ with $\epsilon$ a parameter which indicates the connectivity redundancy of network ${\mathcal {G}}_{\mathbf{p }}$. Here, we assume that node i can receive a fixed benefit $M_i>p_{i}^{\max }$ if the network is connected, and zero revenue if the network loses connectivity. The transmit power $p_i$ is regarded as the primary source of energy consumption for each node i. This function captures the fact that nodes regulate their power levels to ensure the network connectivity as a top priority, but they would use the minimum power to maintain such a connectivity. From [17], a theoretical lower bound of the algebraic connectivity for a connected network is given by $\lambda_2\ge 2(1-\cos (\pi /n))$. Therefore, if $\epsilon =2(1-\cos (\pi /n))$, the network nodes with their utility functions try to maintain the minimum connectivity with approximate tree structures. Additionally, by adjusting the parameter $\epsilon$ adaptively, we can also get the tradeoffs between energy-efficiency and connectivity redundancy.

In our model, node selfishness is associated with its preference to minimize its energy consumption in constructing a connected network, but not to other factors, e.g., for determining the packet forwarding. It is noteworthy that a selfish node is actually interested in the connectivity with its destination nodes rather than that of the whole network. However, as the network connectivity is a fundamental property for network-wide operation, such as broadcasting for routing discovery, all network nodes should collaboratively achieve the global network connectivity. From this perspective, the received fixed benefit $M_i$ for node i can also be understood as a stimulation provided by the network manager. The effect of the selfishness at routing decision is beyond the scope of this work and will be reserved for the future work.

4.2 Game-theoretic analysis

With the strategy set and utility function defined, a game is played by all nodes picking their individual powers. NE network topologies in which no node has incentive to unilaterally change its power, are desirable, because they are stable solutions of the game. We show that the game $\varGamma =\langle {\mathcal {V}},{\mathcal {S}},\{u_i\}\rangle$ with the utility function of each node given by (4) is an ordinal potential game, then the existence of NEs is guaranteed.

Theorem 1

The game $\varGamma =\langle {\mathcal {V}},{\mathcal {S}},\{u_i\}\rangle$ is an ordinal potential game. The ordinal potential function is given by

$$\begin{aligned} V(\mathbf{p })= Mh_{\varLambda }(\mathbf{p })-\sum \limits_{i=1}^{n}p_i \end{aligned}$$

(5)

where $M=\max \{M_1,M_2,\ldots ,M_n\}$.

Proof

This proof is processed according to the definition of OPG. For each sensor $i\in {\mathcal {V}},\, p_{-i}\in {\mathcal {S}}_{-i}$ and $p_i,q_i\in {\mathcal {S}}_i$, let $p_i>q_i$. From the property of algebraic connectivity, we immediately know $\lambda_2({\mathcal {G}}_{(p_i,p_{-i})})\ge \lambda_2({\mathcal {G}}_{(q_i,p_{-i})})$. Firstly, the difference in sensor i’s utility is

$$\begin{aligned} \varDelta u_i= & {} u(p_i,p_{-i})-u(q_i,p_{-i})\\= & {} M_i(h_{\varLambda }(p_i,p_{-i})-h_{\varLambda }(q_i,p_{-i}))-(p_i-q_i) \end{aligned}$$

Similarly,

$$\begin{aligned} \varDelta V= & {} V(p_i,p_{-i})-V(q_i,p_{-i})\\= & {} M(h_{\varLambda }(p_i,p_{-i})-h_{\varLambda }(q_i,p_{-i}))-(p_i-q_i) \end{aligned}$$

It is not difficult to calculate that the difference $h_{\varLambda }(p_i,p_{-i})-h_{\varLambda }(q_i,p_{-i})$ is equal to 1 if $(p_i,p_{-i})\in \varLambda ,(q_i,p_{-i})\notin \varLambda$, and 0, otherwise. By the fact $M\ge M_i>p_{i}^{\max }$ and our assumption $p_i>q_i$, we have

$$\varDelta u_i\,({\text{or}}\,\varDelta V) \left\{ \begin{array}{ll} < 0 &\quad {\text{if}}\,\,(p_i,p_{-i})\in \varLambda ,(q_i,p_{-i})\in \varLambda ,\\ < 0 &\quad {\text{if}}\,\,(p_i,p_{-i})\notin \varLambda ,(q_i,p_{-i})\notin \varLambda ,\\ > 0 & \quad {\text{if}}\,\,(p_i,p_{-i})\in \varLambda ,(q_i,p_{-i})\notin \varLambda . \end{array}\right.$$

Therefore, the game $\varGamma =\langle {\mathcal {V}},{\mathcal {S}},\{u_i\}\rangle$ is an OPG and V is the OPF. $\square$

Theorem 2

The NE $\mathbf{p }$ is Pareto optimal, if the network ${\mathcal {G}}_{\mathbf{p }}$ is connected.

Proof

Let $\mathbf{p }$ be an NE point and ${\mathcal {G}}_{\mathbf{p }}$ be connected. We assume $\mathbf{p }$ is not a Pareto optimal, there exists another power profile $\mathbf{q }=(q_1,\ldots ,q_n)$ such that $u_i(\mathbf{q })\ge u_i(\mathbf{p })$ for $\forall i\in {\mathcal {V}}$ and for some $k\in {\mathcal {V}},\,u_k(\mathbf{q })>u_k(\mathbf{p })$, i.e., $q_i\le p_i$ for $\forall i\in {\mathcal {V}}$ and for some $k\in {\mathcal {V}},\,q_k<p_k$. The reduction from $p_k$ to $q_k$ for any node k leads to a disconnected network topology. Otherwise, the profile $\mathbf{p }$ is not an NE. This is a contradiction. $\square$

5 Game-based topology control

Since the topology control game is an ordinal potential game, both the best response and the better response converge to NE points [11]. Based on our game, we propose two adaptation algorithms for topology control, ACMI and ACDI. Ideally, each node is capable of making decision about its operational parameter autonomously and in place without recourse to any knowledge of the nodes which cannot be seen, i.e., which are outside its neighbors. By confining the domain of information exchange, less control signaling is flooded through the network which makes the algorithms practical. Therefore, we assume that each node is only aware of local topological information about its neighbors. Both ACMI and ACDI which only depend on the neighboring connectivity information are consist of two phases: information collection phase and non-cooperative game phase.

5.1 Information collection phase

Each node in distributed topology control algorithm making topological decision needs to collect some topology-related information. In ACMI and ACDI, the information needed by node i in topology control process are the local topology ${\mathcal {G}}_i=({\mathcal {V}}_i,{\mathcal {E}}_i)$, which is an induced subgraph of ${\mathcal {G}}$ with ${\mathcal {V}}_i={\mathcal {N}}_i\cup \{i\}$, and the minimum transmit power w(j, k) for all links $e_{jk}\in {\mathcal {E}}_i$ $(j,k\in {\mathcal {V}}_i)$.

To obtain these decision-information, node i initializes its transmit power with the maximum power $p_{i}^{\max }$ and discovers its neighbors ${\mathcal {N}}_i$ by broadcasting “Neighbor Request Message” and collecting the responses provided by the receivers at $p_{j}^{\max }$. Upon successful reception of ACK from each responding neighbor j, node i adds neighbor j and w(i, j) into its neighbor list. Here the minimum transmit power w(i, j) required to establish link connection by node i with its each neighbor j can be determined by measuring the received power of request (and/or reply) messages [2]. Then node i broadcasts “Neighbor List Request Message” at $p_{i}^{\max }$ to get the connectivity relationship and the minimum transmit power between its any two neighbors. Based on the collected neighbor lists, node i can figure out the local topology ${\mathcal {G}}_i$ described by a adjacent matrix $A_i$ and the minimum transmit power w(k, j) for each link $e_{kj}\in {\mathcal {E}}_i$ $(j,k\in {\mathcal {V}}_i)$.

5.2 Non-cooperative game phase

In non-cooperative game phase, node i initiates with the maximum power topology ${\mathcal {G}}_{\max }$ and then try to update this topology in an iterative manner according to a greedy best response process and a restrained better response process, which result in ACMI and ACDI, respectively. The procedures of ACMI and ACDI at node i are given in Algorithm 1 and 2.

5.2.1 ACMI

In ACMI, when node i has a chance to revise its transmit power, it chooses a power level which maximizes its utility function (4), as shown in line 5 in Algorithm 1. Owing to the limited horizon, node i could not calculated its utility accurately. Let $p_{-i}$ denote the powers of node i’s neighbors, as distinct from that of all the remaining nodes in utility (4), and $\lambda_2$ similarly denote the algebraic connectivity of the subgraph ${\mathcal {G}}_i$. By redefining the power profile $\mathbf{p }=(p_i,p_{-i})$, the utility of node i could be estimated. According to the minimum powers required to establish links between node i and its neighbors, node i knows which links are removed when it hears the new power settings of its neighbors, and then updates ${\mathcal {G}}_i$. Note that the update of ${\mathcal {G}}_i$ also contains the deletion of node i’s neighbors. If one neighbor of node i, denoted by node j, updates its power setting, one special case may appear: the path from node j to i may include one node k which is node j’s neighbor but not node i’s. In this case, the local topology ${\mathcal {G}}_i$ is not connected, as it does not contain the node k. Therefore, to avoid appearing this case, node i should remove this neighbor j for further power adjustment. The random wait time t is to avoid two adjacent nodes updating their local topologies simultaneously. Two feasible approaches could be used to choose the wait time for node i: multiplying i (for simplicity, i also refers to node i’ ID) by a constant unit time which results in an ordinal update; taking graph coloring technique and assigning a wait time for node i according to its color.

5.2.2 ACDI

In ACDI, at the time that node i updates its transmit power, it may choose a power level one step lower than its current level if the chosen power gives a better payoff than its current power, as shown in line 7 in Algorithm 2. The strategy set ${\mathcal {S}}_{i}$ of node i is discretized by the following descending order set

$$\begin{aligned} {\mathcal {S}}_{i}=\left\{ p_{i}^{\max }=p_{i}^{(1)},p_{i}^{(2)},\ldots ,p_{i}^{(\eta )}=0\right\} . \end{aligned}$$

We confine the step size $\delta$ as the power adaptation from $p_{i}^{(m)}$ to $p_{i}^{(m+1)}$ is sufficiently small such that at most one link is dropped. Clearly, there are total $\eta =\lceil p_{i}^{\max }/\delta \rceil +1$ strategy selections in the set ${\mathcal {S}}_{i}$. The definition of $p_{-i}$ and the update of ${\mathcal {G}}_i$ in ACDI are identical with those in ACMI. The constraint of the counter $m_i$ in the first if loop ensures that all node i’s neighbors can have a chance to update their power settings in the $m_i$th iteration. Algorithm 2 is terminated if no power level can be chosen by node i to further reduce its transmit power without dropping the connectivity of ${\mathcal {G}}_i$. If node i’s NE is achieved, we assign infinity to $m_i$, such that its neighbors $j\in {\mathcal {N}}_i$ can continue to update. It should be noted that, the update of the local topology ${\mathcal {G}}_i$ may force its current power (not an NE) into an NE point, since maintaining connectivity is always the best response for all nodes.

5.3 Algorithm analysis

Theorem 3

ACMI converges to a stable topology in exactly one round, i.e., each node updates once; ACDI converges to a stable topology no more than $\eta$ rounds.

Proof

The maximum power topology ${\mathcal {G}}_{\max }$ is assumed to be connected, a positive utility $u_i$ could be obtained in this topology for each node i. In the implementations of both ACMI and ACDI, no node has incentive to reduce its transmit power with disconnecting the local topology ${\mathcal {G}}_i$ due to its limited connectivity information. Otherwise, these decision-makers may regard negatives as their utilities in a disconnected local network. ACMI at each node i sets the minimum power $p_i^*$ without disconnected ${\mathcal {G}}_i$. After the first round, the utility of each node i is $u_i(\mathbf{p }^*)=M_i-p_i^*$. In the second round, no player can set a power $p_i$ further lower than its current power $p_i^*$ without disconnected ${\mathcal {G}}_i$. Otherwise, $p_i$ is the best response in the first round. In each iteration of ACDI for node i, there are total $\eta$ strategies and it will not increase its transmit power in a connected ${\mathcal {G}}_i$. Therefore, the convergence of ACDI is no more than $\eta$ rounds. $\square$

Theorem 4

The topologies derived under ACMI and ACDI maintain the connectivity of ${\mathcal {G}}_{\max }$, i.e., if ${\mathcal {G}}_{\max }$ is connected, the derived topologies are connected.

Proof

If ${\mathcal {G}}_{\max }$ is connected, the derived topology in which each node i can reach all its initial neighbors (i.e., $\forall j\in {\mathcal {N}}_i$) preserves the connectivity of ${\mathcal {G}}_{\max }$. This state can be easily verified by contradiction. Thus, it is sufficient to prove that, in the derived topology (by ACMI or ACDI), each node i keeps the connectivity with its initial neighbors. If node i does not delete its neighbor $j\in {\mathcal {N}}_i$ in its topology update stage, the power adaptation of node i could not disconnect with j in terms of $\lambda_2({\mathcal {G}}_i)>\epsilon$. If a neighbor $j\in {\mathcal {N}}_i$ is deleted by node i, according to the deletion rule, a path from j to i denoted by $j=w_0,w_1,\ldots ,w_m=i$ is existed. In this path, there exists a node $k=w_l$ (the subscript l may be $1,2\ldots$ or $m-2$), such that $k\in {\mathcal {N}}_j$ but $k\notin {\mathcal {N}}_i$, and the nodes after k, i.e., $w_{l+1},\ldots ,w_{m-1}$, belongs to ${\mathcal {N}}_i$. Since node i updating its local topology keeps the connectivity with the nodes $w_{l+1},\ldots ,w_{m-1}$, the node pair (i, j) still connects with each other, and the path is $j=w_0,\ldots ,k=w_l,w_{l+1},w_{l+2}^{\prime },\ldots ,w_{m-1}^{\prime },w_m=i$, with $w_{l+2}^{\prime },\ldots ,w_{m-1}^{\prime }\in {\mathcal {N}}_i$. Therefore, the topologies derived under both local ACMI and ACDI maintain the connectivity of ${\mathcal {G}}_{\max }$. $\square$

If $\lambda_2({\mathcal {G}}_{\max })>0$, and each node i updates its local topology satisfying $\lambda_2({\mathcal {G}}_{i})>0$, the resulting topology ${\mathcal {G}}$ satisfies $\lambda_2({\mathcal {G}})>0$. This features of the algebraic connectivity provide us a methodology to design fully distributed topology control algorithms. Our topology control algorithms only using neighboring information incur less information-overhead in constructing the network. Actually, the information-overhead in the information collection phase is O(n) to get the neighboring information. The worst cases of the information-overheads in ACMI and ACDI to broadcast the updates are O(n) and $\eta \cdot O(n)$, respectively. Accordingly, in both ACMI and ACDI, the total information-overhead is on the order of O(n), where n is the number of nodes. Compared against the topology control algorithms in [9] which require larger information-overhead on the order of $O(n^2)$, our algorithms have excellent scalabilities. Additionally, our algorithms not only derive the network topologies with the minimum connectivity, but also can generate the network topologies with certain desired connectivity redundancy by adjusting parameter $\epsilon$ adaptively.

Fig. 2

Various performance metrics versus connectivity parameter $\epsilon$. a Transmit power, b node degree, c path length

6 Simulation results

In this section, computer simulations are provided to illustrate the proposed algorithms. Nodes are randomly distributed in a $500\times 500\,{\text{m}}^2$ region in the simulation. The maximum transmit power is $p^{\max }=160$ mW for all of the nodes and the step size $\delta$ for power adaptation in ACDI is set as $\delta =4$ mW. The minimum power w(i, j) required to ensure the link ‘on’ denotes as $w(i,j)=C d_{ij}^2$, where $d_{ij}$ is the distance between nodes i and j, $C=p^{th}(4\pi )^2f^2/c^2$ is a constant with the signal capture threshold $p^{th}=7\times 10^{-10}$ W, the carrier frequency $f=2.5$ GHz and the light velocity $c=3\times 10^8$ m/s [2]. Due to the one-to-one mapping relationship between the transmit range and the transmit power, these two terms are used interchangeably hereafter.

6.1 Analysis of connectivity parameter $\epsilon$

In order to investigate the impact of connectivity parameter $\epsilon$ on network performances, we execute ACMI and ACDI for 100 different topology scenarios with 50 nodes. If the randomly generated network ${\mathcal {G}}_{\max }$ is disconnected, it would be discarded. We use the following metrics which are important to evaluate the performance of topology control algorithms:

• 1. Transmit power (range): it reflects the energy consumption and the interference of the network. A smaller transmit power implies lower energy consumption and better network spatial reuse.

• 2. Node degree: it reflects the redundancy of a topology. A higher node degree usually means more contention and collision. Therefore, topology control attempt to achieve a small average node degree.

• 3. Path length: it refers to the hop-distance of the shortest path between two nodes. A larger path length implies a more energy-efficient routing.

The variations of average transmit power, node degree, and path length with different connectivity parameter $\epsilon$ are shown in Fig. 2a–c, respectively. Obviously, ACDI is superior to ACMI in terms of energy-efficiency. An interesting observation is that, these performance metrics by ACDI increase almost linearly as the connectivity parameter $\epsilon$ increases. This is, to some extent, because the algebraic connectivity has a continuous value and is not too sensitive to a small change of the network. Therefore, our algorithms can derive the network topologies with certain desired connectivity redundancy by adjusting parameter $\epsilon$ adaptively.

Fig. 3

Network topologies derived under different algorithms. a MIA, b ACMI with $\epsilon =0.1$, c ACMI with $\epsilon =0.3$, d DIA, e ACDI with $\epsilon =0.1$, f ACDI with $\epsilon =0.3$

6.2 Results of the topology control algorithms

Consider 50 nodes randomly deployed in the simulation region. We compare the topologies derived by our fully distributed algorithms to these by MIA and DIA in [9]. Both ACMI and ACDI are implemented based on two different values of the connectivity parameter $\epsilon$, that is, $\epsilon =0.1$ (trying to obtain the minimum connectivity) and 0.3 (to get a tradeoff between energy-efficiency and connectivity redundancy). The topologies generated by these algorithms are shown in Fig. 3a–f, respectively. In the topologies by the best response algorithms (MIA and ACMI), some particular nodes (such as 28, 37) influenced by their implement orders, still transmit at exorbitant powers (i.e., with large transmit ranges). As expected, the topologies by the better response algorithms (DIA and ACDI) are much better than those by the best response algorithms, as the phenomenon for some nodes transmitting with large ranges is mitigated. Since nodes do not have the connectivity information outside of the neighbors in our algorithms, the topologies by ACMI and ACDI with $\epsilon =0.1$ contain some big circles. Additionally, the increase of connectivity parameter $\epsilon$ results in more connectivity redundancy.

Fig. 4

Various performance metrics versus number of nodes. a Transmit power, b node degree, c path length, d number of information exchange

6.3 Performance evaluation of the topology control algorithms

In this simulation, we vary the number of nodes in the region from 30 to 80 to change the node density. The results of all parameters are averaged over 100 trials. The implementations of ACMI and ACDI are based on the connectivity parameter $\epsilon =0.1$, which may result in the minimum transmit power. MIA and DIA are used as benchmarks to illustrate that our fully distributed algorithms do not have much degradation in energy-efficiency, but reduce the information-overhead significantly. Therefore, another performance metric, information-overhead which refers to the number of information exchange, is added in the performance evaluation, for a smaller number of information exchange means the topology control algorithm more practical. The average transmit power in the topologies generated by MIA, DIA, ACMI and ACDI is shown in Fig. 4a. The average transmit power derived under these algorithms decreases gradually as the number of nodes increases. Due to the limited topological decision information, the proposed algorithms have a minor degradation in energy-efficiency in contrast to the topologies by MIA and DIA. Especially, there are no more than $10\%$ excess of the average transmit power in topologies by ACMI compared against MIA, and by ACDI compared against DIA. Figure 4b illustrates that the average node degree varies with the number of nodes. It depicts the average node degree is relatively stable and no larger than 2.2. The average-hop of the shortest path between two nodes is shown in Fig. 4c. We can observe that, there is a smaller gap (about one-hop) of the path length by our algorithms than that by MIA and DIA. In Fig. 4d, we show the variation of the number of information exchange with the number of nodes. Obviously, DIA and MIA suffers excessive information-overheads, which increase quickly as the number of nodes increases. Using global connectivity information does not produce a noteworthy energy-efficiency improvement compared with using neighboring connectivity information, but an excessive information-overhead. Therefore, ACDI, which has the sub-optimal topology performance but less information-overhead, is the best choice for practical applications.

7 Conclusions

Nodes in an ad hoc network have been restricted to local communications and make topological decisions selfishly to act in their self-interests. However, the network itself should operate towards a global goal, i.e., energy-efficient connectivity. A non-cooperative game aided topology control approach was developed for minimizing the potential transmit powers at nodes, whilst maintaining the connectivity of the network. The existence of NE was proved in our theoretic analysis. Two fully distributed topology optimization schemes, ACMI and ACDI, were proposed to construct the energy-efficiently connected network, which are vital and practical as the nature of ad hoc network is self-organizing. Both ACMI and ACDI with local information achieved the network connectivity with lower information-overhead and more practical implementation in contrast to MIA and DIA with global information, though suffering a little bit degradation in energy-efficiency. By adaptively adjusting the connectivity parameter, the tradeoffs between energy efficiency and connectivity redundancy were captured by our algorithms. However, there also exist some interesting problems which we will be addressed in the future research. For instance, how to prolong the network lifetime by considering each node’s residual battery energy, what happens if an expanding node selfishness (e.g., selfishness at routing layer) is taken into account.