Sage Journals: Discover world-class research

Abstract

Power assignment in wireless ad hoc networks is an important issue of topology control which assigns power for each wireless node so that the induced communication graph satisfies some desired properties such as the connectivity and the energy spanner. In this paper, we study the problem of power assignment in order that its induced communication graph meets the following properties: (1) it is an energy-t-spanner which is energy efficient; (2) it is k-fault resistant which can withstand up to $k - 1$ node failures where k ⩾ 1; (3) the interference is minimal. We propose algorithms to address this problem. Both the theoretic analysis and the simulations in the paper prove that our algorithms can induce a k-fault resistant energy spanner and furthermore the interference is minimized. To the best of our knowledge, this is the first paper to study the power assignment problem simultaneously considering spanner properties, the fault tolerance, and the interference reduction.

1. Introduction

Ad hoc networks are formed by autonomous nodes communicating via radio without any additional backbone infrastructure. Ad hoc networks have received significant attention in recent years due to their potential civilian and military applications. In wireless ad hoc networks, each node has limited resources such as energy, computing power, storage capacity; there are more challenges and problems compared with traditional fixed infrastructure networks.

A fundamental problem in wireless ad hoc network is to find a power assignment so that the induced communication graph can satisfy some properties such as connectivity and energy spanner.

An energy-t-spanner $G^{'}$ is a subgraph of G, such that for any two nodes u and v in $G^{'}$ , there exists a path from u to v, whose energy is at most t times the energy of a minimum-energy path from u to v in the original communication graph G. The constant t is called the power stretch factor. A small power stretch factor implies low energy spent by relay nodes in propagating a message, which is extremely useful for prolonging the lifetime of the network. Due to limited power sources, the idea of energy-t-spanner becomes an important design consideration in ad hoc networks. Much effort has been devoted to finding a power assignment that the induced graph is energy-t-spanner [1–3].

Nodes in a wireless network are typically battery powered, and it is infeasible or unable to recharge the device. Due to constrained power capacity, hostile deployment environment, and other factors, node failures are more likely to happen, which might cause network partitions and badly degrade network performance. Therefore, it is important to construct k-fault resistant topologies which can withstand up to $k - 1$ node failures or we can say it is k-connected. Shpungin and Segal [4] studied how to find a power assignment that the induced communication graph is energy spanner and fault tolerant.

In wireless networks, a node is not able to receive correct data from its neighbor if any of other neighbors is transmitting at the same time. This mutual disturbance of communication is called interference. Interference which causes collisions and retransmissions has a negative impact on prolonging network lifetime in wireless networks. Reducing interference in wireless network leads to fewer collisions and packet retransmissions, which indirectly extends the lifetime of the network and improves network performance. Reducing the interference in wireless networks is consequently considered one of the foremost goals [5]. In order to make topology withstand up to $k - 1$ node failures, node's transmission power must be improved. And interference will increase dramatically if the transmission power improved improperly. However, previous work studies the fault-tolerant spanner problem but ignores interference reduction. In this paper, we will study the power assignment problem that the induced communication graph is k-fault resistant and energy-t-spanner; in addition, the interference is minimized.

The rest of the paper is organized as follows. Section 2 presents an overview of previous related work. In Section 3, we state the problem studied in this paper. The models will be presented in Section 4. Then the details of our power assignment algorithms and simulation results will be given in Section 5. Finally, we conclude this paper in Section 6.

2. Related Work

To assign power to each node of a wireless network so that the induced communication graph can satisfy some desired properties (such as connectivity, spanner) is an important research topic. Chew [6] first introduced the concept of spanners. Recently, several papers focus on dealing with the problem of power assignment simultaneously with spanning properties.

Wang and Li [1] first studied how to find a power assignment that the induced communication graph is energy spanner with objectives that minimizes the maximum node power and the total energy consumption (also referred to as the cost of the power assignment $c (p)$ ). They also presented two heuristics for the construction of a low cost power assignment with an energy spanner property for unit disk graphs.

Shpungin and Segal [2] studied the spanner problem from a theoretical point of view under two optimization objectives: minimizing the cost of the power assignment and keep the spanner property. They studied both energy spanner and distance spanner. For the energy spanner model, they present a basic construction of a power assignment p, so that the resulting network is an energy-2-spanner with a total energy of at most O( $\log n$ ), the optimum cost power assignment $c (p^{*})$ in $O (n^{4} \log n)$ , where n is the number of nodes in the network, $p^{*}$ denote an optimal power assignment; that is, a power assignment of minimum cost, for which the induced communication graph is strongly connected.

Abu-Affash et al. [3] studied the minimal energy spanner problem, they proved that for any constant $t > 1$ , one can compute in $O (n^{2} \log n)$ time a planar energy-t-spanner $G^{'}$ , such that the cost of power assignment $c (p)$ implied by $G^{'}$ is at most $2 (1 + 2 / (t - 1)) \times c (p^{*})$ , where $p^{*}$ is a minimum-cost power assignment.

All these papers study the spanner problem with additional objective of minimizing the total node power. In many scenarios wireless ad hoc networks are deployed in hostile environments where node failures are very likely to happen. In order to keep network connectivity in wireless networks which is a node-failure prone environment, fault tolerant is especially important. Previous works addressing fault tolerance usually construct a k-connected topology by improving node's transmission range greatly; there are some recent works addressing fault tolerance [7–9]. However, in these works addressing fault tolerance fails to consider the spanner of the networks. Shpungin and Segal [4] studied the power assignment problem which combines fault resistance with spanner property. They addressed the minimum power k-fault resistant energy spanner problem (MPkES). For $k \in {1, 2}$ , they proposed several power assignments which obtain a good bicriteria approximation on the total cost and spanner property. For $k > 2$ , they also analyzed a power assignment $P_{k}$ presented in [10] that the result topology after the power assignment $P_{k}$ can satisfy both k-fault resistant and energy spanner property. In order to consider the fault resistant, we only discuss the situation when $k > 2$ . For $k = 2$ , Shpungin and Segal [4] developed a power assignment $p_{2}$ such that the result topology is 2-strongly connected and both the energy and distance stretch factors are 1. It is obvious that all the minimum-energy paths and distance paths are preserved in the resulting topology, or we can say that the transmission range of each node is still large. For $k = 3$ , a power assignment $P_{k}$ is analyzed. As Figure 1 illustrated, firstly, node t determines all the neighbor nodes and let $N_{t}$ be a set of k closest nodes to t. Then the transmission power of node $r_{t}^{*}$ is assigned to be the value that node t can reach the farthest nodes in $N_{t}$ . After the power assignment of $r_{t}^{*}$ , an MST of the original topology is computed, for each edge $e = (t, s)$ of MST increase the range of the nodes in ${N_{t} \cup N}_{s}$ such that each node $t^{'} \in N_{t}$ can reach all nodes in $N_{s}$ , and vice versa. In [4] Shpungin and Segal proved that the result topology after the power assignment of $P_{k}$ is k-fault resistant and an energy spanner of the original topology. In [4], Shpungin and Segal addressed the k-fault resistant energy spanner problem; however, interference is ignored. As can be seen from Figure 1, if any one node of $N_{t} \cup N_{s}$ is working, all the other nodes in $N_{t} \cup N_{s}$ will be interfered.

Figure 1

The process of $P_{k}$ .

Rickenbach et al. [5] argued that reducing the interference in wireless networks is considered one of the foremost goals. Interference which causes collisions and retransmissions has a negative impact on prolonging network lifetime in wireless networks. An interesting combination of fault resistance, energy spanner, and interference reducing is studied in this paper.

3. Problem Statement

In this paper, we study the Interference Minimal Fault-tolerant Energy Spanner ( $IMFES$ ) problem: Let $V = {v_{1}, v_{2}, \dots, v_{n}}$ be a set of n wireless nodes distributed in wireless network. For any $t \geq 1$ , $k \geq 1$ , find a power assignment that its induced communication graph is k-fault resistant energy-t-spanner $G^{'}$ of the original communication graph G. Furthermore, the interference of $G^{'}$ is minimal. More formally, the problem can be defined as follows:

Input: a set of n wireless nodes $V = {v_{1}, v_{2}, \dots, v_{n}}$ , and two real constants $t \geq 1$ , $k \geq 1$ .

Output: a k-fault resistant energy-t-spanner $G^{'} = (V, E^{'})$ of original communication graph G.

Object: minimize the interference in $G^{'}$ .

4. Models

We consider a 2D wireless network that consists of a set V of n wireless nodes distributed in a 2D plane $R^{2}$ . Each node can adjust the transmission range from 0 to $T_{\max}$ and each node has a unique id(such as IP/MAC address). A generic model of an ad hoc network is a unit disk graph (UDG) in a 2D plane. There is an edge $e = (u, v)$ between two nodes u and v if and only if the Euclidean distance $∥ u, v ∥$ between u and v in $R^{2}$ is at most $T_{\max}$ .

When using common path loss model, the signal strength received by a node can be described as ${p / d}^{β}$ , where p is the transmission power used by the sending node, β is a real constant between 2 and 5 depending on the wireless transmission environment, and d is the distance between the pair of communication node. Consequently, the energy cost to send a message of fixed length from node u to node v is ${∥ u, v ∥}^{β}$ . Each node can calculate the distance from its neighbor node by the received power using the signal degradation model. For simplicity, in this paper we assume that β is 2, although our results can be easily extended to any constant.

For two nodes $u, v \in V$ , let $γ (u, v, G)$ denote the minimum energy consumption from u to v in G.

We define the notion of an energy-t-spanner of G.

Definition 1.

A graph $G^{'} = (V, E^{'})$ is an energy-t-spanner of $G = (V, E)$ , if $E^{'} \subseteq E$ , and for each pair $u, v \in V$ , $γ (u, v, G^{'}) \leq t \times γ (u, v, G)$ .

Here, we also give the definition of k-connected used in this paper.

Definition 2.

A graph $G = (E, V)$ is k-connected if for any two vertices u and $v \in V$ , there are k vertex disjoint paths from u to v. Or equivalently, a graph is k-vertex connected if the removal of any $k - 1$ nodes does not partition graph G.

In order to measure the interference, we define the interference model first. Generally, a node v may not correctly decode the transmission from node u if the signal to interference and noise ratio (SINR) perceived by v is below a certain threshold. While this threshold is dependent on various factors like antenna sensitivity of receivers, signal modulation techniques, and other environmental factors, it is well understood that a third node w interferes node v's signal reception from node u if w is located at a nearby position of v and transmitting simultaneously with u. The distance (region) within which a node w interferes another node is called the interference range (region) of w. For simplicity of analysis, we assume that the interference range and the transmission range are the same for any node w. However, the solution is also applicable where the assumption does not hold. All common models of interference define the notion of coverage, which is the number of nodes or edges that are affected by a transmission over a specific link in the induced communication graph. For simplicity, in this paper, the interference of a node v is defined as the number of nodes covered by v with its transmission range.

Definition 3.

The interference value of a single node v is defined as

\begin{matrix} I (v) = | {u ∣ u \in V - {v}, u \in D (v, r_{v})} |, \end{matrix}

(1)

where

D (v, r_{v})

stands for the transmission circle with node v in its center and the transmission radius is

r_{v}

Definition 4.

The interference of an edge $e = (u, v)$ is defined as the number of nodes which are covered by either of the nodes u and v in edge e,

\begin{matrix} I (e) = | {w ∣ w \in D (u, r_{u}) \cup w \in D (v, r_{v}), w \in V} | . \end{matrix}

(2)

Definition 5.

The interference of graph $G = (V, E)$ is defined as the maximum edge interference in G. That is;

\begin{matrix} I (G) = \underset{e \in E}{Max} I (e) . \end{matrix}

(3)

As can be seen in Figure 2, the interference of node u is $I (u) = 3$ , the interference of node v is $I (v) = 4$ , and the interference of edge $e = (u, v)$ is $I (e) = 6$ , where w is an interference node to both u and v, but it will be calculated only once.

Figure 2

Interference of edge (u, v).

Based on these definitions, we will address the problem described in Section 3.

5. Interference Minimal Fault-Tolerant Energy Spanner

In this section, we address the Interference Minimal Fault-tolerant Energy Spanner problem and propose algorithm $IMFES$ , which produces a k-fault resistant energy-t-spanner; furthermore, the interference is minimized.

$IMFES$ first calculates the interference of each edge in the original communication graph according to the interference model and then sorts all edges by ascending order of weight. In order to guarantee the unique outcome of the greedy algorithms that will be proposed in the second step, we have to ensure that two edges with different end nodes have different weights;

$Weight (u_{1}, v_{1}) > Weight (u_{2}, v_{2})$

$⟺ I (u_{1}, v_{1}) > I (u_{2}, v_{2})$

$⟺ I (u_{1}, v_{1}) = I (u_{2}, v_{2}) & & \max {i d (u_{1}), i d (v_{1})} >$

$\max {i d (u_{2}), i d (v_{2})}$

$⟺ I (u_{1}, v_{1}) = I (u_{2}, v_{2}) & & \max {i d (u_{1}), i d (v_{1})} =$

$\max {i d (u_{2}), i d (v_{2})} & & \min {i d (u_{1})$ , $i d (v_{1})} >$

$\min {i d (u_{2}), i d (v_{2})}$ .

In the first step, $IMFES$ computes an interference minimal k-connected graph based on the greedy algorithm. In the second step, $IMFES$ would check all the rest edges which are not added to $G_{IMFES}$ in the first step. To ensure that $G_{IMFES}$ is an energy-t-spanner, an edge $e = (u, v)$ would be added to $G_{IMFES}$ if $γ (u, v, G_{IMFES}) > t \times γ (u, v, G)$ . The detail of IMFES is described as in Algorithm 1.

Algorithm 1

IMFES:

Input:A set Vof n wireless nodes, $t \geq 1, k \geq 1$ .

Output:A k-fault resistant energy-t-spanner.

First Step:

1: Compute original topology $G = (V, E)$

2: For each edge $e \in E$ , compute $I (e)$

3: sort all edges in E by ascending weight.

4: $G_{IMFES} = (V, E_{IMFES} = \emptyset)$

5: For each edge $e = (u, v)$ in $E (G)$

6: if uand vis not kconnected in $G_{IMFES}$

7: $E_{IMFES} = E_{IMFES} \cup {e}$

8: $E (G) = E (G) - {e}$

9: else if all nodes are kconnected in $G_{IMFES}$

10: go to step two

11: end if

12: end for

Second Step:

13: For each edge $e = (u, v) in E (G)$

14: if $γ (u, v, G_{IMFES}) > t \times γ (u, v, G)$

15: $E_{IMFES} = E_{IMFES} \cup {e}$

16: end if

17: end for

18: Return $G_{IMFES}$

5.1. Analyze

In this section, we will prove that the graph induced by $IMFES$ is a k-connected energy spanner with minimal interference. In the first step, $IMFES$ sorts all edges by ascending weight then uses greedy algorithm to construct a k-connected subgraph of original communication graph. Lines 5–12 are a generalized version of Kruskal's algorithm [11] for $k \geq 2$ .

Let the path $P = {u, w_{1}, w_{2}, \dots, w_{n}, v}$ from u to v be represented by an ordered set P of vertices on the path. Let $S_{u v} (G)$ be the sum of pairwise internally vertex disjoint paths from u to v in graph G. Thus, for any path $P_{1}$ , $P_{2} \in S_{u v} (G)$ , we have $P_{1} \cap P_{2} = {u, v}$ .

Lemma 6.

Let $u_{1}$ and $u_{2}$ be two vertices in a k-connected undirected graph G. If $u_{1}$ and $u_{2}$ are k-connected after the removal of edge $(u_{1}, u_{2})$ , then $G - (u_{1}, u_{2})$ is still k-connected.

Proof.

In order to prove $G - (u_{1}, u_{2})$ isk-connected, let $G^{'} = G - (u_{1}, u_{2})$ , and it is equivalent to prove that $G^{'}$ is connected after the removal of any $k - 1$ vertices in $G^{'}$ . Without loss of generality, assume ${u_{1}, u_{2}} \cap {v_{1}, v_{2}} = \emptyset$ (other cases can be proved using a similar approach). We now prove that $v_{1}$ is still connected to $v_{2}$ after removal of the set of any $k - 1$ vertices $W = {w_{1}, w_{2}, \dots, w_{k - 1}}$ , where $w_{i} \in V (G^{'}) - {v_{1}, v_{2}}$ . Let $G^{''}$ be the resulting graph after $(u_{1}, u_{2})$ and the $k - 1$ vertices in W are removed from G. Now we consider two cases.

(1)

There is an edge $(v_{1}, v_{2})$ in G:

since all the paths in $S_{v_{1} v_{2}} (G)$ are pairwise internally vertex disjoint paths, the removal of $(u_{1}, u_{2})$ and the $k - 1$ vertices does not break the path ${v_{1}, v_{2}}$ which contain only one edge $(v_{1}, v_{2})$ . Thus, $v_{1}$ is still connected to $v_{2}$ after removal of the set of any $k - 1$ vertices $W = {w_{1}, w_{2}, \dots, w_{k - 1}}$ .

(2)

There is no edge from $v_{1}$ to $v_{2}$ in G:

according to the definition of $S_{v_{1} v_{2}} (G^{'})$ , it can be got that the removal of $k - 1$ vertices at most breaks $k - 1$ paths in $S_{v_{1} v_{2}} (G^{'})$ . If we can prove that $| S_{v_{1} v_{2}} (G^{'}) | \geq k,$ then $v_{1}$ is still connected to $v_{2}$ after removal of the set of any $k - 1$ vertices $W = {w_{1}, w_{2}, \dots, w_{k - 1}}$ .

For the sake of contradiction, we assume that $| S_{v_{1} v_{2}} (G^{'}) | < k$ . If $| S_{v_{1} v_{2}} (G^{'}) | < k$ , this occurs only when the removal of ${(u}_{1}, u_{2})$ breaks one path $P_{0} \in S_{v_{1} v_{2}} (G)$ , because G is k-connected and $S_{v_{1} v_{2}} (G) \geq k$ . Since $P_{0}$ is internally disjoint with all paths in $S_{v_{1} v_{2}} (G')$ , we have $P_{0} \cap W = \emptyset$ . Thus, $v_{1}$ is connected to $u_{1}$ and $u_{2}$ is connected to $v_{2}$ in $G^{''}$ . We already know that $u_{1}$ and $u_{2}$ are k-connected after the removal of edge $(u_{1}, u_{2})$ , so we can get that $S_{u_{1} u_{2}} (G^{'})$ ≥ k. Since $v_{1}$ is connected to $u_{1}$ and $u_{2}$ is connected to $v_{2}$ , we can get that $| S_{v_{1} v_{2}} (G^{'}) | \geq k$ , which is a contradiction. Therefore, $| S_{v_{1} v_{2}} (G^{'}) | \geq k$ .

We have proved that for any two vertices $v_{1}$ , $v_{2} \in G^{'}$ , $v_{1}$ is connected to $v_{2}$ after the removal of any $k - 1$ vertices from $G^{'} - {v_{1}, v_{2}}$ . Therefore, $G^{'}$ is k-connected.

Lemma 7.

Let G and $G^{'}$ be two undirected simple graphs such that $V (G) = V (G^{'})$ . If G is k-connected, and every edge $(u, v) \in E (G) - E (G^{'})$ satisfies that u is k-connected to v in $G - {(u_{0}, v_{0}) \in E (G) : Weight (u_{0}, v_{0}) \geq Weight (u, v)}$ , then $G^{'}$ is also k-connected.

Proof.

Let $E = E (G) - E (G^{'}) = {(u_{1}, v_{1}), (u_{2}, v_{2}), \dots, (u_{m}, v_{m})}$ be a set of edges in an descending order of interference weight, that is, $Weight (u_{1}, v_{1}) \geq Weight (u_{2}, v_{2}) \geq \dots \geq Weight (u_{m}, v_{m})$ . We define a series of graphs that is subgraphs of $G : G^{0} = G, a n d G^{i} = G^{i - 1} - (u_{i}, v_{i})$ , $i = 1, 2, \dots, m$ . Now we prove the following by induction. (1)

Base: $G^{0} = G$ is k-connected.

(2)

Induction: if $G^{i - 1}$ is k-connected, and $u_{i}$ is k-connected to $v_{i}$ in $G - {(u, v) \in E (G) : Weight (u, v) \geq Weight (u_{i}, v_{i})}$ . Since $G - {(u, v) \in E (G) : Weight (u, v) \geq Weight (u_{i}, v_{i})} \subseteq G^{i - 1} - (u_{i}, v_{i})$ , $u_{i}$ is k-connected to $v_{i}$ in $G^{i - 1} - (u_{i}, v_{i})$ . Applying Lemma 6 to $G^{i - 1}$ , we can prove that $G^{i}$ is still k-connected.

Now we have proved that $G^{m}$ is k-connected. Since $E (G^{m}) \subseteq E (G^{'})$ , $G^{'}$ is also k-connected.

We denote by $G_{IMFES}^{1}$ the graph that produced by $IMFES$ after the first step and by $G_{IMFES}$ the final induced communication graph.

Lemma 8.

$G_{IMFES}^{1}$ is k-connected if G is k-connected.

Proof.

Since edges are inserted into $G_{MIFES}^{1}$ in an ascending order, whether u is k-connected to v at the moment before $(u, v)$ is inserted depends only on the edges of smaller interference weight. Assume that edge $(u_{0}, v_{0})$ is the last edge added into $G_{IMFES}^{1}$ . Therefore, every edge $(u, v) \in E (G) - E (G_{IMFES}^{1})$ satisfies that u is k-connected to v in $G - {(u, v) \in E (G) : Weight (u, v) > Weight (u_{0}, v_{0})}$ . We can prove that $G_{IMFES}^{'}$ preserves the k-connectivity of G by applying Lemma 7.

Theorem 9.

$G_{IMFES}$ is k-connected if G is k-connected.

Proof.

From Lemma 8 we can get that after the first step of IMFES, $G_{IMFES}^{1}$ is k-connected if G is k-connected. While in the second step of IMFES, the only operation is adding edges into $G_{IMFES}^{1}$ . It is obvious that after the second step of $IMFES$ , $G_{IMFES}$ is k-connected if G is k-connected.

Lemma 10.

Let u₁ and u₂ be two vertices in an energy-t-spanner $G_{s}$ of graph G. If $γ (u_{1}, u_{2}, G_{s} - (u_{1}, u_{2})) \leq t \times γ (u_{1}, u_{2}, G)$ after the removal of edge $(u_{1}, u_{2})$ , then $G_{s} - (u_{1}, u_{2})$ is still an energy-t-spanner of graph G.

Proof.

Let $G_{s}^{'} = G_{s} - (u_{1}, u_{2})$ and ${L P}_{u v}$ the minimum-energy path from u to v in G. We prove the following by contradiction. Assume that $G_{s}^{'}$ is not an energy-t-spanner of graph G. Without loss of generality (other cases can be proved using a similar approach), assume ${u_{1}, u_{2}} \cap {v_{1}, v_{2}} = \emptyset$ and $γ (v_{1}, v_{2}, G_{s}^{'}) > t \times γ (v_{1}, v_{2}, G)$ . This occurs only because edge $(u_{1}, u_{2})$ belongs to $L P_{v_{1} v_{2}} (G_{s})$ , the minimum-energy path from $v_{1}$ to $v_{2}$ . Since after the removal of edge $(u_{1}, u_{2})$ , it still has $γ (u_{1}, u_{2}, G_{s}^{'}) \leq t \times γ (u_{1}, u_{2}, G)$ , by substituting edge $e = (u_{1}, u_{2})$ with $L P_{u_{1} u_{2}} (G_{s})$ , it can get $γ (v_{1}, v_{2}, G_{s}^{'}) \leq t \times γ (v_{1}, v_{2}, G)$ which leads to a contradiction.

Theorem 11.

$G_{IMFES}$ is an energy-t-spanner of G.

Proof.

To show that $G_{IMFES}$ meets the spanner property, it is equivalent to prove that for any pair of nodes ${u, v} \in V$ , $γ (u, v, G_{IMFES}) \leq t \times γ (u, v, G)$ .

Let $E_{0} = E (G) - E_{IMFES}$ . We prove the following by contradiction; assume there exists two nodes ${u_{0}, v_{0}} \in V$ , that $γ (u_{0}, v_{0}, G_{IMFES}) > t \times γ (u_{0}, v_{0}, G)$ . Let $p_{0}$ be the minimum-energy path from $u_{0}$ to $v_{0}$ in $G_{IMFES}$ , in order to satisfy that $γ (u_{0}, v_{0}, G_{IMFES}) \leq t \times γ (u_{0}, v_{0}, G)$ , at least one edge $e = (u_{m}, v_{m})$ in $E_{0}$ has to be added into $p_{0}$ , and let $p_{1} = p_{0} + (u_{m}, v_{m})$ . Without loss of generality, assume $γ (u_{0}, v_{0}, G_{IMFES} + (u_{m}, v_{m})) \leq t \times γ (u_{0}, v_{0}, G)$ . According to lines 14–16 of $IMFES$ , it follows that any edge $(u_{i}, v_{j}) \in E_{0}$ satisfies $γ (u_{i}, v_{j}, G_{IMFES}) \leq t \times γ (u_{i}, v_{j}, G)$ . By applying Lemma 10, it can lead $γ (u_{0}, v_{0}, G_{IMFES}) \leq t \times γ (u_{0}, v_{0}, G)$ which leads to a contradiction. Therefore, $G_{IMFES}$ is an energy-t-spanner of G.

Lemma 12.

The interference of $G_{MIFES}^{1}$ is minimized.

Proof.

Let ${S S}_{k} (G)$ be the set of allk-connected subgraphs of G. By Lemma 8 we can get that $G_{IMFES}^{1}$ is also k-connected if G is k-connected. Suppose that $(u, v)$ is the last edge inserted into $G_{IMFES}^{1}$ in the first step. We can get that $Weight (u, v)$ is larger than any edge which has been already inserted into $G_{IMFES}^{1}$ and $I (G_{IMFES}^{1}) = I (u, v)$ . Let $G_{2} = G_{IMFES}^{1} - (u, v)$ , and we can get that $| S_{u v} (G_{2}) | < k$ otherwise; according to the line 6 of algorithm $IMFES$ , edge $(u, v)$ should not be included in $G_{IMFES}$ .

Now consider a graph $C = (V (C), E (C))$ , where $V (C) = V (G)$ and $E (C) = {(u_{0}, v_{0}) \in E (G) : Weight (u_{0}, v_{0}) < Weight (u, v)}$ . If we can prove that C is not k-connected, we will be able to conclude that any subgraph $F \in {S S}_{k} (G)$ must have at least one edge with interference equal to or larger than $I (u, v)$ , which means is $I (G_{IMFES}^{1})$ is minimal interference.

We prove by contradiction that C is not k-connected. Assume that C is k-connected and hence $| S_{u v} (C) | \geq k$ . We have $E (C) ⊄ E (G_{2})$ ; otherwise, $| S_{u v} (G_{2}) | \geq | S_{u v} (C) | \geq k$ which contradict with the definition of $G_{2}$ . Therefore, $E_{0} = E (C) - E (G_{2}) \neq \emptyset$ . Since edges are inserted into $G_{IMFES}^{1}$ in an ascending order, $for all (u_{1}, v_{1}) \in E_{0}$ satisfies that $u_{1}$ is k-connected to $v_{1}$ in $C - {(u_{0}, v_{0}) \in E (C) : Weight (u_{0}, v_{0}) \geq Weight (u_{1}, v_{1})}$ . By Lemma 7, we can prove that u is still k-connected to v after the removal of all edges in $E_{0}$ . This means $| S_{u v} (G_{2}) | \geq k$ , which is a contradiction. So after step one, the interference of $G_{IMFES}^{1}$ is minimized.

Theorem 13.

The interference of $G_{IMFES}$ is minimized.

Proof.

Lemma 12 shows that the interference of $G_{IMFES}^{1}$ is minimized; in order to prove the interference of $G_{IMFES}$ is minimized, we only consider are all the edges added in the second step of IMFES are minimal interference. Assume that edge $(u, v)$ is the last edge inserted into $G_{IMFES}$ in the second step. Let $G_{3} = G_{IMFES} - (u, v)$ ; according to line 14 of IMFES, $G_{3}$ is not an energy-t-spanner.

Assume that F is k-connected energy-t-spanner, $E (G_{IMFES}^{1}) \subseteq E (F)$ and $I (F) < I (G_{IMFES})$ ; it follows that for any edge $(u_{i}, v_{j}) \in E (F), I (u_{i}, v_{j}) < I (u, v)$ . Since edges are checked in an ascending order in the second step of IMFES, it follows that for any edge $(u_{i}, v_{j}) \in E (F) - E (G_{IMFES}^{1})$ , edge $(u_{i}, v_{j})$ is checked before edge $(u, v)$ . Let $E_{1} = E (F) - E (G_{3})$ ; according to the line 14 of IMFES, any edge $(u_{m}, v_{m}) \in E_{1}$ satisfies that $γ (u, v, G_{3}) \leq t \times γ (u, v, G)$ . By applying Lemma 10, it can be got that $G_{3}$ is an energy-t-spanner which is a contradiction.

Thus, The interference of $G_{IMFES}$ is minimized.

Theorem 14.

The time complexity of $IMFES$ is $O (m (n + m))$ and can be $O (m \log m)$ when $k \leq 3$ , where n is the number of vertices and m is the number of edges in the graph.

Proof.

All the edges can be sorted in $O (m \log m)$ time in line 3, where m is the number of edges in the graph. A query on whether two vertices are k-connected can be answered in $O (n + m)$ time for any fixed k by using network flow techniques [12], where n is the number of vertices in the graph. For $k \leq 3$ , there also exits $O (1)$ time algorithms [13]. Therefore, the time complexity of lines 5–12 is $O (m (n + m))$ and can be improved to $O (m)$ for $k \leq 3$ . A query on the minimum-energy path between two nodes can be finished in $O (n^{2})$ using Dijkstra's algorithm [14]. Thus, the time complexity of lines 13–17 is $O ({m n}^{2})$ .

Therefore, the time complexity of $IMFES$ is $O (m (n + m))$ and can be $O ({m n}^{2})$ when $k \leq 3$ .

5.2. Simulations

In this section, we evaluate the performance of $IMFES$ and $P_{k}$ , the power assignment analyzed in [4], by conducting simulations in random networks. The reason why we compare our work with [4] is that [4] is the previous best work closely matches with our work.

We analyze the performance of $IMFES$ with $P_{k}$ using the following evaluation metrics.

Interference

We measure the level of interference of a network based on the interference graph model proposed in Section 4.

Power Stretch Factor

A low value of power stretch factor implies low energy spent by relay nodes in propagating a message, or we can say that this topology is energy efficient.

We will evaluate $IMFES$ and $P_{k}$ under different fault tolerance requirements: $k = 2$ and $k = 3$ . We also evaluate IMFES under different values of parameter t. The parameter t can affect the power stretch factor of the resulting topology and also have an impact on the network interference reduction.

In our experiments, we randomly generate a set Vof n wireless nodes in a $1000 \times 1000$ square, only if the original communication graph is k-connected and then we run these algorithms. The maximum transmission range R is set to 250; the power constant of path loss exponent β is set to 2. We vary the number of node from 50 to 175. Each result is the average of 100 runs.

Figure 3 shows the average edge interference of the resulting 2-connected topologies induced by the power assignment $P_{2}$ and IMFES. As Figure 3 shows, the average edge interference of the topology induced by IMFES is much lower then the topology induced by $P_{2}$ , especially when $t = 3$ . When the number of nodes increases, the interference of the topology induced by $P_{2}$ increases dramatically, while IMFES can keep the interference at a low level no matter what the value of t is.

Figure 3

Average edge interference when the induced topologies are 2-connected.

Figure 4 shows the average edge interference of the resulting 3-connected topologies induced by the power assignment $P_{k}$ and $IMFES$ . Figure 4 shows that IMFES outperforms $P_{k}$ , which is almost the same result as Figure 3 shows. From Figures 3 and 4, we can also conclude that the larger the parameter t is, the lower the value of edge interference will be in the topology induced by IMFES, that is because more edges would be kept in the resulting topology in order to achieve a lower spanner property. More edges are kept in a topology which implies that nodes in this topology have a larger transmission range; consequently, the interference of the network increases.

Figure 4

Average edge interference when the induced topologies are 3-connected.

Figures 5 and 6 show the power stretch factor of the resulting topologies induced by $P_{2}$ / $P_{k}$ and IMFES under different fault tolerance requirements: $k = 2$ and $k = 3$ . The power stretch factors of all the topologies are less than 3, which means that they are energy efficient.

Figure 5

Power stretch factor when the induced topologies are 2-connected.

Figure 6

Power stretch factor when the induced topologies are 3-connected.

From Figures 3 to 4, we have got that the smaller the parameter t is, the larger the value of edge interference will be in the topology induced by IMFES. Figures 5 and 6 show that the smaller the parameter t is, the smaller the power stretch factor will be in the topology induced by IMFES. Therefore, there is a tradeoff between energy efficient and interference reduction.

6. Conclusion

In this paper, we study how to find a power assignment that the induced communication graph is k-fault resistant energy-t-spanner, in addition that the interference is minimal in it. We propose IMFES to address this problem in two-dimensional wireless ad hoc networks. To the best of our knowledge, this is the first paper to study the problem. We also prove that the communication graph induced by IMFES is an interference minimal k-connected energy-t-spanner, and the energy stretch factor $t (t ⩾ 1)$ can be a low value, which means that the induced communication graph is energy efficient.

Footnotes

Acknowledgments

This work was partly supported by the National Natural Science Foundation of China (no. 61272061, no. 61202289, and no. 61003305), the Fundamental Research Funds for the Central Universities of China (no. 531107040263), and Hunan Natural Science Foundation of China (no. 10JJ5069).

References

Wang

X. Y.

Minimum power assignment in wireless ad hoc networks with spanner property

Journal of Combinatorial Optimization 2006 11 1 99 112

2-s2.0-32944470651

10.1007/s10878-006-5980-0

Shpungin

Segal

Near optimal multicriteria spanner constructions in wireless ad-hoc networks

Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

163 171

2-s2.0-70349656452

10.1109/INFCOM.2009.5061918

Abu-Affash

A. K.

Aschner

Carmi

Katz

M. J.

Minimum power energy spanners in wireless ad hoc networks

Proceedings of the 28th Conference on Computer Communications

March 2010

San Diego, Calif, USA

1 6

2-s2.0-77953302441

10.1109/INFCOM.2010.5462068

Shpungin

Segal

Near-optimal multicriteria spanner constructions in wireless Ad Hoc networks

IEEE/ACM Transactions on Networking 2010 18 6 1963 1976

2-s2.0-77954556510

10.1109/TNET.2010.2053381

Rickenbach

P. V.

Wattenhofer

Zollinger

Algorithmic models of interference in wireless Ad Hoc and sensor networks

IEEE/ACM Transactions on Networking 2009 17 1 172 185

2-s2.0-61449267703

10.1109/TNET.2008.926506

Chew

L. P.

There is a planar graph almost as good as the complete graph

Proceedings of the 2nd Symposium on Computational Geometry

1986

Yorktown Heights, NY, USA

169 177

Moraes

R. E. N.

Ribeiro

C. C.

Duhamel

Optimal solutions for fault-tolerant topology control in wireless ad hoc networks

IEEE Transactions on Wireless Communications 2009 8 12 5970 5981

2-s2.0-72949154944

10.1109/TWC.2009.12.081566

Lian

Bin

Algorithms for k-fault tolerant power assignments in wireless sensor networks

Science China Information Sciences 2010 53 12 2527 2537

Indranil

Lokesh

K. S.

Subhas

K. G.

Ranjeet

K. P.

Distributed fault-tolerant topology control in wireless multi-hop networks

Wireless Networks 2010 16 6 1511 1524

2-s2.0-77957862482

10.1007/s11276-008-0133-2

10.

Carmi

Segal

Katz

M. J.

Shpungin

Fault-tolerant power assignment and backbone in wireless networks

Proceedings of the 4th annual IEEE International Conference on Pervasive Computing and Communications Workshops

March 2006

Washington, DC, USA

80 84

2-s2.0-33750311751

10.1109/PERCOMW.2006.55

11.

Kruskal

J. B.

On the shortest spanning subtree of a graph and the traveling salesman problem

Proceedings of the American Mathematical Society 1956 7 1 48 50

12.

Even

Tarjan

R. E.

Network flow and testing graph connectivity

SIAM Journal on Computing 1975 4 507 518

13.

Di Battista

Tamassia

Vismara

Output-sensitive reporting of disjoint paths

Algorithmica 1999 23 4 302 340

2-s2.0-0013362396

14.

Dijkstra

E. W.

A note on two problems in connexion with graphs

Numerische Mathematik 1959 53 8 41 47

2-s2.0-34147120474

Interference-Aware Fault-Tolerant Energy Spanner in Wireless Ad Hoc Networks

Abstract

1. Introduction

2. Related Work

3. Problem Statement

4. Models

Definition 1.

Definition 2.

Definition 3.

Definition 4.

Definition 5.

5. Interference Minimal Fault-Tolerant Energy Spanner

Algorithm 1

5.1. Analyze

Lemma 6.

Proof.

Lemma 7.

Proof.

Lemma 8.

Proof.

Theorem 9.

Proof.

Lemma 10.

Proof.

Theorem 11.

Proof.

Lemma 12.

Proof.

Theorem 13.

Proof.

Theorem 14.

Proof.

5.2. Simulations

Interference

Power Stretch Factor

6. Conclusion

Footnotes

Acknowledgments

References