# Game Theory Based Construction Efficient Topology in Wireless Sensor Networks

Authors: M. J. Abbasi; Muhammad Shafie Bin Abd Latiff; Hassan Chizari; N. Fisal
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Topology control is one of the most important techniques used in
wireless sensor networks; to some extent it can reduce energy consumption in which
each node is capable of minimizing its transmission power level while preserving
network connectivity. Reducing energy consumption has been addressed through
different aspects till now. In this paper, we present a minimum spanning tree-
(MST-) based algorithm, called noncooperative minimum spanning tree (NMST),
for topology control in wireless multihop networks. In this algorithm, each
node constructs its minimum power-cost spanning tree which is a tree and can
connect the node with one hop away from its neighbor node in constructed topology.
In addition we address the power-cost allocation problem when node acts
selfishly. A class of strategies is proposed which construct minimum power-cost
spanning tree such that the sum of the power-cost (as proxy of weight), at the
same time, is a strong Nash equilibrium for a noncooperative game associated
with the problem of efficient topology construction. Simulation results show that
NMST can maximize the sensor network lifetimes.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are composed of smart nodes, that is, tiny devices equipped with communication component, data computation, and sensing capability [1–3]. In this type of network, each node collects information from the target area and sends this information to a sink, through a multihop communication network. A wireless sensor network consists of a large number of nodes, which are densely deployed inside the target area or very closed off the target area.These WSNs can be employed to increase the efficiency of many important applications such as health care, intrusion detection and plants control, weather monitoring, security and tactical surveillance, disaster monitoring, and ambient conditions detection [4, 5]. Deployment and development of wireless sensor network are limited in terms of resources for a variety of applications. These limitations pose a number of challenges such as routing protocol, topology control scheme, aggregation mechanism, and flow maximization [1, 6, 7]. Many of these challenges are related to issuing problems that have not been solved. Therefore, one of the main design goals to prolong the lifetime of the network through the minimization of the per-node energy consumption is topology control. Deploying several hundreds to thousands of inaccessible and unattended sensor nodes, which are prone to frequent failures, makes topology control an ambitious task. Each node optimizes its own power range while preserving network connectivity by topology control [8–11]. This act must not intervene in the formal service in the wireless network and the system must have enough node degree to increase robustness and adjust minimum transmission power range as well as reduce energy consumption.To efficiently extend the lifetime of the WSN nodes, limited and nonrechargeable battery and energy resources need to be managed efficiently [12]. Efficient topology control (TC) algorithm could conserve energy. The main idea of TC is that nodes collaboratively set their transmission range instead of maximum transmission level and generate the connected topology accordingly. The purpose of a topology control is prolonging the network lifetime while preserving network connectivity. It has been demonstrated that the topology of wireless sensor network has a significant effect on the energy depletion rate of the node [13]. So far, several algorithms had been proposed and evaluated to compose connected topology. As a result, energy consumption becomes minimum while connectivity is preserved.Several algorithms such as LMST [14], XTC [15], and OTTC [16] are introduced for connected topology in wireless networks. In topologies constructed by XTC, LMST, and OTTC the number of neighbors and energy efficiency are considerably bounded. However, in previous approaches each node selects its transmission power individually based on link weights which reduce energy consumption. Moreover, as the result of the topology process some nodes have to use high transmission power level which resulted in the increase energy consumption specifically when high transmission power level is chosen.Nodes act selfishly and are conflicting with each other in pursuit of energy efficiency and connectivity. However, selfish nodes try to overcome conflicting objectives with the pursuit of energy efficiency and topology connectivity. If the nodes select lower transmitting range, the constructed topology will be disconnected. The main problem is to establish a tradeoff within nodes. Game theory is a useful tool to solve the conflicting objectives of nodes in improving the energy efficiency and topology connectivity in the presence of selfish nodes. Several mechanisms for designing of TC based on game theory had been proposed, such as max improvement algorithm (MIA) [17], δ-improvement algorithm (DIA) [18], and Local-DIA [19]. In DIA, the nodes are expected to have only incomplete information of the topology. However, in general a Nash equilibrium (NE) does not converge to construct energy-efficient topology. Furthermore, there exists strategy profile, which is not NE to construct energy efficiency topology.In this paper, we proposed a minimum spanning tree based topology control which we called noncooperative minimum spanning tree (NMST) for wireless network. In this algorithm, we introduce the class of opportune moment strategies which, at the same time, are strong Nash equilibria and produce minimum power-cost spanning trees. We also prove that these strategies are subgame perfect Nash equilibria and strong Nash equilibria. In addition, it is also important to note that the payoffs provided by any profile of opportune moment strategies construct topology with minimum power level. Hence, our opportune moment strategies can be seen as a new justification for the usage of cost allocations in minimum power-cost spanning tree games. The NMST algorithm specifies that(
1
) the constructed topology is connected with a sufficient number of neighbors to increase network performance in real time; (
2
) the degree of each node is sufficient which can minimize the amount of interference and ensure that the network not partition; (
3
) the constructed topology should contain only bidirectional link in which most routing protocols for wireless networks implicitly assume that wireless links are bidirectional.The rest of this paper is organized as follows. Section2 provides an overview of main concepts of game theory which are used throughout this paper. Network model, assumptions, and definitions are presented in Section 3. Moreover, the topology construction process and some properties in case of information exchange and transmission power adjusting which can use moment opportunity model are presented in Section 4. The analysis of NMST game is presented in Section 5. In Section 6 we evaluate the effectiveness of NMST through simulations and compare it with existing algorithms DIA and OTTC. Finally Section 7 presents the concluding remarks.


### 1.1. Related Work

Lately, many TC algorithms have been introduced for sensor networks. All TC algorithms can be arranged as centralized and distributed. In the centralized algorithms [20, 21], a particular node based on global knowledge is responsible for constructing connected topology. These algorithms cannot be used on distributed nodes. The other class contains distributed algorithms that we deal with in this paper. The author in [15] proposed XTC algorithm for topology control that operates with the neighbors’ link qualities. The main features of XTC algorithm are relevant properties (symmetry, connectivity, sparseness, and planarity) of TC while being faster than any previous algorithm. The XTC algorithm does not require node coordinate information. In [16] the author proposed OTTC algorithm that operates with weight of the links. Each node collects its one-hop neighbors in an ordered list and exchanges the list between its neighbors. The OTTC works in fully distributed and low quality information.Game theory has been used as a tool to model and investigate different aspects of wireless communication [22]. The authors in [23] were the first in proposing the equilibrium in topology control game. However, in their proposed algorithm, the stable point of NE is not guaranteed. Furthermore, Nash equilibrium TC algorithms do not consider the energy efficiency.The authors in [17] reformulated the algorithm in [23] as exact potential games (EPG). EPG respond to the existence of at least one NE. MIA [17], DIA [18], and Local-DIA [19] were investigated to adjust the per-node power level such that the resulting topology was energy-efficient while preserving network connectivity. However, in the MIA approach, the authors denoted that various steady-state outcomes emerge based on the order in which nodes modify their strategies. Local-DIA was enhanced from DIA; however the works were based on k-hop neighborhood exchange information. The algorithms assume that nodes are responsible for constructing topology. The authors studied Nash equilibrium to construct efficient topology, when nodes employ a greedy best response mechanism. However, in general a NE does not converge to construct energy-efficient topology.Most of the previous topology control algorithms adjust transmission power levels based on residual energy of neighbor nodes to balance energy consumption [24–26]. However, using such topology construction nodes cannot generate efficient connected topology. Moreover, all proposed algorithms can be efficient in maintenance phases and their algorithms cannot construct energy-efficient topology in beginning of network operational time.


## 1.1. Related Work

Lately, many TC algorithms have been introduced for sensor networks. All TC algorithms can be arranged as centralized and distributed. In the centralized algorithms [20, 21], a particular node based on global knowledge is responsible for constructing connected topology. These algorithms cannot be used on distributed nodes. The other class contains distributed algorithms that we deal with in this paper. The author in [15] proposed XTC algorithm for topology control that operates with the neighbors’ link qualities. The main features of XTC algorithm are relevant properties (symmetry, connectivity, sparseness, and planarity) of TC while being faster than any previous algorithm. The XTC algorithm does not require node coordinate information. In [16] the author proposed OTTC algorithm that operates with weight of the links. Each node collects its one-hop neighbors in an ordered list and exchanges the list between its neighbors. The OTTC works in fully distributed and low quality information.Game theory has been used as a tool to model and investigate different aspects of wireless communication [22]. The authors in [23] were the first in proposing the equilibrium in topology control game. However, in their proposed algorithm, the stable point of NE is not guaranteed. Furthermore, Nash equilibrium TC algorithms do not consider the energy efficiency.The authors in [17] reformulated the algorithm in [23] as exact potential games (EPG). EPG respond to the existence of at least one NE. MIA [17], DIA [18], and Local-DIA [19] were investigated to adjust the per-node power level such that the resulting topology was energy-efficient while preserving network connectivity. However, in the MIA approach, the authors denoted that various steady-state outcomes emerge based on the order in which nodes modify their strategies. Local-DIA was enhanced from DIA; however the works were based on k-hop neighborhood exchange information. The algorithms assume that nodes are responsible for constructing topology. The authors studied Nash equilibrium to construct efficient topology, when nodes employ a greedy best response mechanism. However, in general a NE does not converge to construct energy-efficient topology.Most of the previous topology control algorithms adjust transmission power levels based on residual energy of neighbor nodes to balance energy consumption [24–26]. However, using such topology construction nodes cannot generate efficient connected topology. Moreover, all proposed algorithms can be efficient in maintenance phases and their algorithms cannot construct energy-efficient topology in beginning of network operational time.


## 2. Game Theory Assumptions

This section presents a short review of fundamental elements of noncooperative strategic-form game. The main element of this algorithm is the game, which is a general method of an interactive decision making.The elements of the game theory are defined as{
N
u
,
A
u
,
P
u
}, where N is a set of players in the game and A
u is a set of strategies of a player u
∈
N, where each strategy a
u of the vector u related to the A
u. Denote a strategy profile a
=
(
a
u
,
a
-
u
), where a
u is the player u’s strategy and a
-
u denote the strategy of n
-
1 players. For each player u, P
u is payoff function.In noncooperative strategic-form game NE is an important concept and the most prevalent. In such concept solution, no player has any incentive to deviate from its strategy, because game is defined as a fixed point of NE.Definition 1.
The profile of strategy ofa
∈
A is a Nash equilibrium for the described game Γ
(
G
,
p
), if for every player of the game {
p
u
≤
p
u
(
a
,
a
u
′
)
∀
a
u
′
∈
A
u
,
a
u
′
≠
a
u
}, where a
u
′ is the space vector representing the strategies of all actions except u. Informally, (
a
u
′
) is a NE, if no action u has the incentive to change its profile strategy.That is,a is a NE, if any deviation of player u from the profile of strategies a does not yield an improvement in the energy consumption assigned to player u. In this model, each node is noncooperative to select its strategy. Therefore, set of strategies A
u for u
∈
N is R for the set of all possible strategies. The selected strategy a
- is a power vector p
- with p
u being power levels of u.


## 3. Framework and Assumptions

### 3.1. Network Model

Let the graphG
=
(
N
,
E
,
w
) represent the sensor networks, where N is the number of sensor nodes and N
=
1,2
,
…
,
n. Each node has to connect to a common path, i, and w
-
∈
R
E; that is, w
e
≥
0 is the beginning weight on edges e
∈
E. In WSN with bidirectional transmission range r
∈
R
n constructs topology G
=
(
N
,
E
) in the following scheme: e
=
(
u
,
v
)
∈
E in E if r
u
≥
w
e. Note that the topology is produced by the radius vector r with G
(
N
,
r
).The graphG is in Euclidean space with the number of neighbors N in R
i, such that w
=
d
(
u
,
v
), where d is an Euclidean distance. Denote that nodes u and v are connected, when they are connected with some intermediate node i. If u and v are connected, then removing any arbitrary set, S
⊆
N
∖
{
u
,
v
}, preserves network connectivity. Moreover, for each subgraph of node S
⊆
N, defined by S
i
=
S
∪
i and by G
S the topology (
S
i
,
E
S
i
), where S
i defines the set of nodes and E
S
i is the set of edges, E
S
i
⊆
{
(
u
,
v
)
∈
S
i
×
S
i
,
|
u
,
≠
v
}.


### 3.2. Game Theory Mapping

Here, the topology control process as a normal form game is described. Each nodeu uses incremental power levels to connect to the topology in each step of the game. As such, if each node decides to connect to the topology, it has to use certain transmission power while preserving network connectivity. Therefore, to construct an energy-efficient topology, nodes must use minimum transmission power level between two nodes while ensuring network connectivity. Given two sets of neighbors u
1
,
v
1 and u
2
,
v
2, the link weights d
′
:
E
→
R are determined as d
(
u
1
,
v
1
)
>
d
(
u
2
,
v
2
). The weight function guarantees the MST T
a constructed by node u are unique. While a node u generates the topology, it will determine its neighborhoods. If no node joins the topology at the end of game, each node has to use a penalty that means using higher transmission power than current transmission power to connect to node v. Node v is neighbor of a node u, if and only if (
u
,
v
)
∈
T
u. Furthermore, u and v have reverse link if and only if u reaches to v and v reaches to u.In each step of the games, nodeu tries to connect to node v by using high transmission power which results in more energy consumption. However, each node tries to connect to the topology even, they have to use their maximum transmission power. Furthermore, this condition can be reformulated by stating that when game ends with some nodes which are not joined to the topology, then it uses another strategy, which means using higher transmission power level. Each strategy is represented as a
=
(
a
u
)
u
∈
N. Note that A
u is the list of all available strategies for node u by A. Given strategies of a for all lists of nodes, N, and a subset of nodes S
⊂
N, noted by (
a
S
,
a
-
S
), the layout of a on S
(
N
∖
S
) denoted the responsible strategies for the nodes in S
(
N
∖
S
). Moreover, (
a
,
a
S
′
) represents the strategy profile in which nodes in S deviate from a by using a
′; that is, (
a
,
a
S
u
′
)
=
a
u
′ for any u
∈
S and (
a
,
a
S
v
′
)
=
a
j for all v
′
∈
S.The results about noncooperative minimum spanning trees that are useful in the analyses of the problem presented in this chapter are assumed as follows.Theorem 2.
Denote a MST byT
S on S
i
⊂
N
i, that is, NMST on N
i. If u
∈
M
S
,
v
∈
S
i, then, at least one of the NMSTs on N
i includes T
S
∪
(
u
,
v
)
∪
E
S.Proof.
As a result of the properties on MST, ifu
∈
M
S and v
∈
S
i, the set of topologies {
T
S
,
T
{
u
}
,
u
∈
N
∖
S
} is considered. Furthermore, there exists at least one NMST on N
i which includes T
S
∪
{
(
u
,
v
)
} since c
u
v is minimum power levels within T
S and any other MST in topology. Moreover, by considering the topology {
T
S
∪
(
u
,
v
)
,
T
{
k
}
,
k
∈
N
∖
S
∪
{
u
}
} and any u
∗
∈
M
S, the similar reason could be applied to connect u
∗ to a best node v
∗
∈
S
u
i
∗, since c
u
∗
v
∗ is the minimum power for u
∗ and is the lower communication cost within T
u
∗ and any other MST in the topology. Additionally, there is at least one NMST on N
i which includes T
S
∪
{
(
u
,
v
)
∪
(
u
∗
,
v
∗
)
}. In addition, all other nodes u
∗
∈
M
S could connected to nodes in S
i in the similar process.It is significant to point out that to deduce the result in Theorem2 it is not sufficient for T
S to be a NMST on S
i, but it is necessary that T
S be contained in a NMST on N.


## 3.1. Network Model

Let the graphG
=
(
N
,
E
,
w
) represent the sensor networks, where N is the number of sensor nodes and N
=
1,2
,
…
,
n. Each node has to connect to a common path, i, and w
-
∈
R
E; that is, w
e
≥
0 is the beginning weight on edges e
∈
E. In WSN with bidirectional transmission range r
∈
R
n constructs topology G
=
(
N
,
E
) in the following scheme: e
=
(
u
,
v
)
∈
E in E if r
u
≥
w
e. Note that the topology is produced by the radius vector r with G
(
N
,
r
).The graphG is in Euclidean space with the number of neighbors N in R
i, such that w
=
d
(
u
,
v
), where d is an Euclidean distance. Denote that nodes u and v are connected, when they are connected with some intermediate node i. If u and v are connected, then removing any arbitrary set, S
⊆
N
∖
{
u
,
v
}, preserves network connectivity. Moreover, for each subgraph of node S
⊆
N, defined by S
i
=
S
∪
i and by G
S the topology (
S
i
,
E
S
i
), where S
i defines the set of nodes and E
S
i is the set of edges, E
S
i
⊆
{
(
u
,
v
)
∈
S
i
×
S
i
,
|
u
,
≠
v
}.


## 3.2. Game Theory Mapping

Here, the topology control process as a normal form game is described. Each nodeu uses incremental power levels to connect to the topology in each step of the game. As such, if each node decides to connect to the topology, it has to use certain transmission power while preserving network connectivity. Therefore, to construct an energy-efficient topology, nodes must use minimum transmission power level between two nodes while ensuring network connectivity. Given two sets of neighbors u
1
,
v
1 and u
2
,
v
2, the link weights d
′
:
E
→
R are determined as d
(
u
1
,
v
1
)
>
d
(
u
2
,
v
2
). The weight function guarantees the MST T
a constructed by node u are unique. While a node u generates the topology, it will determine its neighborhoods. If no node joins the topology at the end of game, each node has to use a penalty that means using higher transmission power than current transmission power to connect to node v. Node v is neighbor of a node u, if and only if (
u
,
v
)
∈
T
u. Furthermore, u and v have reverse link if and only if u reaches to v and v reaches to u.In each step of the games, nodeu tries to connect to node v by using high transmission power which results in more energy consumption. However, each node tries to connect to the topology even, they have to use their maximum transmission power. Furthermore, this condition can be reformulated by stating that when game ends with some nodes which are not joined to the topology, then it uses another strategy, which means using higher transmission power level. Each strategy is represented as a
=
(
a
u
)
u
∈
N. Note that A
u is the list of all available strategies for node u by A. Given strategies of a for all lists of nodes, N, and a subset of nodes S
⊂
N, noted by (
a
S
,
a
-
S
), the layout of a on S
(
N
∖
S
) denoted the responsible strategies for the nodes in S
(
N
∖
S
). Moreover, (
a
,
a
S
′
) represents the strategy profile in which nodes in S deviate from a by using a
′; that is, (
a
,
a
S
u
′
)
=
a
u
′ for any u
∈
S and (
a
,
a
S
v
′
)
=
a
j for all v
′
∈
S.The results about noncooperative minimum spanning trees that are useful in the analyses of the problem presented in this chapter are assumed as follows.Theorem 2.
Denote a MST byT
S on S
i
⊂
N
i, that is, NMST on N
i. If u
∈
M
S
,
v
∈
S
i, then, at least one of the NMSTs on N
i includes T
S
∪
(
u
,
v
)
∪
E
S.Proof.
As a result of the properties on MST, ifu
∈
M
S and v
∈
S
i, the set of topologies {
T
S
,
T
{
u
}
,
u
∈
N
∖
S
} is considered. Furthermore, there exists at least one NMST on N
i which includes T
S
∪
{
(
u
,
v
)
} since c
u
v is minimum power levels within T
S and any other MST in topology. Moreover, by considering the topology {
T
S
∪
(
u
,
v
)
,
T
{
k
}
,
k
∈
N
∖
S
∪
{
u
}
} and any u
∗
∈
M
S, the similar reason could be applied to connect u
∗ to a best node v
∗
∈
S
u
i
∗, since c
u
∗
v
∗ is the minimum power for u
∗ and is the lower communication cost within T
u
∗ and any other MST in the topology. Additionally, there is at least one NMST on N
i which includes T
S
∪
{
(
u
,
v
)
∪
(
u
∗
,
v
∗
)
}. In addition, all other nodes u
∗
∈
M
S could connected to nodes in S
i in the similar process.It is significant to point out that to deduce the result in Theorem2 it is not sufficient for T
S to be a NMST on S
i, but it is necessary that T
S be contained in a NMST on N.


## 4. Noncooperative MST Topology Control Algorithm

This section discusses the MST with connectivity on a bidirectional link, where each node has to reach each of the other sensor nodes overu. The further discussion is on decision making of nodes to connect to the other nodes in a noncooperative game, Γ
(
G
,
p
), related with each lower power level problem in the topology G with energy costs p. The introduced algorithm consists of 3 phases: exchange information, adjust transmission power that constructs topology with opportunity moment, and update phases.


### 4.1. Information Exchange Phases

Each nodeu needs all nodes in its response neighborhood’s information for topology construction. This can be obtained by having each node u broadcast “Hello Messages” using its maximum transmission power level and receive ACK from neighbor. The information contained in a “Hello Message” should include the node ID and the position of node. Each node can define its neighborhoods power level. p
u
v is the power required to edge u
→
v and it is channel attenuation, internodal separation, and the power range threshold p
th at which the response neighbor can understand the “Hello Message.” The transmission power level between two nodes can be computed based on “Determination of Transmission Power” [14]. For simplicity i
d
N
u
=
u, neighborhood response N
u
(
G
) of a node u is defined by the following definition.Definition 3 (response neighbor).
The response neighborN
u
(
G
) is the list of nodes that node u can be connected to by using its maximal power level p
max
⁡
⁡
N
u
(
G
)
=
{
v
∈
G
s
}
:
p
(
u
,
v
)
<
p
max
⁡
⁡ and maximum distance d
max
⁡; that is, N
u
(
G
)
=
{
v
∈
G
s
}
:
d
(
u
,
v
)
<
d
max
⁡
⁡.In this algorithm, nodes’ neighbor list is set to arrange nodeu’s strategy. In order to collect other nodes’ strategy profile, each node u is required to broadcast “Hello Message” to its 1-hop and 2-hop neighbors.


### 4.2. Transmission Power Adjusting Phases

In the beginning, all nodes are disconnected. Based on information exchange each nodeu decides whether to join the topology or not. The game ends, when either no node connects or every node connects to the topology. Otherwise, the game proceeds to a next step. In subsequent steps, the unconnected node faces a set of nodes already joined to the topology and has made a decision, whether to remain unconnected or to join to one of the nodes in the topology. The game ends when no more nodes join or when all the nodes are already joined in a topology.Letp
u
(
a
) denote the transmission power for node u when a strategy profile a is adjusted. Thus, the total transmission power generated by a is noted by p
(
a
), p
(
a
)
=
∑
u
∈
N
‍
p
u
(
a
).Denote that, in the rest of this chapter, any NE construct a MST onN.Definition 4.
The strategy profile ofa
∈
A is a strong Nash equilibrium (SNE) for γ
(
N
,
p
), if, for each cooperation S
⊂
N and each a
S
′
=
a
S, there is at least one node with a minimum power level u
∈
S such that p
u
(
a
)
≤
p
u
(
a
;
a
S
′
).In general, this last equilibrium notion is stronger than that of NE. A SNE is such that deviations from the strategy of any nodes will not yield a development in the transmission cost of all the nodes that deviate.However, in this algorithm, a NE of the gameΓ
(
N
,
p
) is also a SNE, as is presented in the following lemma.Lemma 5.
Ifa
∈
A is a NE for Γ
(
N
,
p
), then a is a SNE.Proof.
Without loss of generality,a is a non-SNE for a game Γ
(
N
,
p
). Let H
⊂
N be a subset of a node and a
∗ be a strategy of the nodes in H such that p
u
(
a
,
a
H
∗
)
<
p
u
(
a
) for all u
∈
H. Let T
⊆
N
∖
H be the list of nodes, which join if the response neighbor N
∖
H plays based on a and if nodes in H ever play a. Furthermore, for all u
∈
H, p
u
a
≤
mi
n
v
∈
T
{
p
u
v
}, since a is a NE and the strategy of delaying until all response neighbors of T are connected at a current transmission power level. Let u be the first node in H that joins when (
a
,
b
H
) is played. Then u applies a
r
c to a node in T, and therefore p
u
(
a
,
a
H
∗
)
≥
mi
n
v
∈
T
{
p
u
v
}, which is a contradiction.Leta
=
(
a
u
)
i
∈
N be a strategy for the set of nodes, N, and let T
a be the topology constructed on S
u
⊆
N
u (this topology connects a set of nodes S
u to the u). Let T
S be any subgraph of T
a, which contains the node u, where S
⊂
S
u is the set of involved bidirectional paths.NoticeN
∖
S by S
- and push T
S to a fictitious node u
-
∈
S
-. Define the subgame (
S
-
u
-
,
p
S
), where S
-
u
-
=
S
-
∪
u
- and p
u
v
S
=
p
i
j.Definition 6.
The strategya
∈
A is a subgame prefect Nash equilibrium (SPNE) for the game Γ
(
N
,
p
) if a
-
S is a NE for any subgame (
S
-
u
-
,
p
S
).Recall that not all NE are SPNE and a NE does not construct a NMST. Furthermore, there exist strategies which are not NE but construct NMST onN
u.The necessity of selecting a minimum power level forces the nodes to connect to the topology when the minimum transmission range is available. DefineB
u
=
{
v
∈
N
:
(
v
,
u
)
∈
A
u
∗
,
p
∪
(
v
,
u
)
∈
P
u
,
∀
p
∈
P
v
}
,
u
∈
N, as the set of nodes v such that node u can connect at its lower power level to v and the union of (
v
,
u
) with any shortest bidirectional path from u to v.Definition 7.
The strategya
u
∈
A
u is a Bellman strategy for node u in Γ
(
G
,
p
) if, for any S
∈
2
N
(
u
),(1)
a
u
(
S
)
=
P
∪
(
v
,
u
)
if
v
∈
B
i
∩
S
,
s
∈
P
v
,
p
⊆
dis
otherwise
.LetP
u be the collection of all minimum transmission power from u to v. A profile strategy for the node u
∈
N is a map a
u
:
2
(
u
)
N
→
P
u
∪
{
dis
} such that a
u
(
S
)
=
p illustrates that the node u generates the subgraph of p starting from the last node on a graph p that is a response neighbor of S and ending at node u. Note that no graph was named “dis” and use this symbol for the selection of the unconnected nodes; a
u
(
S
)
=
dis means that node u does not generate any link when the current MST is S.


#### 4.2.1. Opportune Moment Adjusting

In the case where each node’s smallest power level constructs a topology, this topology is a MST. However, this action could not construct a topology, and further improvement is necessary to algorithm of the strategy that the nodes will adjust transmission power. Initially, when at a current time of the gameΓ
(
N
,
p
) the minimum power of a node is available, it joins to the topology, by using the “best individual opportunity.” However, when the node does not consider the “best individual opportunity” and wants to wait for connection to the topology, it may have opportunity of a best connection with a minimum power level. Let σ
:
2
N
→
N represent a permutation function that denoted node power level ranking. Furthermore, for each ranking, σ, let f
σ
2
N
→
N represent the function that adopts to every coalition M
∈
2
N the node, u
σ
∈
M
,
f
σ
(
M
)
=
u
σ
∈
(
M
), such that σ
(
u
σ
≤
σ
(
u
)
,
∀
u
∈
M
). The strategies for the aforementioned function are based on the ranking, σ, applied as a tiebreaker to select the nodes that wish to join its neighbors which have the minimum power level. Moreover, given the ranking, σ, when nodes in S are already connected, the best node in M
S
=
{
u
∈
N
∖
S
∣
∃
v
∈
S
,
p
u
v
=
m
S
}
,
f
σ
(
M
S
), is selected to connect to the connected topology.Definition 8.
A ranking of each node,σ, an opportune moment strategy, a
σ
∈
A, for Γ
(
N
,
p
) is denoted as follows:(2)
a
u
σ
(
S
)
=
k
∈
B
u
∩
S
,
if
,
B
u
∩
S
≠
0
v
∈
S
u
,
if
,
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.Recall that, by applying an “opportune moment strategy” profile, more than one node may reach to the existing connected topology at any step of the game, but only one of these response nodes uses its best opportunity. Additionally, a strategy is well defined since, if at the same proceeding time,B
u
∩
S
≠
0 and u
∈
M
S, then B
u
∩
S
=
S
u.Note that the opportune strategy is different from those strategies used by Prim’s algorithm with a ranking; that is,(3)
y
u
σ
(
S
)
=
v
∈
S
u
if
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.The following result states that Bellman profile strategies are NE for the gameΓ
(
G
,
p
) and push dis NMST on N
u and then a profile of opportune moment strategies is a SPNE and induces a NMST on N
u.Theorem 9.
Given a ranking for nodes,σ, a profile of opportune moment strategies for the game Γ
(
G
,
p
) constructs NMST on N
u and is SPNE. On the other hand, if strategy a constructs a NMST on N
u, then ranking of nodes, σ, and a profile of opportune moment strategies, a
σ, exist such that p
u
(
a
)
=
p
u
(
a
σ
) for all nodes u
∈
N.Proof.
To prove that a strategy profile ofa
σ is a SPNE considering the MST T
a
σ, any subgraph T
S of T
a
σ, with bidirectional path on the connected topology, and the set of nodes S
⊂
N generate (
S
i
=
S
∪
i
). Let (
S
-
i
~
,
p
S
) be the corresponding subgame. Assume that node u
∈
S deviates from strategy a
σ by using a strategy a
u. One of the following inductions occurs.(1)
Either
(a)
B
u
∩
S
i
=
0 and u
∉
M
S or
(b)
B
u
∩
S
i
=
0
,
u
∈
M
S, and f
σ
(
M
S
)
≠
u.
If nodeu is refused from a
σ by applying a
u, which consists of connection to any node v
∈
S of the certain topology, then (
a
σ
;
a
u
)
u
(
S
)
=
a
u
(
S
)
=
v
∈
S and node u higher transmission power level p
u
(
a
σ
,
a
u
)
=
p
u
v
≥
m
u
S. Since every node in S, except for node u, uses a
-
(
S
∪
{
u
}
)
σ, if the node u is not refused from a
u
σ and remains disconnected from the topology, it waits for its best opportunity to connect to the topology with a minimum power level. Therefore, if the node u uses an opportunity, a
u
σ, it could be reached at this stage with maximum power level p
u
(
a
σ
)
=
m
u
R
≤
m
u
S
≤
p
u
v
=
p
u
(
a
σ
,
a
u
).
(2)
B
u
∩
S
i
=
0
,
u
∈
M
S
,
and
f
σ
(
M
S
)
=
u, but either
(i)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
v
∉
S
i
u or
(ii)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
dis.
Obviously, nodeu is not improved by joining to v
∉
S
u. On the other hand, if the node u is refused from a
σ by applying a
u, which consists of nonconnected nodes, the rest of the nodes play a
S
∪
u
σ and the minimum transmission level does not appear, since nodes in M
S connect at their minimum power level, which are not less than m
u
S. Therefore, node u does not improve its opportunity strategy and loses its best opportunity.
(3)
B
u
∩
S
i
≠
0, but either
(a)
a
σ
;
a
u
u
S
i
=
a
u
S
i
=
v
∉
B
u
∩
S
i
u, or
(b)
a
σ
;
a
u
u
S
i
=
a
u
(
S
i
)
=
dis.
SinceB
u
=
{
v
∈
N
∖
{
u
}
∣
a
u
v
≤
a
u
k
,
∀
k
∈
N
,
k
≠
u
}, then node u is not improved by joining v
∉
B
u
∩
S, nor by waiting for a minimum power level and therefore, p
(
a
σ
;
a
u
)
≥
p
u
(
a
σ
).Conversely, leta be a strategy for the set of nodes, N, that construct a NMST on graph G. Let T
a be the constructed NMST topology. Since, by using Prim’s algorithm, all minimum transmission power levels in the topology can be constructed, consider the ranking of the nodes, σ, that reflects how the nodes are reached by Prim’s algorithm when T
a is the result. Consider also the profile of opportune moment strategies a
σ. Obviously, p
u
(
a
)
≥
p
u
(
a
σ
) for all u
∈
N. Furthermore, the equality holds since if at a stage when the nodes in S
u
=
S
∩
u are connected the nodes in M
S use their minimum transmission to connect to the topology. Therefore, p
u
(
a
)
=
p
u
(
a
σ
) for all nodes that, when using a
σ, do not use their best individual opportunity. The equality holds also for those nodes that, by playing a
σ, use their best individual opportunity when it is not their best collective opportunity. This happens due to the fact that they use their minimum transmission power which is already available.Note that, in the converse part of Theorem9, it can be concluded that the allocation of costs provided by any profile of strategies inducing a MCST (which is not necessarily NE) can always be attained by a profile of opportune moment strategies.Algorithm1 formulate the description of NMST topology control Γ
(
N
,
p
).Algorithm 1:Noncooperative MST Γ
(
p
max
⁡
→
p
u
) algorithm.
Data: nodeu's one and one-hop and two hop neighborhood list
Output: nodeu's power range p
u
(1)m
=
1
(2)  Construct the undirected, complete graphK
N over N with edge weights p
(
u
,
v
) for all
{
u
,
v
∈
N
}. // Initialize each sensor node transmission power to max
(3)  Find a minimum weight spanning treeT of K
N
(4)  For allv
∈
N let p
u
v
=
max
⁡
{
w
v
,
u
∥
{
v
,
u
}
∈
T
}
(5)while:  P
u is not strong Nash equilibrium do
(6)m
=
m
+
1
(7)for  u
∈
N in ascending neighborhood list of ID do
(8)  select best individualp
u
′
=
p
u
v
∈
P
u
(9)
if  u can connect by Bellman strategy the node k with reverses link
(10)Γ
(
G
,
p
)
=
p
(
a
u
(
S
)
)
(11)else  d
i
s
(12)if Bellman profile strategy is NE for the game Γ
(
G
,
p
) and pushes dis to join MST on N
A ranking of the sensor nodes,σ, an opportune moment strategy, a
σ, for Γ
(
G
,
p
)
(13)endif
(14)endif
(15)p
u
′
=
arg
⁡
max
⁡
Γ
(
G
,
p
u
(
a
σ
)
)
(16)endfor
(17)endwhile


### 4.3. Update Phases

Under algorithm NMST, nodes’ selection of transmission power range in each iteration redefines its neighbor. Since a particular node adjusts its transmission power to the current power level, other neighbors are made aware of this adjustment by means of sending “Hello Message.” Each node sends messages to its neighbor order list every time there is a change in its 1-hop neighbor. Denote that it is necessary for every node to broadcast updates only to those nodes that are within their two-hop order list. The idea of two-hop neighbor is capable of minimizing the overhead cost from increasing with network size. Upon receiving these messages, other nodes update their neighbor order lists. Every node responds to the topology change by adjusting an adequate transmission power range.


## 4.1. Information Exchange Phases

Each nodeu needs all nodes in its response neighborhood’s information for topology construction. This can be obtained by having each node u broadcast “Hello Messages” using its maximum transmission power level and receive ACK from neighbor. The information contained in a “Hello Message” should include the node ID and the position of node. Each node can define its neighborhoods power level. p
u
v is the power required to edge u
→
v and it is channel attenuation, internodal separation, and the power range threshold p
th at which the response neighbor can understand the “Hello Message.” The transmission power level between two nodes can be computed based on “Determination of Transmission Power” [14]. For simplicity i
d
N
u
=
u, neighborhood response N
u
(
G
) of a node u is defined by the following definition.Definition 3 (response neighbor).
The response neighborN
u
(
G
) is the list of nodes that node u can be connected to by using its maximal power level p
max
⁡
⁡
N
u
(
G
)
=
{
v
∈
G
s
}
:
p
(
u
,
v
)
<
p
max
⁡
⁡ and maximum distance d
max
⁡; that is, N
u
(
G
)
=
{
v
∈
G
s
}
:
d
(
u
,
v
)
<
d
max
⁡
⁡.In this algorithm, nodes’ neighbor list is set to arrange nodeu’s strategy. In order to collect other nodes’ strategy profile, each node u is required to broadcast “Hello Message” to its 1-hop and 2-hop neighbors.


## 4.2. Transmission Power Adjusting Phases

In the beginning, all nodes are disconnected. Based on information exchange each nodeu decides whether to join the topology or not. The game ends, when either no node connects or every node connects to the topology. Otherwise, the game proceeds to a next step. In subsequent steps, the unconnected node faces a set of nodes already joined to the topology and has made a decision, whether to remain unconnected or to join to one of the nodes in the topology. The game ends when no more nodes join or when all the nodes are already joined in a topology.Letp
u
(
a
) denote the transmission power for node u when a strategy profile a is adjusted. Thus, the total transmission power generated by a is noted by p
(
a
), p
(
a
)
=
∑
u
∈
N
‍
p
u
(
a
).Denote that, in the rest of this chapter, any NE construct a MST onN.Definition 4.
The strategy profile ofa
∈
A is a strong Nash equilibrium (SNE) for γ
(
N
,
p
), if, for each cooperation S
⊂
N and each a
S
′
=
a
S, there is at least one node with a minimum power level u
∈
S such that p
u
(
a
)
≤
p
u
(
a
;
a
S
′
).In general, this last equilibrium notion is stronger than that of NE. A SNE is such that deviations from the strategy of any nodes will not yield a development in the transmission cost of all the nodes that deviate.However, in this algorithm, a NE of the gameΓ
(
N
,
p
) is also a SNE, as is presented in the following lemma.Lemma 5.
Ifa
∈
A is a NE for Γ
(
N
,
p
), then a is a SNE.Proof.
Without loss of generality,a is a non-SNE for a game Γ
(
N
,
p
). Let H
⊂
N be a subset of a node and a
∗ be a strategy of the nodes in H such that p
u
(
a
,
a
H
∗
)
<
p
u
(
a
) for all u
∈
H. Let T
⊆
N
∖
H be the list of nodes, which join if the response neighbor N
∖
H plays based on a and if nodes in H ever play a. Furthermore, for all u
∈
H, p
u
a
≤
mi
n
v
∈
T
{
p
u
v
}, since a is a NE and the strategy of delaying until all response neighbors of T are connected at a current transmission power level. Let u be the first node in H that joins when (
a
,
b
H
) is played. Then u applies a
r
c to a node in T, and therefore p
u
(
a
,
a
H
∗
)
≥
mi
n
v
∈
T
{
p
u
v
}, which is a contradiction.Leta
=
(
a
u
)
i
∈
N be a strategy for the set of nodes, N, and let T
a be the topology constructed on S
u
⊆
N
u (this topology connects a set of nodes S
u to the u). Let T
S be any subgraph of T
a, which contains the node u, where S
⊂
S
u is the set of involved bidirectional paths.NoticeN
∖
S by S
- and push T
S to a fictitious node u
-
∈
S
-. Define the subgame (
S
-
u
-
,
p
S
), where S
-
u
-
=
S
-
∪
u
- and p
u
v
S
=
p
i
j.Definition 6.
The strategya
∈
A is a subgame prefect Nash equilibrium (SPNE) for the game Γ
(
N
,
p
) if a
-
S is a NE for any subgame (
S
-
u
-
,
p
S
).Recall that not all NE are SPNE and a NE does not construct a NMST. Furthermore, there exist strategies which are not NE but construct NMST onN
u.The necessity of selecting a minimum power level forces the nodes to connect to the topology when the minimum transmission range is available. DefineB
u
=
{
v
∈
N
:
(
v
,
u
)
∈
A
u
∗
,
p
∪
(
v
,
u
)
∈
P
u
,
∀
p
∈
P
v
}
,
u
∈
N, as the set of nodes v such that node u can connect at its lower power level to v and the union of (
v
,
u
) with any shortest bidirectional path from u to v.Definition 7.
The strategya
u
∈
A
u is a Bellman strategy for node u in Γ
(
G
,
p
) if, for any S
∈
2
N
(
u
),(1)
a
u
(
S
)
=
P
∪
(
v
,
u
)
if
v
∈
B
i
∩
S
,
s
∈
P
v
,
p
⊆
dis
otherwise
.LetP
u be the collection of all minimum transmission power from u to v. A profile strategy for the node u
∈
N is a map a
u
:
2
(
u
)
N
→
P
u
∪
{
dis
} such that a
u
(
S
)
=
p illustrates that the node u generates the subgraph of p starting from the last node on a graph p that is a response neighbor of S and ending at node u. Note that no graph was named “dis” and use this symbol for the selection of the unconnected nodes; a
u
(
S
)
=
dis means that node u does not generate any link when the current MST is S.


### 4.2.1. Opportune Moment Adjusting

In the case where each node’s smallest power level constructs a topology, this topology is a MST. However, this action could not construct a topology, and further improvement is necessary to algorithm of the strategy that the nodes will adjust transmission power. Initially, when at a current time of the gameΓ
(
N
,
p
) the minimum power of a node is available, it joins to the topology, by using the “best individual opportunity.” However, when the node does not consider the “best individual opportunity” and wants to wait for connection to the topology, it may have opportunity of a best connection with a minimum power level. Let σ
:
2
N
→
N represent a permutation function that denoted node power level ranking. Furthermore, for each ranking, σ, let f
σ
2
N
→
N represent the function that adopts to every coalition M
∈
2
N the node, u
σ
∈
M
,
f
σ
(
M
)
=
u
σ
∈
(
M
), such that σ
(
u
σ
≤
σ
(
u
)
,
∀
u
∈
M
). The strategies for the aforementioned function are based on the ranking, σ, applied as a tiebreaker to select the nodes that wish to join its neighbors which have the minimum power level. Moreover, given the ranking, σ, when nodes in S are already connected, the best node in M
S
=
{
u
∈
N
∖
S
∣
∃
v
∈
S
,
p
u
v
=
m
S
}
,
f
σ
(
M
S
), is selected to connect to the connected topology.Definition 8.
A ranking of each node,σ, an opportune moment strategy, a
σ
∈
A, for Γ
(
N
,
p
) is denoted as follows:(2)
a
u
σ
(
S
)
=
k
∈
B
u
∩
S
,
if
,
B
u
∩
S
≠
0
v
∈
S
u
,
if
,
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.Recall that, by applying an “opportune moment strategy” profile, more than one node may reach to the existing connected topology at any step of the game, but only one of these response nodes uses its best opportunity. Additionally, a strategy is well defined since, if at the same proceeding time,B
u
∩
S
≠
0 and u
∈
M
S, then B
u
∩
S
=
S
u.Note that the opportune strategy is different from those strategies used by Prim’s algorithm with a ranking; that is,(3)
y
u
σ
(
S
)
=
v
∈
S
u
if
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.The following result states that Bellman profile strategies are NE for the gameΓ
(
G
,
p
) and push dis NMST on N
u and then a profile of opportune moment strategies is a SPNE and induces a NMST on N
u.Theorem 9.
Given a ranking for nodes,σ, a profile of opportune moment strategies for the game Γ
(
G
,
p
) constructs NMST on N
u and is SPNE. On the other hand, if strategy a constructs a NMST on N
u, then ranking of nodes, σ, and a profile of opportune moment strategies, a
σ, exist such that p
u
(
a
)
=
p
u
(
a
σ
) for all nodes u
∈
N.Proof.
To prove that a strategy profile ofa
σ is a SPNE considering the MST T
a
σ, any subgraph T
S of T
a
σ, with bidirectional path on the connected topology, and the set of nodes S
⊂
N generate (
S
i
=
S
∪
i
). Let (
S
-
i
~
,
p
S
) be the corresponding subgame. Assume that node u
∈
S deviates from strategy a
σ by using a strategy a
u. One of the following inductions occurs.(1)
Either
(a)
B
u
∩
S
i
=
0 and u
∉
M
S or
(b)
B
u
∩
S
i
=
0
,
u
∈
M
S, and f
σ
(
M
S
)
≠
u.
If nodeu is refused from a
σ by applying a
u, which consists of connection to any node v
∈
S of the certain topology, then (
a
σ
;
a
u
)
u
(
S
)
=
a
u
(
S
)
=
v
∈
S and node u higher transmission power level p
u
(
a
σ
,
a
u
)
=
p
u
v
≥
m
u
S. Since every node in S, except for node u, uses a
-
(
S
∪
{
u
}
)
σ, if the node u is not refused from a
u
σ and remains disconnected from the topology, it waits for its best opportunity to connect to the topology with a minimum power level. Therefore, if the node u uses an opportunity, a
u
σ, it could be reached at this stage with maximum power level p
u
(
a
σ
)
=
m
u
R
≤
m
u
S
≤
p
u
v
=
p
u
(
a
σ
,
a
u
).
(2)
B
u
∩
S
i
=
0
,
u
∈
M
S
,
and
f
σ
(
M
S
)
=
u, but either
(i)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
v
∉
S
i
u or
(ii)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
dis.
Obviously, nodeu is not improved by joining to v
∉
S
u. On the other hand, if the node u is refused from a
σ by applying a
u, which consists of nonconnected nodes, the rest of the nodes play a
S
∪
u
σ and the minimum transmission level does not appear, since nodes in M
S connect at their minimum power level, which are not less than m
u
S. Therefore, node u does not improve its opportunity strategy and loses its best opportunity.
(3)
B
u
∩
S
i
≠
0, but either
(a)
a
σ
;
a
u
u
S
i
=
a
u
S
i
=
v
∉
B
u
∩
S
i
u, or
(b)
a
σ
;
a
u
u
S
i
=
a
u
(
S
i
)
=
dis.
SinceB
u
=
{
v
∈
N
∖
{
u
}
∣
a
u
v
≤
a
u
k
,
∀
k
∈
N
,
k
≠
u
}, then node u is not improved by joining v
∉
B
u
∩
S, nor by waiting for a minimum power level and therefore, p
(
a
σ
;
a
u
)
≥
p
u
(
a
σ
).Conversely, leta be a strategy for the set of nodes, N, that construct a NMST on graph G. Let T
a be the constructed NMST topology. Since, by using Prim’s algorithm, all minimum transmission power levels in the topology can be constructed, consider the ranking of the nodes, σ, that reflects how the nodes are reached by Prim’s algorithm when T
a is the result. Consider also the profile of opportune moment strategies a
σ. Obviously, p
u
(
a
)
≥
p
u
(
a
σ
) for all u
∈
N. Furthermore, the equality holds since if at a stage when the nodes in S
u
=
S
∩
u are connected the nodes in M
S use their minimum transmission to connect to the topology. Therefore, p
u
(
a
)
=
p
u
(
a
σ
) for all nodes that, when using a
σ, do not use their best individual opportunity. The equality holds also for those nodes that, by playing a
σ, use their best individual opportunity when it is not their best collective opportunity. This happens due to the fact that they use their minimum transmission power which is already available.Note that, in the converse part of Theorem9, it can be concluded that the allocation of costs provided by any profile of strategies inducing a MCST (which is not necessarily NE) can always be attained by a profile of opportune moment strategies.Algorithm1 formulate the description of NMST topology control Γ
(
N
,
p
).Algorithm 1:Noncooperative MST Γ
(
p
max
⁡
→
p
u
) algorithm.
Data: nodeu's one and one-hop and two hop neighborhood list
Output: nodeu's power range p
u
(1)m
=
1
(2)  Construct the undirected, complete graphK
N over N with edge weights p
(
u
,
v
) for all
{
u
,
v
∈
N
}. // Initialize each sensor node transmission power to max
(3)  Find a minimum weight spanning treeT of K
N
(4)  For allv
∈
N let p
u
v
=
max
⁡
{
w
v
,
u
∥
{
v
,
u
}
∈
T
}
(5)while:  P
u is not strong Nash equilibrium do
(6)m
=
m
+
1
(7)for  u
∈
N in ascending neighborhood list of ID do
(8)  select best individualp
u
′
=
p
u
v
∈
P
u
(9)
if  u can connect by Bellman strategy the node k with reverses link
(10)Γ
(
G
,
p
)
=
p
(
a
u
(
S
)
)
(11)else  d
i
s
(12)if Bellman profile strategy is NE for the game Γ
(
G
,
p
) and pushes dis to join MST on N
A ranking of the sensor nodes,σ, an opportune moment strategy, a
σ, for Γ
(
G
,
p
)
(13)endif
(14)endif
(15)p
u
′
=
arg
⁡
max
⁡
Γ
(
G
,
p
u
(
a
σ
)
)
(16)endfor
(17)endwhile


## 4.2.1. Opportune Moment Adjusting

In the case where each node’s smallest power level constructs a topology, this topology is a MST. However, this action could not construct a topology, and further improvement is necessary to algorithm of the strategy that the nodes will adjust transmission power. Initially, when at a current time of the gameΓ
(
N
,
p
) the minimum power of a node is available, it joins to the topology, by using the “best individual opportunity.” However, when the node does not consider the “best individual opportunity” and wants to wait for connection to the topology, it may have opportunity of a best connection with a minimum power level. Let σ
:
2
N
→
N represent a permutation function that denoted node power level ranking. Furthermore, for each ranking, σ, let f
σ
2
N
→
N represent the function that adopts to every coalition M
∈
2
N the node, u
σ
∈
M
,
f
σ
(
M
)
=
u
σ
∈
(
M
), such that σ
(
u
σ
≤
σ
(
u
)
,
∀
u
∈
M
). The strategies for the aforementioned function are based on the ranking, σ, applied as a tiebreaker to select the nodes that wish to join its neighbors which have the minimum power level. Moreover, given the ranking, σ, when nodes in S are already connected, the best node in M
S
=
{
u
∈
N
∖
S
∣
∃
v
∈
S
,
p
u
v
=
m
S
}
,
f
σ
(
M
S
), is selected to connect to the connected topology.Definition 8.
A ranking of each node,σ, an opportune moment strategy, a
σ
∈
A, for Γ
(
N
,
p
) is denoted as follows:(2)
a
u
σ
(
S
)
=
k
∈
B
u
∩
S
,
if
,
B
u
∩
S
≠
0
v
∈
S
u
,
if
,
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.Recall that, by applying an “opportune moment strategy” profile, more than one node may reach to the existing connected topology at any step of the game, but only one of these response nodes uses its best opportunity. Additionally, a strategy is well defined since, if at the same proceeding time,B
u
∩
S
≠
0 and u
∈
M
S, then B
u
∩
S
=
S
u.Note that the opportune strategy is different from those strategies used by Prim’s algorithm with a ranking; that is,(3)
y
u
σ
(
S
)
=
v
∈
S
u
if
u
∈
M
S
,
f
σ
(
M
S
)
=
u
dis
otherwise
.The following result states that Bellman profile strategies are NE for the gameΓ
(
G
,
p
) and push dis NMST on N
u and then a profile of opportune moment strategies is a SPNE and induces a NMST on N
u.Theorem 9.
Given a ranking for nodes,σ, a profile of opportune moment strategies for the game Γ
(
G
,
p
) constructs NMST on N
u and is SPNE. On the other hand, if strategy a constructs a NMST on N
u, then ranking of nodes, σ, and a profile of opportune moment strategies, a
σ, exist such that p
u
(
a
)
=
p
u
(
a
σ
) for all nodes u
∈
N.Proof.
To prove that a strategy profile ofa
σ is a SPNE considering the MST T
a
σ, any subgraph T
S of T
a
σ, with bidirectional path on the connected topology, and the set of nodes S
⊂
N generate (
S
i
=
S
∪
i
). Let (
S
-
i
~
,
p
S
) be the corresponding subgame. Assume that node u
∈
S deviates from strategy a
σ by using a strategy a
u. One of the following inductions occurs.(1)
Either
(a)
B
u
∩
S
i
=
0 and u
∉
M
S or
(b)
B
u
∩
S
i
=
0
,
u
∈
M
S, and f
σ
(
M
S
)
≠
u.
If nodeu is refused from a
σ by applying a
u, which consists of connection to any node v
∈
S of the certain topology, then (
a
σ
;
a
u
)
u
(
S
)
=
a
u
(
S
)
=
v
∈
S and node u higher transmission power level p
u
(
a
σ
,
a
u
)
=
p
u
v
≥
m
u
S. Since every node in S, except for node u, uses a
-
(
S
∪
{
u
}
)
σ, if the node u is not refused from a
u
σ and remains disconnected from the topology, it waits for its best opportunity to connect to the topology with a minimum power level. Therefore, if the node u uses an opportunity, a
u
σ, it could be reached at this stage with maximum power level p
u
(
a
σ
)
=
m
u
R
≤
m
u
S
≤
p
u
v
=
p
u
(
a
σ
,
a
u
).
(2)
B
u
∩
S
i
=
0
,
u
∈
M
S
,
and
f
σ
(
M
S
)
=
u, but either
(i)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
v
∉
S
i
u or
(ii)
(
a
σ
;
a
u
)
u
(
S
i
)
=
a
u
(
S
i
)
=
dis.
Obviously, nodeu is not improved by joining to v
∉
S
u. On the other hand, if the node u is refused from a
σ by applying a
u, which consists of nonconnected nodes, the rest of the nodes play a
S
∪
u
σ and the minimum transmission level does not appear, since nodes in M
S connect at their minimum power level, which are not less than m
u
S. Therefore, node u does not improve its opportunity strategy and loses its best opportunity.
(3)
B
u
∩
S
i
≠
0, but either
(a)
a
σ
;
a
u
u
S
i
=
a
u
S
i
=
v
∉
B
u
∩
S
i
u, or
(b)
a
σ
;
a
u
u
S
i
=
a
u
(
S
i
)
=
dis.
SinceB
u
=
{
v
∈
N
∖
{
u
}
∣
a
u
v
≤
a
u
k
,
∀
k
∈
N
,
k
≠
u
}, then node u is not improved by joining v
∉
B
u
∩
S, nor by waiting for a minimum power level and therefore, p
(
a
σ
;
a
u
)
≥
p
u
(
a
σ
).Conversely, leta be a strategy for the set of nodes, N, that construct a NMST on graph G. Let T
a be the constructed NMST topology. Since, by using Prim’s algorithm, all minimum transmission power levels in the topology can be constructed, consider the ranking of the nodes, σ, that reflects how the nodes are reached by Prim’s algorithm when T
a is the result. Consider also the profile of opportune moment strategies a
σ. Obviously, p
u
(
a
)
≥
p
u
(
a
σ
) for all u
∈
N. Furthermore, the equality holds since if at a stage when the nodes in S
u
=
S
∩
u are connected the nodes in M
S use their minimum transmission to connect to the topology. Therefore, p
u
(
a
)
=
p
u
(
a
σ
) for all nodes that, when using a
σ, do not use their best individual opportunity. The equality holds also for those nodes that, by playing a
σ, use their best individual opportunity when it is not their best collective opportunity. This happens due to the fact that they use their minimum transmission power which is already available.Note that, in the converse part of Theorem9, it can be concluded that the allocation of costs provided by any profile of strategies inducing a MCST (which is not necessarily NE) can always be attained by a profile of opportune moment strategies.Algorithm1 formulate the description of NMST topology control Γ
(
N
,
p
).Algorithm 1:Noncooperative MST Γ
(
p
max
⁡
→
p
u
) algorithm.
Data: nodeu's one and one-hop and two hop neighborhood list
Output: nodeu's power range p
u
(1)m
=
1
(2)  Construct the undirected, complete graphK
N over N with edge weights p
(
u
,
v
) for all
{
u
,
v
∈
N
}. // Initialize each sensor node transmission power to max
(3)  Find a minimum weight spanning treeT of K
N
(4)  For allv
∈
N let p
u
v
=
max
⁡
{
w
v
,
u
∥
{
v
,
u
}
∈
T
}
(5)while:  P
u is not strong Nash equilibrium do
(6)m
=
m
+
1
(7)for  u
∈
N in ascending neighborhood list of ID do
(8)  select best individualp
u
′
=
p
u
v
∈
P
u
(9)
if  u can connect by Bellman strategy the node k with reverses link
(10)Γ
(
G
,
p
)
=
p
(
a
u
(
S
)
)
(11)else  d
i
s
(12)if Bellman profile strategy is NE for the game Γ
(
G
,
p
) and pushes dis to join MST on N
A ranking of the sensor nodes,σ, an opportune moment strategy, a
σ, for Γ
(
G
,
p
)
(13)endif
(14)endif
(15)p
u
′
=
arg
⁡
max
⁡
Γ
(
G
,
p
u
(
a
σ
)
)
(16)endfor
(17)endwhile


## 4.3. Update Phases

Under algorithm NMST, nodes’ selection of transmission power range in each iteration redefines its neighbor. Since a particular node adjusts its transmission power to the current power level, other neighbors are made aware of this adjustment by means of sending “Hello Message.” Each node sends messages to its neighbor order list every time there is a change in its 1-hop neighbor. Denote that it is necessary for every node to broadcast updates only to those nodes that are within their two-hop order list. The idea of two-hop neighbor is capable of minimizing the overhead cost from increasing with network size. Upon receiving these messages, other nodes update their neighbor order lists. Every node responds to the topology change by adjusting an adequate transmission power range.


## 5. Analysis of NMST Algorithm

Based on Theorem9 the OMS converges to energy-efficient topology. The foundation of this algorithm consists of the following results: when nodes utilize the OMS, the process converges to a NE that generates an energy-efficient topology. Recall from Theorem 2, which construct the topology, where the power thresholds between two nodes is weight functions of the current network. The NMST considers weight function to be defined as follows.Definition 10.
A topologyG is a NMST G
NMST if it is a MST and consists of any link generated by bidirectional properties.Based on that, Lemmas11 and 12 present main results in which there exists strategy profile that is not NE but constructs energy-efficient topology.Lemma 11.
Let the noncooperative gameΓ
(
N
,
p
) where nodes utilize the OMS under Definition 8 denote ranking σ for each node. For all u
∈
N, a
u
σ be an opportune moment for node u and y
u
σ be the strategy given in Definition 3. Then, p
u
(
a
,
a
u
σ
)
≤
p
u
(
a
,
y
u
σ
) for all a
∈
A.Proof.
Leta
∈
A be a strategy for the list of nodes N. If, when a node u is refused from strategy a by applying a
σ, at the end of the game node u still is disconnected, then it also will be disconnected if it uses a
-
σ. On the other hand, by refusing from a by using a
σ, node u connects when the number of nodes S
⊂
N is already connected. Furthermore, in this situation, p
u
(
a
,
a
u
σ
)
=
p
u
v for some v
⊂
S. If v
∈
B
u
∩
S, then p
u
v
=
p
u
(
a
,
a
u
σ
)
≤
p
u
(
a
,
a
-
u
σ
), since p
u
v is minimum transmission power that node u can use. Otherwise, v
∈
S using a
-
σ is already connected. Moreover, p
u
v
=
p
u
(
a
,
a
u
σ
)
=
p
u
(
a
,
a
-
u
σ
), node u connected v
′
∈
S
′, and p
u
v
=
p
u
v
′. For simplicity, consider the topology with two available rankings of the nodes σ
1 and σ
2, where σ
1
(
1
)
=
1, σ
1
(
2
)
=
0.02, σ
2
(
1
)
=
0.02, and σ
2
(
2
)
=
0.02. f
σ generates two minimum spanning trees by a
-
σ
1
:
T
1
a
-
σ
1
=
{
(
0,1
)
,
(
1,2
)
} and T
2
a
-
σ
1
=
{
(
0,1
)
,
(
0,2
)
}. On the other hand, a
-
σ
2
:
T
1
a
-
σ
2
=
{
(
0,2
)
,
(
1,2
)
} and T
2
a
-
σ
2
=
{
(
0,1
)
,
(
0,2
)
} constructed two minmum spaning tree by a
-
σ
2 as shown in Figure 1. However, if the nodes adjust strategy of opportune moment, then only one MST is generated regardless of ranking T
a
-
σ
1
,
T
a
-
σ
2
=
{
(
0,1
)
,
(
0,2
)
}.
The example in Figure2(a) considers the topology with different transmission power. Without loss of generality, that G
max
⁡ is a connected topology with 4 nodes. Furthermore, the strategy used by node 1 is a
-
σ; the strategy of node 2 generates connection to node 3 when node 3 is already connected and remains disconnected meanwhile. If node 3 uses an opportune moment strategy, then the connected topology as shown in Figure 2(b) is generated, and it uses transmission power 0.018. However, if node 3 uses a
-
1
σ it will be disconnected when the game ends, as shown in Figure 2(c).Figure 1
Illustration of NMST based on ranking finds minimum power level for three nodes.
(a)
(b)Figure 2
Illustration of NMST based on ranking finds the minimum power level for four nodes.
(a)
(b)
(c)Lemma 12.
NMST reduces maximum transmission power of every given sensor node in the connected network.Proof.
Let the idea behind the proof be the rule that NMST reduces the link-cost of the connected topology. Furthermore, this explanation is shown by contradiction. Obtain, in contrast, that there exists different spanning treeT that reduces the link-cost. Let d
t
max
⁡
=
arg
⁡
max
⁡
u
v
∈
T
c
(
u
v
) and d
nmst
max
⁡
=
arg
max
⁡
u
v
∈
NMST
p
(
u
v
), where p is the link-cost function. By this contradiction, p
(
d
nmst
max
⁡
)
<
p
(
d
t
max
⁡
). The nodes are divided into two lists T
1 and T
2 in NMST by deleting d
nmst
max
⁡ from the connected topology. Since T is a spanning tree, a minimum transmission level link is determined as p
′
∈
T by combining T
1 and T
2 and constructing a new spanning tree T
′. Because d
t
max
⁡ is the link in T with the maximal link weight, there is p
(
d
nmst
max
⁡
)
<
p
(
d
′
)
<
p
(
d
t
max
⁡
). Since a tree T
′ is essentially generated from the NMST, ∑
p
∈
NMST
p
(
d
)
<
∑
d
∈
T
′
p
(
d
), and a contradiction is obtained. Therefore, NMST is a connected topology with the minimum power level.The following result states that an opportune moment strategy profile is a SPNE and constructs a NMST onN. Furthermore, with an initial topology G
max
⁡ generated by the power level p
max
⁡, the algorithm converges to a subgraph, G
S, of the NMST.Theorem 13.
The communication complexity of the NMST algorithm isO
(
n
), where n is the number of sensor nodes in the networks.Proof.
Based on initialization phase of NMST in Section4.1, it obviously shows that each sensor node requires exchanging information with its neighbors twice for its individual information collection which include neighbor request message and neighbor list message. Thus, the total information exchange for their individual information collection in this phase is 2
n. And there is not any information exchange in NMST algorithm. The communication complexity of NMST algorithm is on the order of O
(
n
). However, DIA and OTTC, although distributed, require large information exchange; as it update transmission power adjustment, which to know the topology is connected or not to all other node in the networks, which complexity is on the order of O
(
n
2
).


## 6. Simulation Results

Optimum transmission power selection in a wireless sensor network has some additional issues over ad hoc topology control. These issues are related to limited battery resource. In this section, the NMST is compared with two existing topology control algorithms, including OTTC [16] and DIA [18]. Simulations are implemented by using Matlab. In the experimental nodes are randomly deployed in a (
500
×
500
) size. The minimum power p
u
v between nodes u and v can be characterized, as p
u
v
s
=
p
t
(
4
π
)
2
d
i
j
2
L
/
G
t
G
r
λ
2 [14]. Other settings are listed in Table 1 [14].Table 1
Parameters and values are used for the proposed algorithm.
Parameter
Value
Simulation area
500× 500
The antenna gain of the receiverG
r
7
×
1
0
-
10 w
The system lossL
1
The wave lengthλ
0.1224 m
The antenna gain of the transmissionG
t
1
Number of sensor nodes
30
,
…
,
80
The maximal transmission distance,d
max
⁡
150 (m)With the experimental setup as illustrated in Table1, two scenarios are considered in which each scenario consists of the following. The first scenario is derived from the proposed network topology control and current topology control to show the drawback of the current topology with 70 nodes. In the second scenario, the number of nodes in the network area changes from 30 to 80. In addition, all data are an average of 100 experimental runs. The following metrics are considered for comparative evaluation of the abovementioned algorithms: node degree, transmission range, and stretch factor and power stretch mean psm. The sf of node u and v is determined as sf
(
u
,
v
)
=
p
t
c
(
u
,
v
)
/
p
(
u
,
v
) where p
t
c
(
u
,
v
) represents the energy cost of the shortest path between nodes u and v on the topology network of G
t
c and the initial graphs, respectively [16]. In addition, the psm is determined as psm
(
u
,
v
)
=
∑
u
,
v
∈
V
‍
p
t
c
(
u
,
v
)
/
p
(
u
,
v
)
/
n
2 where n denotes the number of nodes [16]. The maximum transmission power levels for each node in initial topology are 150 m.The algorithms DIA, OTTC, and NMSTs shown in Figure3, respectively, are extracted based on original graph. However, the DIA and OTTC topology as shown in Figures 3(a) and 3(b) are sparser, as nodes are working at transmission power level less than their maximal power. Figure 3 illustrates that the connected topology constructed by OTTC and DIA appears (the node in a circle), which use high transmission power for constructing topology. On the other hand, NMST constructs topology as illustrated in Figure 3(c) which used minimum transmission power level. Minimum transmission power level can minimize energy consumption significantly. The figure shows that the constructed topology by NMST has less transmission power level than the executed OTTC and DIA algorithms. Furthermore, the figure shows that NMST, OTTC, and DIA algorithms guarantee connectivity of network as there exists a reverse link within each neighbor node; besides, NMST constructs an efficient topology.Figure 3
OTTC, DIA, and NMST.
(a)
OTTC topology
(b)
DIA topology
(c)
NMST topologyThe mean node degree and maximum degree of the nodes in the OTTC, DIA, and NMST topologies are illustrated in Figure4. In addition, each node should, at least, have a minimum one degree to preserve network connectivity. The results in Figure 4(b) show that the maximum degree for NMST is lower than that for OTTC and DIA. Furthermore, the slope of the maximum degree (Figure 4(b)) curve for the NMST topology grows very slightly as the number of nodes increases. The maximum node degree for the OTTC and DIA topologies varies around 6.9 and 5.2, respectively, and, for NMST, is 4.462. The mean degree for DIA and NMST algorithms is constant at approximately 2.1143 and 2.233, respectively. However, the mean node degree and maximum node degree of OTTC are higher than those of NMST and DIA algorithms as shown in Figures 4(a) and 4(b), respectively. Although with considering the maximum mean degree value (about 2.1) the node degree of NMST algorithm is not high. It implies that the NMST is robust in some sense; this is mainly because NMST uses minimum transmission power levels compared to OTTC and DIA and helps to improve the operational lifetime of the topology. On the other hand, maximum node degree in OTTC and DIA is higher than in NMST, in which each node uses high transmission level to construct topology.Figure 4
Maximum node degree of OTTC, DIA, and NMST.
(a)
Average node degree
(b)
Maximum node degreeThe experimental results in Figure5 show the mean, maximal, and minimum transmission power level for NMST, OTTC, and DIA algorithms which are extracted from the original graph. Figures 5(a) and 5(b) show the maximum and average transmission power level in NMST are lower than in OTTC and DIA algorithms. Moreover, NMST uses minimum transmission power levels which can minimize the energy consumption of nodes. The average and maximum transmission level reduce as the number of nodes increases. The average transmission level in the NMST topology is the smallest and compared to the DIA and OTTC algorithms is reduced by about 9
% and 12.5
%, respectively. Additionally, as shown in Figure 5(c), the minimum transmission level in the OTTC topologies is less than NMST 0.0023 and 0.0032, respectively. Figure 5(c) shows that the NMST algorithm does not have fewer transmission power levels. It illustrates that each node wants to connect to those nodes which are already connected and selects minimum transmission power levels. However, it needs to increase its transmission power levels. The power required to transmit messages between nodes increases with an exponent a
>
2. Furthermore, Figure 5 illustrates that transmission power level is decreased as the number of nodes increases.Figure 5
Mean, maximum, and minimum transmission range of OTTC, DIA, and NMST.
(a)
Maximum transmission power level
(b)
Average transmission power level
(c)
Minimum transmission power levelFigures6(a) and 6(b) illustrate the stretch factor (sf) and power stretch mean (psm) values over topology. Results show that the mean of the sf for the NMST topology in topology is 0.9, while these values for the DIA and OTTC connected topology are 1.2 and 1.1, respectively. The psm of the NMST, DIA, and OTTC algorithms is approximately equivalent and has small difference and does not exceed 0.001. Furthermore, the psm decreases while the number of nodes increases. Also the NMST connected topologies have the best sf compared to DIA and OTTC. Moreover, it shows that the NMST topology can construct an energy-efficient connected topology and helps to improve the network operational lifetime.Figure 6
(a) Stretch factor of OTTC, DIA, and NMST. (b) Power stretch mean of OTTC, DIA, and NMST.
(a)
Stretch factor
(b)
Power stretch mean


## 7. Summary

Most of the previous topology control algorithms have been used individually to select transmission power level, which cannot optimize the network topology. Moreover, many mechanisms did not consider the energy usage and robustness and they select very high or extremely low power levels, which results in reduced network performance and operational lifetime. In this paper, a noncooperative MST topology control (NMST) is proposed which can adjust minimum power levels. The NMST algorithm considers reducing a transmission power level while preserving network connectivity. It adaptively selects a subset of nodes to be individual opportunity from all nodes within the network. Furthermore, the main goal of the topology control, when minimizing the transmission power levels, is the network connectivity. Each node can join the topology and find the bidirectional path between its neighbors based on individual opportunity. In order to address this problem, the NMST algorithm is able to minimize the transmission power level and preserve network connectivity. In another point of view, optimum transmission power level can significantly minimize energy consumption.



---

*Source: 754940-2015-05-05.xml*