# Power Control Methods for Improving Spatial Reuse in TDMA-Based Wireless Mesh Networks

Authors: Go Hasegawa; Toshiaki Hidekuma; Masahiro Sasabe; Hirotaka Nakano
Journal: ISRN Communications and Networking
 (2011)

---

## Abstract

Wireless Mesh Networks (WMNs) have attracted a great deal of interest in recent years as a cost-effective method to provide a wireless network infrastructure. To accommodate various types of application traffic in WMNs, improvement of network capacity is one of the most critical issues. The efficiency of wireless network resource utilization decreases due to radio interference when multiple transmissions occur simultaneously in an interference region. To resolve this problem, we focus on the transmission power control of mesh nodes.  We expect to improve spatial reuse by applying power control because this decreases radio interference between wireless links.  In this paper, we propose power control methods of mesh nodes for improving spatial reuse in TDMA-based wireless mesh networks. We first propose two types of power control methods, which employ a simple threshold-based mechanism. Furthermore, we develop an additional method that suppresses the unnecessary increase in path length associated with limiting the increase in the hop count to the nearby mesh nodes. Numerical evaluation results reveal that the proposed method decreases the frame length by up to 27% with non sensitive parameter setting.


---

## Body

## 1. Introduction

Wireless Mesh Networks (WMNs) have attracted a great deal of interest in recent years as a cost-effective method by which to provide a wireless network infrastructure [1, 2]. A WMN generally consists of three types of network nodes, namely, mesh nodes, gateway nodes, and stations, as illustrated in Figure 1. A collection of mesh nodes form the backbone network by constructing wireless links between mesh nodes within the radio transmission range. Unlike the traditional Wireless Local Area Network (WLAN), only a portion of the mesh nodes need be connected to the wired network. The mesh nodes that are connected to the wired network are called gateway nodes and other mesh nodes connect to the wired network by multihop connections through gateway nodes. The stations connect to one of the mesh nodes and communicate with other stations or access a wired network such as the Internet via the gateway node through the backbone network of mesh nodes. Wireless connection realizes the cost-effective deployment of access networks, as compared to the use of a wired connection, and provides good extensibility without geographical limitations.Figure 1
Wireless mesh network.One of the major problems in constructing a WMN is radio interference caused by simultaneous transmissions in the interference region [3]. In the WMN, since all mesh nodes generally share the radio channels of the backbone network, decreasing radio interference is necessary in order to increase the capacity of the WMNs.In an attempt to suppress the capacity reduction by radio interference, various approaches have been proposed in the literature. These studies include channel assignment using multiple channels in multiradio mesh networks [4, 5] and topology control with directional antennas [6, 7]. They mainly focus on exploiting the wireless resource diversity to improve channel or spatial reuse. However, although these solutions greatly reduce radio interference, they require additional equipments, such as multiple radio interfaces or directional antennas, which limits the applicability of such solutions.In the Time Division Multiple Access (TDMA) MAC protocols, radio interference is eliminated by a link scheduling mechanism [8, 9]. The link scheduling mechanism assigns different time slots to wireless links that interfere with each other in order to avoid simultaneous transmission on these links. A TDMA-based MAC protocol is proposed in the Wireless Metropolitan Area Network (WMAN), which is standardized as IEEE 802.16 [10]. However, an increase in radio interference would increase the number of time slots needed for all transmissions on links (hereinafter referred to as the frame length). This leads to the degradation of spatial reuse.We focus on the power control method, which adjusts the transmission power of mesh nodes, in order to address the above problem. Generally, the connection between mesh nodes in the backbone network is established using the maximum transmission power determined in the specification. For this reason, an improved spatial reuse is expected by applying power control because this decreases radio interference between wireless links. On the other hand, minimizing transmission power decreases the network connectivity because it reduces the number of available links in the WMN. This increases the path length (hop count of traversing wireless links) between mesh nodes and gateway nodes. The increase in hop count also increases the traffic load on wireless links, which degrades the performance of WMNs. Therefore, when applying the power control method to mesh nodes, the trade-off relationship between the decrease in radio interference and the increase in path length should be considered. However, the details of the trade-off relationship of WMNs have not been reported in the literature.In this paper, we propose power control methods of mesh nodes in TDMA-based wireless mesh networks. The proposed methods are an attempt to reduce radio interference while suppressing the increase in path length by decreasing the transmission power of mesh nodes according to the number of wireless links of each mesh node or the number of mesh nodes in the interference region. In addition, the proposed methods suppress any further increase in path length by limiting the increase in the hop count to the nearby mesh nodes.The rest of this paper is organized as follows. Previous research related to topology control approaches with power control is discussed in Section2. The network model used in this paper is described in Section 3. In Section 4, we propose new methods of power control for mesh nodes. In Section 5, we explain the evaluation method for the proposed methods and present the evaluation results to confirm the effectiveness of the proposed methods. Finally, we give conclusions and future works in Section 6.


## 2. Related Work

There are several power control approaches for use with wireless multihop networks, including wireless mesh networks and wireless ad hoc networks. A topology control with power control is very useful for minimizing power consumption and enhancing network capacity by reducing radio interference [11]. In the power control methods for minimizing power consumption [12–14], the objectives are to extend the battery life under a limited power supply and to reduce radio interference, with the enhancement network capacity being regarded as a secondary effect. To minimize power consumption, these approaches decrease node degree, which is defined as the number of wireless links of a node or the transmission power. CBTC [12] generates a power-efficient topology, which guarantees network connectivity by maintaining the angle between any two consecutive neighboring nodes to be constant. The methods in [13, 14] build a local minimum spanning tree using the Euclidean distance between nodes as the link cost in order to generate a power-efficient topology.On the other hand, a power-efficient topology does not necessarily have low interference [15]. LISE [15] attempts to minimize the maximum edge interference and limit the increase in path length by limiting the ratio of the increase in the hop count after the power control. In [16], the author discusses the effect of existing topology control methods under several interference model.Topology control approaches that control multiple factors, including transmission power, have been studied extensively. In a previous study [17], joint power control, which is a problem that concerns channel assignment and routing, was investigated based on the idea that the topology should be dynamically adjusted according to the traffic demand, which is determined by a routing algorithm. The network capacity in TDMA-based WMNs was improved by solving a linear programming problem in which the conditions for the power control and link scheduling that are to be satisfied are given [18, 19]. They focused on optimization of the transmission power configuration and the time slot assignment under the assumption that the traffic load on each wireless link is given in advance. However, these approaches do not consider the situation in which the power control removes some wireless links and the traffic load changes due to changes in network topology.We focus on the decrease in radio interference and the increase in path length and propose power control methods for improving spatial reuse considering traffic load changes.


## 3. Network Model

In this section, the network model and notation used in this paper are described. Hereinafter, the termlink is used to indicate the wireless link. We assume an infrastructure wireless mesh network, in which the backbone network consists of mesh nodes that are fixedly located and have no mobility. Note that the location information is not necessary in the proposed method. A wireless mesh network can be represented as a directed graph G=(V,E,ft), called a communication graph, where V={v1,…,vn} is the set of mesh nodes, E is the set of links between the mesh nodes, and ft:E→V×V is a mapping from a link to a pair of mesh nodes. Each mesh node vi has a transmission range ti, and a link exists between vi and vj and (vi,vj)∈E if ∥vi-vj∥≤ti.Each mesh nodevi also has an interference range ri, which is determined by its transmission range and interference-transmission ratio, denoted as ri=γ×ti. The interference-transmission ratio is determined by the radio characteristics and is established as 2<γ<4 [20]. The interference between links is also affected by the interference model.The interference between links is determined by an interference model. Many of past literature uses the interference models introduced in [3], which are the physical interference model and the protocol interference model. In the physical interference model, the interference relationships are determined only from the radio strength of all mesh nodes in the network. On the other hand, the protocol interference model considers the detailed situation where the interference occurs from the results of protocol behaviors. In this paper, we utilize the interference model based on the RTS/CTS model [21] which is one of the protocol interference model because it can describe the interference conditions easily. Note that the proposed methods can be applied under other interference models in the 802.16-based wireless mesh network.Figure2(a) shows the case in which the link el(ft(el)=(vi,vj)) is interfered with by the link em(ft(em)=(vp,vq)). Consider the situation in which vp sends an RTS message to vq and vi receives the RTS message. The RTS message does not interfere with other communications between mesh nodes because they are carried by different radio channels, but the communication from vp to vq and that from vi to vj cannot take place simultaneously due to the characteristics of the RTS/CTS model. In this case, an interference relationship between el and em is said to exist. The interference due to a CTS message is similarly addressed. Therefore, the condition whereby em interferes with el is denoted as follows:(1)‖vp-vi‖≤rp,‖vp-vj‖≤rp,‖vq-vi‖≤rq,‖vq-vj‖≤rq.
The RTS/CTS model is used because it is one of the most essential interference models.Interference based on the RTS/CTS model.
(a)
RTS message(b)
CTS messageGiven a communication graphG=(V,E,ft), a conflict graph [22] is constructed to represent the interference relationship in G. A link between two mesh nodes corresponds to a vertex in the conflict graph, and an interference relationship between two links is represented by an edge in the conflict graph. The conflict graph is denoted as Gc=(E,C,fc), where C={c1,…,ck} is the set of interference relationships between links and fc:C→E×E is a mapping from an interference relationship to a pair of links.We also assume that the WMN uses a TDMA MAC protocol, in which the time is divided into slots of fixed duration, and the time slots are grouped into a frame. The link scheduling in the TDMA MAC protocol assigns time slots to each link according to its traffic load. Once the schedule is determined, the schedule is used in every frame until the traffic demand changes. Using the conflict graph, the link scheduling problem can be treated as a vertex coloring problem in the conflict graph [20].


## 4. Power Control Methods

In this section, we introduce the power control methods for improving spatial reuse. We assume that the initial network topology is constructed such that all mesh nodes connect to other mesh nodes with the maximum transmission power determined in the specification. Then the power control methods proposed in this section are applied. First, we describe two types of power control methods called Power Control based on Node Degree (PCND) and Power Control based on Node Interference (PCNI). Both of these methods employ a simple threshold-based mechanism but differ in terms of the parameter that is used as a threshold metric. We then describe Path Length Adjustment between adjacent nodes (PLA) which attempts to suppress the increase in path length. PLA is applied after the process of PCND or PCNI. Finally, We introduce another power control method called Power Control based on Local Optimization (PCLO) for the purpose of performance comparison.


### 4.1. Power Control Based on Node Degree (PCND)

Algorithm1 is the algorithm of PCND. PCND reduces the transmission power of mesh nodes according to their node degree by preventing the node degree from becoming too small. Specifically, the transmission power of a mesh nodes is reduced so that the degree of the mesh node should be decreased to δ. For mesh nodes of degree less than or equal to δ in the initial topology, the transmission power is set to the minimum power so as not to remove any links. The key ideas in the PCND algorithm are suppression of the increase in path length and cutting of highly interfering links. By preventing the node degree from becoming too small, the increase in path length can be suppressed. Since the links connected to the mesh node of large degree are likely to have numerous interference relationships, the degree-based power control is reasonable.Algorithm 1:Power Control based on Node Degree (PCND).
Require:  A communication graph G=(V,E,ft) and a node degree threshold δ.Ensure: A set of transmission ranges {t1,…,tn}.(1)for allvi∈Vdo(2)ti=tmax(3)whileδ<d(vi)do(4)   Find the farthest vertexvj among adjacent vertices of vi.(5)ti=∥vi-vj∥.(6)ifδ<d(vj)then(7)    Remove edges betweenvi and vj.(8)ifG is not a connected graphthen(9)     Repair edges betweenvi and vj.(10)break(11)end if(12)else(13)break(14)end if(15)end while(16)end for*d(vj) is the number of outgoing links from vi.


### 4.2. Power Control Based on Node Interference (PCNI)

Algorithm2 is the algorithm of PCNI. Here, the node interference of a mesh node is defined as the number of other mesh nodes located within the interference range of the mesh node. PCNI reduces the transmission power of mesh nodes so that its node interference is equal to λ. As for mesh nodes that node interference is less than or equal to λ in the initial topology, the transmission power is set to the minimum power so as not to remove any links. PCNI makes it possible to efficiently reduce radio interference because the interference relationship between links depends on the interference range of mesh nodes. Since power control according to the node interference does not remove a significant number of links, the increase in path length can be suppressed.Algorithm 2:Power Control based on Node Interference (PCNI).
Require:  A communication graph G=(V,E,ft) and a node interference threshold λ.Ensure:  A set of transmission ranges {t1,…,tn}.(1)for allvi∈Vdo(2)ti=tmax(3)whileλ<I(vi)do(4)   Find the farthest vertexvj among adjacent vertices of vi.(5)ti=∥vi-vj∥.(6)ifλ<I(vj)then(7)    Remove edges betweenvi and vj.(8)ifG is not a connected graphthen(9)     Repair edges betweenvi and vj.(10)break(11)end if(12)else(13)break(14)end if(15)end while(16)end for*I(vi) is the number of mesh nodes in the interference region in vi.


### 4.3. Path Length Adjustment between Adjacent Nodes (PLA)

In PCND and PCNI, each mesh node removes links so that a metric can reache a threshold value. Although PCND and PCNI are effective in reducing radio interference, they cause an increase in path length in some situations. Especially, we focus on the path between mesh nodes that connect to each other directly in the initial topology. Such a path is referred to as the target path. For target paths, there are few alternative paths with small path lengths when the mesh nodes are connected to each other with nearly maximum transmission power. In this situation, removing links by applying PCND or PCNI is likely to increase the length of the target path.Based on the above discussion, we introduce a power control method called Path Length Adjustment between adjacent nodes (PLA). In PLA, each mesh node adds links by increasing transmission power until the length of all target paths is less than or equal toh. When all of the target paths have fewer than h hop counts, the transmission power remains unchanged. PLA adds the most effective links for suppressing the increase in the length of the target paths. Algorithm 3 is the algorithm of PLA. Hereinafter, the methods of adding PLA to PCND and PCNI are referred to as PCND-PLA and PCNI-PLA, respectively.Algorithm 3:Path length adjustment between adjacent nodes (PLA).
Required: A communication graph without power control Gb=(V,Eb), a communication graph withpower controlGa=(V,Ea), and a path length threshold hEnsure:  A set of transmission ranges {t1,…,tn}(1)forvi∈Vdo(2)for(vi,vj)∈Ebdo(3)ifh(vi,vj,Ga)>hthen(4)    Add a link fromvi to vj(5)ifti<∥vi-vj∥then(6)ti=∥vi-vj∥(7)end if(8)iftj<∥vi-vj∥then(9)tj=∥vi-vj∥(10)end if(11)end if(12)end for(13)end for*h(vi,vj,G) is the path length from vi to vj in G.


### 4.4. Power Control Based on Local Optimization (PCLO)

Algorithm4 is the algorithm of PCLO. PCLO is based on a simple heuristic algorithm. As for all mesh nodes, the “longest link” which is the link with the farthest neighboring node is defined for each mesh node, where the farthest neighboring node is removed first by reducing the transmission power of the mesh node. Then, for all mesh nodes, the degree of the decrease in the frame length when the longest link for its mesh node is removed is calculated. So the longest link which gives the largest decrease in frame length is actually removed. The transmission power of the selected mesh node is set to the minimum power so as to remove only its longest link. This process is repeatedly applied until the frame length no longer decreases.Algorithm 4:Power Control based on Local Optimization (PCLO).
Require: A communication graph G=(V,E,ft) and the frame length without power control l0.Ensure:  A set of transmission ranges {t1,…,tn} and frame length l.(1)l=l0 and define temporary frame length l′=l0.(2)for allti∈{t1,…,tn}do(3)ti=tmax(4)end for(5)whilel′≤ldo(6)l=l′.(7)for allvi∈Vdo(8)   Find the farthest vertexvj among adjacent vertices of vi.(9)   Set temporary transmission rangeti′=∥vi-vj∥.(10)if  Remove edges between vi and vj and G is a connected graph then(11)    Get frame lengthli by the weighted link scheduling.(12)end if(13)end for(14)  Explore the vertexvp that satisfies lp==min{l1,…,ln}.(15)l′=lp.(16)  Remove the longest edge ofvp and tp=tp′.(17)end whileIn PCLO, the computational overhead is the most serious problem because the frame length must be calculated by applying the link scheduling algorithms for all candidate links to be removed. However, we expect that PCLO gives a smaller frame length than other proposed methods due to its exhaustive search mechanism. Note that the frame length after applying PCLO is not necessarily optimal because PCLO is based on a simple local optimization. However, since there is no effective method by which to obtain the theoretical lower bound of the frame length, we use PCLO for the purpose of performance comparison.


## 4.1. Power Control Based on Node Degree (PCND)

Algorithm1 is the algorithm of PCND. PCND reduces the transmission power of mesh nodes according to their node degree by preventing the node degree from becoming too small. Specifically, the transmission power of a mesh nodes is reduced so that the degree of the mesh node should be decreased to δ. For mesh nodes of degree less than or equal to δ in the initial topology, the transmission power is set to the minimum power so as not to remove any links. The key ideas in the PCND algorithm are suppression of the increase in path length and cutting of highly interfering links. By preventing the node degree from becoming too small, the increase in path length can be suppressed. Since the links connected to the mesh node of large degree are likely to have numerous interference relationships, the degree-based power control is reasonable.Algorithm 1:Power Control based on Node Degree (PCND).
Require:  A communication graph G=(V,E,ft) and a node degree threshold δ.Ensure: A set of transmission ranges {t1,…,tn}.(1)for allvi∈Vdo(2)ti=tmax(3)whileδ<d(vi)do(4)   Find the farthest vertexvj among adjacent vertices of vi.(5)ti=∥vi-vj∥.(6)ifδ<d(vj)then(7)    Remove edges betweenvi and vj.(8)ifG is not a connected graphthen(9)     Repair edges betweenvi and vj.(10)break(11)end if(12)else(13)break(14)end if(15)end while(16)end for*d(vj) is the number of outgoing links from vi.


## 4.2. Power Control Based on Node Interference (PCNI)

Algorithm2 is the algorithm of PCNI. Here, the node interference of a mesh node is defined as the number of other mesh nodes located within the interference range of the mesh node. PCNI reduces the transmission power of mesh nodes so that its node interference is equal to λ. As for mesh nodes that node interference is less than or equal to λ in the initial topology, the transmission power is set to the minimum power so as not to remove any links. PCNI makes it possible to efficiently reduce radio interference because the interference relationship between links depends on the interference range of mesh nodes. Since power control according to the node interference does not remove a significant number of links, the increase in path length can be suppressed.Algorithm 2:Power Control based on Node Interference (PCNI).
Require:  A communication graph G=(V,E,ft) and a node interference threshold λ.Ensure:  A set of transmission ranges {t1,…,tn}.(1)for allvi∈Vdo(2)ti=tmax(3)whileλ<I(vi)do(4)   Find the farthest vertexvj among adjacent vertices of vi.(5)ti=∥vi-vj∥.(6)ifλ<I(vj)then(7)    Remove edges betweenvi and vj.(8)ifG is not a connected graphthen(9)     Repair edges betweenvi and vj.(10)break(11)end if(12)else(13)break(14)end if(15)end while(16)end for*I(vi) is the number of mesh nodes in the interference region in vi.


## 4.3. Path Length Adjustment between Adjacent Nodes (PLA)

In PCND and PCNI, each mesh node removes links so that a metric can reache a threshold value. Although PCND and PCNI are effective in reducing radio interference, they cause an increase in path length in some situations. Especially, we focus on the path between mesh nodes that connect to each other directly in the initial topology. Such a path is referred to as the target path. For target paths, there are few alternative paths with small path lengths when the mesh nodes are connected to each other with nearly maximum transmission power. In this situation, removing links by applying PCND or PCNI is likely to increase the length of the target path.Based on the above discussion, we introduce a power control method called Path Length Adjustment between adjacent nodes (PLA). In PLA, each mesh node adds links by increasing transmission power until the length of all target paths is less than or equal toh. When all of the target paths have fewer than h hop counts, the transmission power remains unchanged. PLA adds the most effective links for suppressing the increase in the length of the target paths. Algorithm 3 is the algorithm of PLA. Hereinafter, the methods of adding PLA to PCND and PCNI are referred to as PCND-PLA and PCNI-PLA, respectively.Algorithm 3:Path length adjustment between adjacent nodes (PLA).
Required: A communication graph without power control Gb=(V,Eb), a communication graph withpower controlGa=(V,Ea), and a path length threshold hEnsure:  A set of transmission ranges {t1,…,tn}(1)forvi∈Vdo(2)for(vi,vj)∈Ebdo(3)ifh(vi,vj,Ga)>hthen(4)    Add a link fromvi to vj(5)ifti<∥vi-vj∥then(6)ti=∥vi-vj∥(7)end if(8)iftj<∥vi-vj∥then(9)tj=∥vi-vj∥(10)end if(11)end if(12)end for(13)end for*h(vi,vj,G) is the path length from vi to vj in G.


## 4.4. Power Control Based on Local Optimization (PCLO)

Algorithm4 is the algorithm of PCLO. PCLO is based on a simple heuristic algorithm. As for all mesh nodes, the “longest link” which is the link with the farthest neighboring node is defined for each mesh node, where the farthest neighboring node is removed first by reducing the transmission power of the mesh node. Then, for all mesh nodes, the degree of the decrease in the frame length when the longest link for its mesh node is removed is calculated. So the longest link which gives the largest decrease in frame length is actually removed. The transmission power of the selected mesh node is set to the minimum power so as to remove only its longest link. This process is repeatedly applied until the frame length no longer decreases.Algorithm 4:Power Control based on Local Optimization (PCLO).
Require: A communication graph G=(V,E,ft) and the frame length without power control l0.Ensure:  A set of transmission ranges {t1,…,tn} and frame length l.(1)l=l0 and define temporary frame length l′=l0.(2)for allti∈{t1,…,tn}do(3)ti=tmax(4)end for(5)whilel′≤ldo(6)l=l′.(7)for allvi∈Vdo(8)   Find the farthest vertexvj among adjacent vertices of vi.(9)   Set temporary transmission rangeti′=∥vi-vj∥.(10)if  Remove edges between vi and vj and G is a connected graph then(11)    Get frame lengthli by the weighted link scheduling.(12)end if(13)end for(14)  Explore the vertexvp that satisfies lp==min{l1,…,ln}.(15)l′=lp.(16)  Remove the longest edge ofvp and tp=tp′.(17)end whileIn PCLO, the computational overhead is the most serious problem because the frame length must be calculated by applying the link scheduling algorithms for all candidate links to be removed. However, we expect that PCLO gives a smaller frame length than other proposed methods due to its exhaustive search mechanism. Note that the frame length after applying PCLO is not necessarily optimal because PCLO is based on a simple local optimization. However, since there is no effective method by which to obtain the theoretical lower bound of the frame length, we use PCLO for the purpose of performance comparison.


## 5. Numerical Evaluation

In this section, we evaluate the effectiveness of each of the proposed methods by numerical evaluations. We first explain the frame length as a metric of performance in Section5.1. Then in Section 5.2, we evaluate the performance of the proposed methods and compare the evaluations obtained by the proposed methods with each other as well as with those obtained by existing methods.


### 5.1. Evaluation Method

When the power control is applied to mesh nodes in a WMN, the changes in traffic load on the links caused by the topology change must be considered. Decreasing the transmission power of a mesh node causes a decrease in the degree of interference in the WMN. On the other hand, this also decreases the number of links in the WMN, which results in a topology change. This causes changes in the traffic load on the links.In previous studies, the frame length, which is calculated by link scheduling algorithms, has been used for evaluating the performance of the TDMA-based link scheduling algorithm [23]. Here, the frame length is defined as the number of time slots needed for all links to transmit their traffic. Minimizing the frame length results in an increase in the number of simultaneous transmissions in a single time slot, which can be regarded as an improvement in spatial reuse. However, the conventional link scheduling mechanisms assign a single time slot to each link, regardless of the traffic load on the link [20]. This means that the difference in the traffic load of each link has been ignored in such evaluations. When the power control to mesh nodes is applied, however, such a simple evaluation method cannot be used.In this paper, we evaluate the performance of power control methods using the frame length, assuming theweighted link scheduling algorithm proposed in [20], where the number of time slots assigned to each link is determined according to the weight of the link. By introducing the weighted link scheduling algorithm, the degree of spatial reuse can be evaluated for the case in which the traffic load on the links changes according to the power control. A number of link scheduling algorithms have been proposed in the literature [21, 24], and the frame length depends on the link scheduling algorithm. However, we used the algorithm in [20] because the link scheduling algorithm gives the minimum frame length easily under the situation in which all interference relationships are known.The link weight is computed according to the traffic load on each link, and the weighted link scheduling algorithm is applied to the conflict graphGc. The link weight is determined as follows. The amount of communications between each pair of mesh nodes is determined by the given traffic demands. We assume that the path between each pair of mesh nodes is decided using Dijkstra's algorithm. Here, Ei,j is defined as a set of links that are included in the path from vi to vj. We also assume the traffic load on a link ek is proportional to the sum of the traffic demands of the communications between mesh nodes that traverse ek. Here, fi,j(ek) is defined for mesh nodes vi and vj and link ek, as follows:(2)fi,j(ek)={li,j,(Ei,jincludesek),0,(Ei,jdoesnotincludeek),
where li,j is the amount of traffic demand from vi to vj. Hence, the traffic load of ek, defined by f(ek), can be calculated as(3)f(ek)=∑{vi,vj}∈Pfi,j(ek),
where P is a set of source and destination node pairs of paths on which the communication exists. Finally, the link weight in (3) is quantized with the quantization factor β in order to decrease the complexity of calculating the time slot assignment and the frame length. The following equation shows the quantized link weight:(4)wk=⌈f(ek)β⌉,
where ⌈·⌉ denotes the ceiling of a real number.In assigning time slots to links, it is necessary to consider the actual amount of traffic on each link. However, in this paper, the degree of spatial reuse is evaluated comparatively with respect to the frame length decided by the weighted link scheduling with (4) as the link weight.


### 5.2. Numerical Evaluation Results

Table1 shows the parameter settings used in the evaluation. The process of the numerical evaluation is as follows. First, a wireless mesh network is generated with n mesh nodes, which are randomly placed in a 1 × 1 area. The locations of all mesh nodes are determined independently. Next, the initial topology is generated with the maximum transmission power, and the communication graph is obtained. The connectedness of the communication graph is then assessed by checking whether a valid path exists between all pairs of mesh nodes in the graph. If the communication graph is not connected, it is discarded and another communication graph is generated.Table 1
Parameter settings.
Number of evaluations100Area size1 × 1Mesh node locationRandomNumber of mesh nodes:n20, 30, 40, 50, 6070, 80, 90, 100Initial transmission range:tmax0.20Interference-transmission ratio:γ2.0Traffic demand1(for all mesh node pairs)Quantization factor:β100After the communication graph is connected, the power control methods described in Section4 are applied, and the frame length determined by the weighted link scheduling algorithm is evaluated. In this evaluation, we assume that only end-to-end communications exist between mesh nodes and that the same amount of traffic demand is generated on all pairs of mesh nodes in the network. Note that the proposed method can be applied to the heterogeneous traffic demand. For each power control method, the initial network topology is generated 100 times and the average frame length after applying the power control method is evaluated.


#### 5.2.1. Performance of PCND and PCNI

We first evaluate the impact of the settings of the thresholdδ for PCND and the threshold λ for PCNI. Figure 3 shows the changes in frame length for PCND and PCNI for various thresholds, as a function of the number of mesh nodes. The changes in the frame length ratio with power control to that without power control, hereinafter referred to simply as the frame length ratio, are shown in Figures 3(a) and 3(b), respectively. The error bars in Figures 3(a) and 3(b) show the 95% confidence intervals.Impact of the threshold in PCND and PCNI.
(a)
PCND(b)
PCNIIn PCND, the use ofδ= 2 and 3 decreases the frame length when the number of mesh nodes is small, as shown in Figure 3(a). However, the frame length ratio increases as the number of mesh nodes increases, and the frame length with power control is greater than that without power control when n≥60. This is because that the use of a small value of δ causes an increase in the path length due to cutting too many links and the increase in traffic load on each link. In contrast, the use of δ≥4 decreases the frame length regardless of the number of mesh nodes. Furthermore, the frame length ratio decreases significantly as the number of mesh nodes increases.In PCNI, there is a similar tendency to PCND with respect to the change inλ, as shown in Figure 3(b). As the number of mesh nodes increases, the use of λ≤15 increases the frame length ratio, but using λ≥25 decreases the ratio of frame length.Although the parameters to be used for power control differ between PCND and PCNI, in both PCND and PCNI, the parameter settings to decrease the frame length are highly dependent on the number of nearby mesh nodes. In addition, PCND decreases the frame length by up to 22%, and PCNI decreases the frame length by up to 26%, which corresponds to the degree of improvement in spatial reuse.We also assess the variation in the performance of PCND and PCNI caused by the difference in initial topology. Figure4 shows the Cumulative Distribution Function (CDF) of the frame length ratio for 100 numerical evaluations. There is a similar trend in terms of the threshold values in PCND and PCNI. When the number of mesh nodes is small, the probability that the proposed method decreases the frame length is approximately 1, regardless of the threshold value. As the number of mesh nodes increases, the small threshold value decreases the probability, and the degree of the increase in the frame length becomes large. This is because the small threshold value results in a difference in topology after the power control, which leads to an increase in the path length. On the other hand, when the threshold is large, the probability that the proposed method decreases the frame length is approximately 1.CDF of the frame length ratio (PCND, PCNI).
(a)
PCND(b)
PCNIBased on these results, the performances of PCND and PCNI are thought to be highly dependent on the threshold settings, whereas a significant decrease in frame length can be obtained when the thresholds are configured appropriately.


#### 5.2.2. Performance of PCND-PLA and PCNI-PLA

We next evaluate the performance of PCND-PLA and PCNI-PLA in which PLA is applied after the processing of PCND and PCNI, respectively. Since, in PCND and PCNI, the number of target paths in PLA depends on the threshold values, we show the evaluation results for PCND-PLA (δ=2) and PCNI-PLA (λ=5) for the case of the a number of target paths and for PCND-PLA (δ=5) and PCNI-PLA (λ=30) for the case of a small number of target paths.Figures5 and 6 show the frame length ratio of PCND-PLA and PCNI-PLA. Using small threshold values, PCND and PCNI increase the frame length ratio as the number of mesh nodes increases, but PCND-PLA and PCNI-PLA decrease the frame length significantly. On the other hand, when large threshold values are used, PCND-PLA and PCNI-PLA have little effect. Suppressing the decrease in the path length by PLA is less effective because the topology generated by PCND and PCNI using large threshold values has a certain level of network connectivity. Focusing on the value of h, when the threshold values are small, the frame length decreases significantly with small h values.Impact of the thresholdh in PCND-PLA.
(a)
PCND-PLA (δ=2)(b)
PCND-PLA (δ=5)Impact of the thresholdh in PCND-PLA.
(a)
PCNI-PLA (λ=5)(b)
PCNI-PLA (λ=30)Figure7 shows the CDF of the frame length ratio for 100 numerical evaluations. When the number of mesh nodes is small, PCND-PLA and PCNI-PLA have similar trends to those of PCND and PCNI, meaning that the probability of decreasing the frame length is approximately 1, regardless of the parameter settings. When the number of mesh nodes is large, on the other hand, PCND-PLA and PCNI-PLA using small threshold values significantly improve the performance, especially, when the value of h is small. Comparing Figures 4, 5, and 6 reveals that, by applying PLA, the performances of PCND and PCNI become stable, meaning that PCND and PCNI can decrease the frame length for almost all initial topologies.CDF of the frame length ratio (PCND-PLA, PCNI-PLA).
(a)
PCND-PLA(b)
PCNI-PLABased on these results, adding PLA to PCND and PCNI can decrease the frame length, regardless of the number of mesh nodes and parameter settings. PCND-PLA (δ=5, h=4) decreases the frame length by up to 23%, and PCNI-PLA (λ=30, h=4) decreases the from length by up to 27%. In addition, PCND-PLA and PCNI-PLA can decrease the frame length stably with nonsensitive parameter settings, while the threshold parameters should be selected carefully in PCND and PCNI without PLA.


#### 5.2.3. Performance Comparison with Existing Methods

We show the comparative results with existing methods and evaluate the effectiveness of each of the proposed method. Three types of power control methods are used for the purpose of comparison: PCLO (explained in Section4.4), CBTC [12], and LISE [15].Since there is no effective method by which to obtain the theoretical lower bound of frame length, we use PCLO for the purpose of the performance comparison as a measure of the degree to which a power control can decrease the frame length. In the comparison with conventional methods, different power control methods are used according to the primary goal. Specially, CBTC is used to minimize power consumption, and LISE is used to reduce radio interference. Although the purpose of the proposed method differs from that of CBTC, we evaluate the effectiveness of the proposed method as compared to the power control method to minimize power consumption in terms of spatial reuse. LISE generates a topology with low interference by limiting the increase in the path length caused by power control.Figure8 shows the frame length ratio by PCNI-PLA, PCLO, CBTC, and LISE. The parameters of each method are set such that the decrease in the degree of the frame length becomes largest. Note that for CBTC, all optimization methods shown in [12] are applied. In PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, because the mechanism of PCLO is independent of the number of mesh nodes. The performance of PCNI-PLA is comparable to that of PCLO when the number of mesh nodes is either small or large.Figure 8
Comparison with existing methods.The effect of CBTC and LISE is quite limited as compared with PCNI-PLA. CBTC generates a power-efficient topology with small node degree, but excessively reducing the number of links increases the path length, which increases traffic loads. On the other hand, PCNI-PLA, which reduces the number of links in order to decrease radio interference considering the increase in the path length, is more effective for improving spatial reuse. Although LISE also takes care of the increase in path length, the links to be used are determined by only its degree of interference, so each mesh node cannot decrease its transmission power so largely. The paths which are taken care of the increase in the length by PCNI-PLA are different from that by LISE, which makes the difference in performance between PCNI-PLA and LISE.


#### 5.2.4. Computation Complexity of the Proposed Methods

Finally, we discuss the computation complexity of the proposed methods. The comparative evaluation showed that in PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, while the performances of PCND-PLA and PCNI-PLA depend on the number of mesh nodes in the WMN. However, PCND-PLA and PCNI-PLA have an advantage in terms of computation complexity, as compared to PCLO.The primary factors in determining the computation complexity are checking the connectedness of the communication graph and calculating the frame length by the weighted link scheduling algorithm. Table2 shows the computation complexity for the worst case in which a communication graph has n mesh nodes. These results are obtained as follows.Table 2
Computation complexity.
ProcessPCND, PCNIPCND-PLA, PCNI-PLAPCLOChecking a graph connectednessO(n4)O(n4)O(n5)Calculating frame lengthO(n4)O(n4)O(n7)Checking path length—O(n4)—Total computation complexityO(n4)O(n4)O(n7)Since the number of links in the network is proportional ton2, the number of links removed by the power control is also proportional to n2. Checking the graph connectedness requires a computation complexity of O(n2) [25]. Since the calculation of the frame length is regarded as a vertex coloring problem of a conflict graph, the computation complexity of this problem is O(n4) because the number of vertices in the conflict graph is proportional to n2 [26]. In PCND and PCNI, the graph connectedness must be checked every time when a link is removed. On the other hand, the frame length need only to be calculated once at the end of the algorithm. Therefore, the total computation complexity of PCND and PCNI is O(n4). For PLA, the length of the paths to the nearby mesh nodes can be computed with the same complexity as for checking the graph connectedness and should be checked each time a link is added. Therefore, the total computation complexity of PLA is O(n4) and those of PCND-PLA and PCNI-PLA are also O(n4). For PCLO, on the other hand, checking the graph connectedness is necessary every time a link is removed. Furthermore, PCLO requires O(n) calculations of the frame length in each iteration. Therefore, the total computation complexity is O(n7). Based on the above discussion, PCND and PCNI with PLA can be applied with far less computation complexity than PCLO, so, the proposed methods can be applied easily as compared to PCLO especially when the traffic demand changes frequently.We next evaluate the average calculation times of the proposed methods. Table3 shows the average calculation time of the proposed methods, as obtained by averaging 50 calculations with Fedora 7 on a PC with a Pentium (R) D 3.4-GHz CPU and 4 GB of memory. As shown in the table, the proposed methods can be applied with much less computation complexity than PCLO. Furthermore, when the number of mesh nodes is large, the calculation of the proposed methods finishes much more quickly than that of PCLO.Table 3
Average calculation time (sec).
Number of mesh nodesPCND (δ=2)PCNI (λ=5)PCND-PLA (δ=2, h=2)PCNI-PLA (λ=5, h=2)PCLO20 mesh nodes0.540.500.560.550.5860 mesh nodes0.320.320.430.414.27 ×102100 mesh nodes2.382.302.962.971.47 ×104


## 5.1. Evaluation Method

When the power control is applied to mesh nodes in a WMN, the changes in traffic load on the links caused by the topology change must be considered. Decreasing the transmission power of a mesh node causes a decrease in the degree of interference in the WMN. On the other hand, this also decreases the number of links in the WMN, which results in a topology change. This causes changes in the traffic load on the links.In previous studies, the frame length, which is calculated by link scheduling algorithms, has been used for evaluating the performance of the TDMA-based link scheduling algorithm [23]. Here, the frame length is defined as the number of time slots needed for all links to transmit their traffic. Minimizing the frame length results in an increase in the number of simultaneous transmissions in a single time slot, which can be regarded as an improvement in spatial reuse. However, the conventional link scheduling mechanisms assign a single time slot to each link, regardless of the traffic load on the link [20]. This means that the difference in the traffic load of each link has been ignored in such evaluations. When the power control to mesh nodes is applied, however, such a simple evaluation method cannot be used.In this paper, we evaluate the performance of power control methods using the frame length, assuming theweighted link scheduling algorithm proposed in [20], where the number of time slots assigned to each link is determined according to the weight of the link. By introducing the weighted link scheduling algorithm, the degree of spatial reuse can be evaluated for the case in which the traffic load on the links changes according to the power control. A number of link scheduling algorithms have been proposed in the literature [21, 24], and the frame length depends on the link scheduling algorithm. However, we used the algorithm in [20] because the link scheduling algorithm gives the minimum frame length easily under the situation in which all interference relationships are known.The link weight is computed according to the traffic load on each link, and the weighted link scheduling algorithm is applied to the conflict graphGc. The link weight is determined as follows. The amount of communications between each pair of mesh nodes is determined by the given traffic demands. We assume that the path between each pair of mesh nodes is decided using Dijkstra's algorithm. Here, Ei,j is defined as a set of links that are included in the path from vi to vj. We also assume the traffic load on a link ek is proportional to the sum of the traffic demands of the communications between mesh nodes that traverse ek. Here, fi,j(ek) is defined for mesh nodes vi and vj and link ek, as follows:(2)fi,j(ek)={li,j,(Ei,jincludesek),0,(Ei,jdoesnotincludeek),
where li,j is the amount of traffic demand from vi to vj. Hence, the traffic load of ek, defined by f(ek), can be calculated as(3)f(ek)=∑{vi,vj}∈Pfi,j(ek),
where P is a set of source and destination node pairs of paths on which the communication exists. Finally, the link weight in (3) is quantized with the quantization factor β in order to decrease the complexity of calculating the time slot assignment and the frame length. The following equation shows the quantized link weight:(4)wk=⌈f(ek)β⌉,
where ⌈·⌉ denotes the ceiling of a real number.In assigning time slots to links, it is necessary to consider the actual amount of traffic on each link. However, in this paper, the degree of spatial reuse is evaluated comparatively with respect to the frame length decided by the weighted link scheduling with (4) as the link weight.


## 5.2. Numerical Evaluation Results

Table1 shows the parameter settings used in the evaluation. The process of the numerical evaluation is as follows. First, a wireless mesh network is generated with n mesh nodes, which are randomly placed in a 1 × 1 area. The locations of all mesh nodes are determined independently. Next, the initial topology is generated with the maximum transmission power, and the communication graph is obtained. The connectedness of the communication graph is then assessed by checking whether a valid path exists between all pairs of mesh nodes in the graph. If the communication graph is not connected, it is discarded and another communication graph is generated.Table 1
Parameter settings.
Number of evaluations100Area size1 × 1Mesh node locationRandomNumber of mesh nodes:n20, 30, 40, 50, 6070, 80, 90, 100Initial transmission range:tmax0.20Interference-transmission ratio:γ2.0Traffic demand1(for all mesh node pairs)Quantization factor:β100After the communication graph is connected, the power control methods described in Section4 are applied, and the frame length determined by the weighted link scheduling algorithm is evaluated. In this evaluation, we assume that only end-to-end communications exist between mesh nodes and that the same amount of traffic demand is generated on all pairs of mesh nodes in the network. Note that the proposed method can be applied to the heterogeneous traffic demand. For each power control method, the initial network topology is generated 100 times and the average frame length after applying the power control method is evaluated.


### 5.2.1. Performance of PCND and PCNI

We first evaluate the impact of the settings of the thresholdδ for PCND and the threshold λ for PCNI. Figure 3 shows the changes in frame length for PCND and PCNI for various thresholds, as a function of the number of mesh nodes. The changes in the frame length ratio with power control to that without power control, hereinafter referred to simply as the frame length ratio, are shown in Figures 3(a) and 3(b), respectively. The error bars in Figures 3(a) and 3(b) show the 95% confidence intervals.Impact of the threshold in PCND and PCNI.
(a)
PCND(b)
PCNIIn PCND, the use ofδ= 2 and 3 decreases the frame length when the number of mesh nodes is small, as shown in Figure 3(a). However, the frame length ratio increases as the number of mesh nodes increases, and the frame length with power control is greater than that without power control when n≥60. This is because that the use of a small value of δ causes an increase in the path length due to cutting too many links and the increase in traffic load on each link. In contrast, the use of δ≥4 decreases the frame length regardless of the number of mesh nodes. Furthermore, the frame length ratio decreases significantly as the number of mesh nodes increases.In PCNI, there is a similar tendency to PCND with respect to the change inλ, as shown in Figure 3(b). As the number of mesh nodes increases, the use of λ≤15 increases the frame length ratio, but using λ≥25 decreases the ratio of frame length.Although the parameters to be used for power control differ between PCND and PCNI, in both PCND and PCNI, the parameter settings to decrease the frame length are highly dependent on the number of nearby mesh nodes. In addition, PCND decreases the frame length by up to 22%, and PCNI decreases the frame length by up to 26%, which corresponds to the degree of improvement in spatial reuse.We also assess the variation in the performance of PCND and PCNI caused by the difference in initial topology. Figure4 shows the Cumulative Distribution Function (CDF) of the frame length ratio for 100 numerical evaluations. There is a similar trend in terms of the threshold values in PCND and PCNI. When the number of mesh nodes is small, the probability that the proposed method decreases the frame length is approximately 1, regardless of the threshold value. As the number of mesh nodes increases, the small threshold value decreases the probability, and the degree of the increase in the frame length becomes large. This is because the small threshold value results in a difference in topology after the power control, which leads to an increase in the path length. On the other hand, when the threshold is large, the probability that the proposed method decreases the frame length is approximately 1.CDF of the frame length ratio (PCND, PCNI).
(a)
PCND(b)
PCNIBased on these results, the performances of PCND and PCNI are thought to be highly dependent on the threshold settings, whereas a significant decrease in frame length can be obtained when the thresholds are configured appropriately.


### 5.2.2. Performance of PCND-PLA and PCNI-PLA

We next evaluate the performance of PCND-PLA and PCNI-PLA in which PLA is applied after the processing of PCND and PCNI, respectively. Since, in PCND and PCNI, the number of target paths in PLA depends on the threshold values, we show the evaluation results for PCND-PLA (δ=2) and PCNI-PLA (λ=5) for the case of the a number of target paths and for PCND-PLA (δ=5) and PCNI-PLA (λ=30) for the case of a small number of target paths.Figures5 and 6 show the frame length ratio of PCND-PLA and PCNI-PLA. Using small threshold values, PCND and PCNI increase the frame length ratio as the number of mesh nodes increases, but PCND-PLA and PCNI-PLA decrease the frame length significantly. On the other hand, when large threshold values are used, PCND-PLA and PCNI-PLA have little effect. Suppressing the decrease in the path length by PLA is less effective because the topology generated by PCND and PCNI using large threshold values has a certain level of network connectivity. Focusing on the value of h, when the threshold values are small, the frame length decreases significantly with small h values.Impact of the thresholdh in PCND-PLA.
(a)
PCND-PLA (δ=2)(b)
PCND-PLA (δ=5)Impact of the thresholdh in PCND-PLA.
(a)
PCNI-PLA (λ=5)(b)
PCNI-PLA (λ=30)Figure7 shows the CDF of the frame length ratio for 100 numerical evaluations. When the number of mesh nodes is small, PCND-PLA and PCNI-PLA have similar trends to those of PCND and PCNI, meaning that the probability of decreasing the frame length is approximately 1, regardless of the parameter settings. When the number of mesh nodes is large, on the other hand, PCND-PLA and PCNI-PLA using small threshold values significantly improve the performance, especially, when the value of h is small. Comparing Figures 4, 5, and 6 reveals that, by applying PLA, the performances of PCND and PCNI become stable, meaning that PCND and PCNI can decrease the frame length for almost all initial topologies.CDF of the frame length ratio (PCND-PLA, PCNI-PLA).
(a)
PCND-PLA(b)
PCNI-PLABased on these results, adding PLA to PCND and PCNI can decrease the frame length, regardless of the number of mesh nodes and parameter settings. PCND-PLA (δ=5, h=4) decreases the frame length by up to 23%, and PCNI-PLA (λ=30, h=4) decreases the from length by up to 27%. In addition, PCND-PLA and PCNI-PLA can decrease the frame length stably with nonsensitive parameter settings, while the threshold parameters should be selected carefully in PCND and PCNI without PLA.


### 5.2.3. Performance Comparison with Existing Methods

We show the comparative results with existing methods and evaluate the effectiveness of each of the proposed method. Three types of power control methods are used for the purpose of comparison: PCLO (explained in Section4.4), CBTC [12], and LISE [15].Since there is no effective method by which to obtain the theoretical lower bound of frame length, we use PCLO for the purpose of the performance comparison as a measure of the degree to which a power control can decrease the frame length. In the comparison with conventional methods, different power control methods are used according to the primary goal. Specially, CBTC is used to minimize power consumption, and LISE is used to reduce radio interference. Although the purpose of the proposed method differs from that of CBTC, we evaluate the effectiveness of the proposed method as compared to the power control method to minimize power consumption in terms of spatial reuse. LISE generates a topology with low interference by limiting the increase in the path length caused by power control.Figure8 shows the frame length ratio by PCNI-PLA, PCLO, CBTC, and LISE. The parameters of each method are set such that the decrease in the degree of the frame length becomes largest. Note that for CBTC, all optimization methods shown in [12] are applied. In PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, because the mechanism of PCLO is independent of the number of mesh nodes. The performance of PCNI-PLA is comparable to that of PCLO when the number of mesh nodes is either small or large.Figure 8
Comparison with existing methods.The effect of CBTC and LISE is quite limited as compared with PCNI-PLA. CBTC generates a power-efficient topology with small node degree, but excessively reducing the number of links increases the path length, which increases traffic loads. On the other hand, PCNI-PLA, which reduces the number of links in order to decrease radio interference considering the increase in the path length, is more effective for improving spatial reuse. Although LISE also takes care of the increase in path length, the links to be used are determined by only its degree of interference, so each mesh node cannot decrease its transmission power so largely. The paths which are taken care of the increase in the length by PCNI-PLA are different from that by LISE, which makes the difference in performance between PCNI-PLA and LISE.


### 5.2.4. Computation Complexity of the Proposed Methods

Finally, we discuss the computation complexity of the proposed methods. The comparative evaluation showed that in PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, while the performances of PCND-PLA and PCNI-PLA depend on the number of mesh nodes in the WMN. However, PCND-PLA and PCNI-PLA have an advantage in terms of computation complexity, as compared to PCLO.The primary factors in determining the computation complexity are checking the connectedness of the communication graph and calculating the frame length by the weighted link scheduling algorithm. Table2 shows the computation complexity for the worst case in which a communication graph has n mesh nodes. These results are obtained as follows.Table 2
Computation complexity.
ProcessPCND, PCNIPCND-PLA, PCNI-PLAPCLOChecking a graph connectednessO(n4)O(n4)O(n5)Calculating frame lengthO(n4)O(n4)O(n7)Checking path length—O(n4)—Total computation complexityO(n4)O(n4)O(n7)Since the number of links in the network is proportional ton2, the number of links removed by the power control is also proportional to n2. Checking the graph connectedness requires a computation complexity of O(n2) [25]. Since the calculation of the frame length is regarded as a vertex coloring problem of a conflict graph, the computation complexity of this problem is O(n4) because the number of vertices in the conflict graph is proportional to n2 [26]. In PCND and PCNI, the graph connectedness must be checked every time when a link is removed. On the other hand, the frame length need only to be calculated once at the end of the algorithm. Therefore, the total computation complexity of PCND and PCNI is O(n4). For PLA, the length of the paths to the nearby mesh nodes can be computed with the same complexity as for checking the graph connectedness and should be checked each time a link is added. Therefore, the total computation complexity of PLA is O(n4) and those of PCND-PLA and PCNI-PLA are also O(n4). For PCLO, on the other hand, checking the graph connectedness is necessary every time a link is removed. Furthermore, PCLO requires O(n) calculations of the frame length in each iteration. Therefore, the total computation complexity is O(n7). Based on the above discussion, PCND and PCNI with PLA can be applied with far less computation complexity than PCLO, so, the proposed methods can be applied easily as compared to PCLO especially when the traffic demand changes frequently.We next evaluate the average calculation times of the proposed methods. Table3 shows the average calculation time of the proposed methods, as obtained by averaging 50 calculations with Fedora 7 on a PC with a Pentium (R) D 3.4-GHz CPU and 4 GB of memory. As shown in the table, the proposed methods can be applied with much less computation complexity than PCLO. Furthermore, when the number of mesh nodes is large, the calculation of the proposed methods finishes much more quickly than that of PCLO.Table 3
Average calculation time (sec).
Number of mesh nodesPCND (δ=2)PCNI (λ=5)PCND-PLA (δ=2, h=2)PCNI-PLA (λ=5, h=2)PCLO20 mesh nodes0.540.500.560.550.5860 mesh nodes0.320.320.430.414.27 ×102100 mesh nodes2.382.302.962.971.47 ×104


## 5.2.1. Performance of PCND and PCNI

We first evaluate the impact of the settings of the thresholdδ for PCND and the threshold λ for PCNI. Figure 3 shows the changes in frame length for PCND and PCNI for various thresholds, as a function of the number of mesh nodes. The changes in the frame length ratio with power control to that without power control, hereinafter referred to simply as the frame length ratio, are shown in Figures 3(a) and 3(b), respectively. The error bars in Figures 3(a) and 3(b) show the 95% confidence intervals.Impact of the threshold in PCND and PCNI.
(a)
PCND(b)
PCNIIn PCND, the use ofδ= 2 and 3 decreases the frame length when the number of mesh nodes is small, as shown in Figure 3(a). However, the frame length ratio increases as the number of mesh nodes increases, and the frame length with power control is greater than that without power control when n≥60. This is because that the use of a small value of δ causes an increase in the path length due to cutting too many links and the increase in traffic load on each link. In contrast, the use of δ≥4 decreases the frame length regardless of the number of mesh nodes. Furthermore, the frame length ratio decreases significantly as the number of mesh nodes increases.In PCNI, there is a similar tendency to PCND with respect to the change inλ, as shown in Figure 3(b). As the number of mesh nodes increases, the use of λ≤15 increases the frame length ratio, but using λ≥25 decreases the ratio of frame length.Although the parameters to be used for power control differ between PCND and PCNI, in both PCND and PCNI, the parameter settings to decrease the frame length are highly dependent on the number of nearby mesh nodes. In addition, PCND decreases the frame length by up to 22%, and PCNI decreases the frame length by up to 26%, which corresponds to the degree of improvement in spatial reuse.We also assess the variation in the performance of PCND and PCNI caused by the difference in initial topology. Figure4 shows the Cumulative Distribution Function (CDF) of the frame length ratio for 100 numerical evaluations. There is a similar trend in terms of the threshold values in PCND and PCNI. When the number of mesh nodes is small, the probability that the proposed method decreases the frame length is approximately 1, regardless of the threshold value. As the number of mesh nodes increases, the small threshold value decreases the probability, and the degree of the increase in the frame length becomes large. This is because the small threshold value results in a difference in topology after the power control, which leads to an increase in the path length. On the other hand, when the threshold is large, the probability that the proposed method decreases the frame length is approximately 1.CDF of the frame length ratio (PCND, PCNI).
(a)
PCND(b)
PCNIBased on these results, the performances of PCND and PCNI are thought to be highly dependent on the threshold settings, whereas a significant decrease in frame length can be obtained when the thresholds are configured appropriately.


## 5.2.2. Performance of PCND-PLA and PCNI-PLA

We next evaluate the performance of PCND-PLA and PCNI-PLA in which PLA is applied after the processing of PCND and PCNI, respectively. Since, in PCND and PCNI, the number of target paths in PLA depends on the threshold values, we show the evaluation results for PCND-PLA (δ=2) and PCNI-PLA (λ=5) for the case of the a number of target paths and for PCND-PLA (δ=5) and PCNI-PLA (λ=30) for the case of a small number of target paths.Figures5 and 6 show the frame length ratio of PCND-PLA and PCNI-PLA. Using small threshold values, PCND and PCNI increase the frame length ratio as the number of mesh nodes increases, but PCND-PLA and PCNI-PLA decrease the frame length significantly. On the other hand, when large threshold values are used, PCND-PLA and PCNI-PLA have little effect. Suppressing the decrease in the path length by PLA is less effective because the topology generated by PCND and PCNI using large threshold values has a certain level of network connectivity. Focusing on the value of h, when the threshold values are small, the frame length decreases significantly with small h values.Impact of the thresholdh in PCND-PLA.
(a)
PCND-PLA (δ=2)(b)
PCND-PLA (δ=5)Impact of the thresholdh in PCND-PLA.
(a)
PCNI-PLA (λ=5)(b)
PCNI-PLA (λ=30)Figure7 shows the CDF of the frame length ratio for 100 numerical evaluations. When the number of mesh nodes is small, PCND-PLA and PCNI-PLA have similar trends to those of PCND and PCNI, meaning that the probability of decreasing the frame length is approximately 1, regardless of the parameter settings. When the number of mesh nodes is large, on the other hand, PCND-PLA and PCNI-PLA using small threshold values significantly improve the performance, especially, when the value of h is small. Comparing Figures 4, 5, and 6 reveals that, by applying PLA, the performances of PCND and PCNI become stable, meaning that PCND and PCNI can decrease the frame length for almost all initial topologies.CDF of the frame length ratio (PCND-PLA, PCNI-PLA).
(a)
PCND-PLA(b)
PCNI-PLABased on these results, adding PLA to PCND and PCNI can decrease the frame length, regardless of the number of mesh nodes and parameter settings. PCND-PLA (δ=5, h=4) decreases the frame length by up to 23%, and PCNI-PLA (λ=30, h=4) decreases the from length by up to 27%. In addition, PCND-PLA and PCNI-PLA can decrease the frame length stably with nonsensitive parameter settings, while the threshold parameters should be selected carefully in PCND and PCNI without PLA.


## 5.2.3. Performance Comparison with Existing Methods

We show the comparative results with existing methods and evaluate the effectiveness of each of the proposed method. Three types of power control methods are used for the purpose of comparison: PCLO (explained in Section4.4), CBTC [12], and LISE [15].Since there is no effective method by which to obtain the theoretical lower bound of frame length, we use PCLO for the purpose of the performance comparison as a measure of the degree to which a power control can decrease the frame length. In the comparison with conventional methods, different power control methods are used according to the primary goal. Specially, CBTC is used to minimize power consumption, and LISE is used to reduce radio interference. Although the purpose of the proposed method differs from that of CBTC, we evaluate the effectiveness of the proposed method as compared to the power control method to minimize power consumption in terms of spatial reuse. LISE generates a topology with low interference by limiting the increase in the path length caused by power control.Figure8 shows the frame length ratio by PCNI-PLA, PCLO, CBTC, and LISE. The parameters of each method are set such that the decrease in the degree of the frame length becomes largest. Note that for CBTC, all optimization methods shown in [12] are applied. In PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, because the mechanism of PCLO is independent of the number of mesh nodes. The performance of PCNI-PLA is comparable to that of PCLO when the number of mesh nodes is either small or large.Figure 8
Comparison with existing methods.The effect of CBTC and LISE is quite limited as compared with PCNI-PLA. CBTC generates a power-efficient topology with small node degree, but excessively reducing the number of links increases the path length, which increases traffic loads. On the other hand, PCNI-PLA, which reduces the number of links in order to decrease radio interference considering the increase in the path length, is more effective for improving spatial reuse. Although LISE also takes care of the increase in path length, the links to be used are determined by only its degree of interference, so each mesh node cannot decrease its transmission power so largely. The paths which are taken care of the increase in the length by PCNI-PLA are different from that by LISE, which makes the difference in performance between PCNI-PLA and LISE.


## 5.2.4. Computation Complexity of the Proposed Methods

Finally, we discuss the computation complexity of the proposed methods. The comparative evaluation showed that in PCLO, the frame length decreases by more than 15%, regardless of the number of mesh nodes, while the performances of PCND-PLA and PCNI-PLA depend on the number of mesh nodes in the WMN. However, PCND-PLA and PCNI-PLA have an advantage in terms of computation complexity, as compared to PCLO.The primary factors in determining the computation complexity are checking the connectedness of the communication graph and calculating the frame length by the weighted link scheduling algorithm. Table2 shows the computation complexity for the worst case in which a communication graph has n mesh nodes. These results are obtained as follows.Table 2
Computation complexity.
ProcessPCND, PCNIPCND-PLA, PCNI-PLAPCLOChecking a graph connectednessO(n4)O(n4)O(n5)Calculating frame lengthO(n4)O(n4)O(n7)Checking path length—O(n4)—Total computation complexityO(n4)O(n4)O(n7)Since the number of links in the network is proportional ton2, the number of links removed by the power control is also proportional to n2. Checking the graph connectedness requires a computation complexity of O(n2) [25]. Since the calculation of the frame length is regarded as a vertex coloring problem of a conflict graph, the computation complexity of this problem is O(n4) because the number of vertices in the conflict graph is proportional to n2 [26]. In PCND and PCNI, the graph connectedness must be checked every time when a link is removed. On the other hand, the frame length need only to be calculated once at the end of the algorithm. Therefore, the total computation complexity of PCND and PCNI is O(n4). For PLA, the length of the paths to the nearby mesh nodes can be computed with the same complexity as for checking the graph connectedness and should be checked each time a link is added. Therefore, the total computation complexity of PLA is O(n4) and those of PCND-PLA and PCNI-PLA are also O(n4). For PCLO, on the other hand, checking the graph connectedness is necessary every time a link is removed. Furthermore, PCLO requires O(n) calculations of the frame length in each iteration. Therefore, the total computation complexity is O(n7). Based on the above discussion, PCND and PCNI with PLA can be applied with far less computation complexity than PCLO, so, the proposed methods can be applied easily as compared to PCLO especially when the traffic demand changes frequently.We next evaluate the average calculation times of the proposed methods. Table3 shows the average calculation time of the proposed methods, as obtained by averaging 50 calculations with Fedora 7 on a PC with a Pentium (R) D 3.4-GHz CPU and 4 GB of memory. As shown in the table, the proposed methods can be applied with much less computation complexity than PCLO. Furthermore, when the number of mesh nodes is large, the calculation of the proposed methods finishes much more quickly than that of PCLO.Table 3
Average calculation time (sec).
Number of mesh nodesPCND (δ=2)PCNI (λ=5)PCND-PLA (δ=2, h=2)PCNI-PLA (λ=5, h=2)PCLO20 mesh nodes0.540.500.560.550.5860 mesh nodes0.320.320.430.414.27 ×102100 mesh nodes2.382.302.962.971.47 ×104


## 6. Conclusions and Future Work

In this paper, we proposed the power control methods to improve spatial reuse in a TDMA-based wireless mesh network. We first proposed Power Control based on Node Degree (PCND) and Power Control based on Node Interference (PCNI), which employ a simple threshold-based mechanism. PCND and PCNI can decrease radio interference effectively by considering the ill-effect of the increase in path length by cutting too many wireless links. In addition, we introduced Path Length Adjustment between mesh nodes (PLA), which suppresses any further increase in path length by limiting the increase in the hop count to the nearby mesh nodes. PLA was combined with PCND and PCNI, and these methods are referred to as PCND-PLA and PCNI-PLA. The numerical evaluation revealed that PCND-PLA decreased the frame length by up to 23% and PCNI-PLA decreased the frame length by up to 27%. In addition, PCND-PLA and PCNI-PLA decreased the frame length stably with nonsensitive parameter settings, whereas the threshold parameters must be carefully selected in PCND and PCNI without PLA. In comparative evaluations with existing methods, the effectiveness of each of the proposed methods in terms of spatial reuse was demonstrated.As future work, we plan to construct a new power control method by combining the power control and routing, which improves spatial reuse by power control to reduce radio interference and interference-aware routing to alleviate the traffic load on links with large interference.



---

*Source: 970943-2011-08-15.xml*