Open access peer-reviewed chapter

Stability-Based Topology Control in Wireless Mesh Networks

By Gustavo Vejarano

Submitted: December 6th 2011Reviewed: April 19th 2012Published: August 14th 2012

DOI: 10.5772/48576

Downloaded: 1110

1. Introduction

Topology control[1] - in wireless mesh networks is an important problem due to the effects it has on the different layers of the protocol stack [1]. For example, the network connectivity, energy consumption, total physical-link throughput, spatial reuse, and total end-to-end throughput as a function of the network topology have been investigated in [2-6] respectively. In this chapter, we look at the problem of topology control for adapting the stability region of the link-scheduling policy of the network. Therefore, we start by defining the problem of link scheduling and the stability region.

The goal when designing link-scheduling policies is to achieve maximum throughput while making the policies amenable for implementation [7, 8]. Link scheduling refers to the selection of a subset of links for simultaneous transmission that have the following characteristic: When the links are activated simultaneously, the interference between them is low enough to allow successful reception for every activated link. A link-scheduling policy specifies the mechanism that determines, for every time slot, a subset of links that fits this characteristic. For example, consider the network and the link (i,j)shown in Figure 1. Let this network operate under the frame structure shown in Figure 2. Therefore, in the network, time is divided into frames; each frame is divided into a control subframe and a data subframe, and each subframe is further divided into a series of time slots. Whenever link (i,j)is activated by the link-scheduling policy during a data-time slot, the link transmits a data packet. In order for the packet to be received successfully, none of the links that interfere with (i,j)can be active while (i,j)is active. Otherwise, the packet transmitted by node iis not received successfully by nodej. This is known as a packet collision at nodej, i.e., the packet transmitted over (i,j)collides with the packet transmitted over the interfering link. The set of links that interfere with (i,j)is denoted by (i,j)in Figure 1. Therefore, when (i,j)is active, none of the links in (i,j)can be active. Given that every link has a set of interfering links, only subsets of the set of all links in the network can be active at a given time. The task of the link scheduling policy is to select one of these subsets for every data-time slot. This selection is done by exchanging control information during the control-time slots.

Figure 1.

Interfering Links

Figure 2.

Frame Structure

Besides considering the interfering link sets of every link, the link-scheduling policy needs to consider the queue length of every link. In a wireless mesh network, when data packets are being transported over the flow's path, the links that form the path need to store the packets temporarily from the moment the node receives the packet until the moment the node forwards the packet to the next node in the path. Therefore, each link maintains queues of data packets for every flow that it belongs to. This is shown in Figure 3, which includes the queues of both link (i,j)and link(j,i). Each link has two queues. These are the input and output queues, which are denoted by Qi(i,j)and Qo(i,j)respectively for link(i,j). When node ireceives a data packet that needs to be forwarded to nodej, it stores the packet in Qi(i,j)first. Then, it exchanges control packets with neighboring nodes in order to determine the data subframe and data-time slot when the data packet can be transmitted to node jwithout collisions. This is done according to the link-scheduling policy of the network. Once the transmission schedule of the data packet has been determined, the packet is moved to Qo(i,j)where it waits for the data-time slot scheduled for its transmission. Finally, node iforwards the packet to node jat the scheduled data-time slot. At this point, the packet leavesQo(i,j). When node jreceives the data packet, it checks whether it is the packet's destination. If it is, the packet is no longer stored in any queue and leaves the network[1] -. If it is not, it starts the link-scheduling process again in order to forward the packet to the next node in the data flow's path.

Figure 3.

Data-packet transmissions over links (i,j) and (j,i)

When designing a link-scheduling policy, the goal is to support the largest set of data-packet rates for all the flows established in the network, and this should be done while guaranteeing the following conditions:

  • There are no packet collisions

  • The queues do not grow indefinitely

  • A given level of fairness is guaranteed for all the flows

Packet collisions need to be avoided in order to guarantee the completeness of the information being delivered to the user. Given the limited amount of memory that nodes have, the queue lengths need to be guaranteed not to grow indefinitely. Otherwise, the nodes will drop data packets when they have run out of memory to store the packets while the transmission schedules are being determined. The fairness among data flows guarantees that each flow is assigned some part of the total capacity of the network to transport information[1] -.

The mathematical formulation of this problem is based on Markovian systems [9]. In order to do this formulation, the following definitions for each node's queues need to be considered first. In Equations 1 and 2, S1jis the set of 1-hop neighbors of nodej. These are the nodes that have links with nodej. Therefore, Qijis the total number of packets stored in nodej’s 1-hop neighbors that need to be forwarded to node jand that are waiting to be scheduled, and Qojis the maximum number of scheduled packets waiting to be forwarded to node jamong all of j's 1-hop neighbors[1] -. The time indexes nand mnrepresent the nthtime that at least one control packet is transmitted in the network and the control-time slot mnwhen this takes place.


Consider the following measure of the queue lengths of all links in the network, where Nis the set of all nodes in the network, and the indexes iand oindicate whether input or output queues are being considered.


Intuitively, Vsi,o(n)can be interpreted as a total volume occupied by all of the input or output queues[1] -, depending on whether the index is ioro, and that is updated at every control-time slot in which there is at least one control-packet transmission. Vsi,o(n)increases and decreases randomly in time. It increases due to the data packets that the flows input into the network, and it decreases when data packets reach their destination and leave the network. This is shown graphically in Figure 4, which includes a network of 7 nodes. The volume of the network, shown in circles, increases and decreases according to the queue lengths in the network.

Figure 4.

Network stability

Based on the concept ofVsi,o(n), the stability of a network can be defined as follows. A network is stable if Vsi,o(n)decreases to zero with some probability greater than zero at some finite future timen+m, i.e., there is a probability that the volume of the network decreases to zero within some finite time independently of the current volume. It can be shown that this condition is met if the expectation that Vsi,o(n)decreases is greater than zero [9]. Therefore, a network is stable if Equation 4 holds[1] -.


A network becomes unstable when the rate at which data flows input packets into the network increases to a point in which the link-scheduling policy is not able decrease queue lengths fast enough to guarantee the condition given by Equation 4. Therefore, the task of the link-scheduling policy is to maintain the network stable under the constraints that there should not be data-packet collisions and that data-flows are fairly serviced.

The performance of the link-scheduling policy in performing this task is measured in terms of the set of data-packet rates for which it guarantees that the network is stable. The largest set of data-packet rates supported by the link-scheduling policy is known as the stability region. In order to compare different link-scheduling policies, these are usually compared against the optimal stability region, which is the largest region that any policy can achieve[1] -. This comparison is done using the concept of efficiency ratio, which is defined as the fraction of the optimal stability region in which a suboptimal link-scheduling policy guarantees the stability of the network. Therefore, an optimal link-scheduling policy has an efficiency ratio of unity. When the link-scheduling policy has an optimal efficiency ratio, the network is able to support the largest set of data-packet rates, and so it achieves maximum throughput.

The stability region of most link-scheduling policies depends on the interference sets of the links in the network. This can be observed, for example, in the following case that considers two links of a network. If the two links interfere with each other, only one of them can be active at a time. However, if they do not interfere with each other, they can be active simultaneously. Therefore, when they do not interfere, the links are able to support higher data-packet rates for the flows that they belong to, and this increases the size of the stability region. Given that the interference sets are determined from the network topology, i.e., from the relative distance between nodes and their transmission powers, the stability region can be modified by controlling the network topology. Therefore, for a given network with a given link-scheduling policy and a given set of end-to-end data flows, the stability region can be adapted by means of topology control in order to increase the data-packet rates supported by the links for the flows that they belong to. An example of this adaptation is shown in Figure 5. This example considers two flows. There are an initial stability region and a final stability region. The coordinates of the operating point indicate the data-packet rates of the two flows. Therefore, as the flows increase their data-packet rates, the operating point moves further away from the origin. Given that the operating point has not crossed the boundary of the initial stability region, the network is stable. After controlling the network topology, the stability region is modified such that the distance from the boundary of the region to the operating point is increased. Therefore, the final stability region allows the operating point to be moved further away from the origin without crossing the boundary. In this way, the flows are able to operate at higher data-packet rates without destabilizing the network.

Figure 5.

An example of stability-region adaptation

In the following, the operation and performance of the different link-scheduling policies is discussed. Special attention is given to reservation-based scheduling (RBDS) policies [8,11]. Then, based on the stability region of RBDS policies, the topology-control mechanisms are discussed.

2. Link-scheduling policies[1] -

The challenge in link scheduling is that the policies are highly complex. The scheduling problem in general is nondeterministic polynomial time (NP) hard [12]. Therefore, the research literature has focused on policies of lower complexity that are more amenable to implementation [7].

Most distributed scheduling policies that achieve provable efficiency ratios calculate, at the onset of every frame, a subset of links that is allowed to transmit data in the immediately following frame only. In this chapter, we refer to these policies as non-RBDS policies, i.e., they do not reserve any future frame but only the following one. On the other hand, RBDS policies [8, 11] select links to transmit data in any future frames by means of frame reservations. Since this framework considers reservations of any future frames, non-RBDS policies correspond to a special case within the RBDS framework, i.e., the case that links are allowed to reserve the next frame only.

It should be noticed that non-RBDS policies require the input queue only (i.e.,Qi(i,j)). They do not need the output queue (i.e.,Qo(i,j)) because data packets do not need to wait for future data subframes. In non-RBDS policies, once a data packet is scheduled at the onset of the data subframe, the packet is transmitted immediately.

2.1. Non-RBDS policies

The concept of optimal stability region and a centralized scheduling policy with efficiency ratio of unity were introduced in [10]. The centralized scheduling policy attempts to solve a complex global optimization problem so that the entire network is stable for the largest possible set of input data-packet rates. Under the 1-hop interference model[1] -, the problem is shown to correspond to a maximum weighted matching (MWM), where the weights of the links are determined from the length of their queues. The solution to MWM has complexity O(N3)[13, 14], where Nis the number of nodes. Under the k-hop interference model, the problem has been proven to be NP-Hard [12]. Therefore, the optimal scheduling policy is not convenient for implementation due to its high complexity. As a consequence, less complex scheduling policies that achieve only a fraction of the optimal stability region for general network topologies have been developed [12, 15-28].

The different suboptimal scheduling policies proposed in the literature can be classified according to the techniques they use to calculate the next schedule. These techniques usually depend on the interference model assumed for the network and the links' weights at the onset of every frame. Also, the suboptimal scheduling policies can be further classified according to their centralized or distributed mechanism (Unless otherwise specified, the scheduling policies reviewed in this section consider 1-hop traffic only, i.e., the data flows' paths have one link only.).

2.1.1. Centralized policies

In [15], a centralized scheduling approach known as pick-and-compare [17] that achieves the optimal efficiency ratio is defined. The pick-and-compare scheduling policy selects the optimal schedule at every frame with some probability greater than zero. First, the scheduling algorithm randomly picks a new schedule such that the links can satisfy the interference model constraints. Then, the newly picked schedule is compared with the current schedule. If the picked schedule reduces the total weight of the network (i.e., queue lengths) more than the current schedule, then the picked schedule is selected as the next schedule; otherwise the current schedule is used again. The pick-and-compare policy requires the calculation and comparison of the updated total weight for every frame. Therefore, the complexity of this technique grows linearly withN, which makes it difficult to implement in networks with a high number of nodes or in networks where nodes have low processing capabilities.

Greedy maximal scheduling (GMS) is a suboptimal, centralized scheduling policy. In GMS, the links of the network are ordered according to their weights, where the link with maximum weight is placed at the top of this globally ordered list. A valid schedule is found by selecting links from the list from top to bottom that do not interfere with each other. The complexity of GMS isO(Llog(N)), where Lis the number of links [29]. GMS has efficiency ratio of 1/2 under the 1-hop interference model [7], and under the k-hop interference model, GMS has efficiency ratio of 1, 1/6, and 1/49 for tree, geometric, and general network graphs respectively [12, 27].

2.1.2. Distributed policies

A distributed version of the pick-and-compare scheduling policy was proposed in [19]. In this policy, a node is selected with some probability less than one to initiate the calculation of a schedule for the links in its neighborhood. The new schedule is selected for the next frame if the new schedule reduces the neighborhood's weight by more than the current schedule. The algorithm has constant complexity, so it does not depend on the number of nodes of the network. It does depend, however, on the diameter of the neighborhood. The efficiency ratio increases as the diameter of the neighborhood increases. The algorithm assumes the 1-hop interference model, so it can only be directly used on networks with physical layers such as frequency-hopping code-division-multiple-access (FH-CDMA) that allow that assumption to be made.

Greedy scheduling (GS) policies [29] have been developed that achieve the same efficiency ratio of GMS [17, 25, 28]. In the GS policies, nodes calculate locally the next schedule based on the links that have the maximum local weights.

In [17, 20-23], a maximal scheduling (MS) approach is described. In this approach, maximum weight is not required to schedule a link. A link is eligible for the next schedule as long as it has enough packets in the queue to transmit during the entire duration of a frame. The efficiency ratio of MS scheduling policies is 1/κ, where κis the maximum number of non-interfering links in the interference set of any link in the network. MS policies have also been adapted to multi-hop flow scenarios[1] - in which a set of flows with their respective rates and routes are given [16, 20-23].

Lastly, distributed scheduling policies of complexity O(1)have been developed in [18, 24, 30]. These are known as constant time (CT) scheduling policies [17]. The CT approach differs from the MS approach in that when a link does not interfere with the links in a schedule, it is selected with probability less than one. Therefore, in CT scheduling policies, frames can be wasted with some probability greater than zero. In [30], CT policies are proposed for the 1-hop and 2-hop interference models[1] -. The efficiency ratios of these policies were improved in [18, 24]. In [25], the improved efficiency ratios are 121mand 2n^(121m)for the 1-hop and 2-hop interference models respectively, where n^is the maximum number of 1-hop neighboring links for any link of the network.

2.2. Reservation-based distributed scheduling

In an RBDS wireless network, the nodes negotiate with their neighbors the reservation of future data-time slots for their links. This negotiation is based on a three-way handshake that consists of a request, a grant, and a grant confirmation. Requests, grants, and grant confirmations are transmitted in scheduling packets. The nodes access the control-time slots for transmitting scheduling packets using an election algorithm. Therefore, in an RBDS wireless network, the nodes access the wireless channel using two different algorithms: the election algorithm and the RBDS algorithm, whose roles are to avoid collisions and wasted time slots in the control and data subframes respectively.

In this chapter we assume that the election algorithm is given, and we focus on the RBDS algorithm only. For example, in the IEEE 802.16 standard [31], the election algorithm is completely specified while the link-scheduling algorithm is not. The standard only specifies the control messages that can be used for the implementation of RBDS policies. We adopt the election algorithm of IEEE 802.16 wireless mesh networks with coordinated distributed scheduling. Also, it is assumed that the RBDS wireless network follows the 2-hop interference model, which is the model considered in the IEEE 802.16 standard [31].

In the IEEE-802.16 election algorithm, the nodes in every 2-hop neighborhood take turns by competing between them to access the control-time slots and transmit scheduling packets. Let the 2-hop neighborhood of nodei, i.e., nodei, its 1-hop neighbors, and its 2-hop neighbors, be denoted byS2i. We model the operation of this election algorithm as follows[1] -.

  • In order to avoid scheduling-packet collisions, no more than one node is selected in every S2iat any control-time slot.

  • The nodes inS2i, where ican be any node inN, are selected in cycles. We refer to these cycles as scheduling cycles.

  • Within a scheduling cycle, the nodes in S2iare selected once and only once each. The order in which they are selected is uniformly distributed among all the possible orders of selection.

  • The order that nodes in S2iare selected is independent across scheduling cycles.

When nodes iand jexchange scheduling messages to perform the three-way handshake, they schedule data packets on link (i,j)and multicast the negotiated schedule to all links in(i,j). The handshake consists of the following steps[1] -.

  1. Node isends a request to node jfor a certain number of data-time slots along with a set of data-time slot numbers that are available for reservation at nodei.

  2. Node jsends a grant to node ifor the requested number of data-time slots according to its set of data-time slots available for reservation and those of nodei.

  3. Node iconfirms the successful reception of the grant by echoing the grant in its next scheduling-packet transmission.

The reservation of the data-time slots takes place at steps 2 and 3. When node jtransmits its scheduling packet, j's 1-hop neighbors receive the grant and mark the granted data-time slots as unavailable. When node iconfirms the grant, i's 1-hop neighbors receive the grant and mark the granted data-time slots as unavailable too. Therefore, at the end of step 3, all links in (i,j)have made the granted data-time slots unavailable (i.e., the grant has been multicast to all links in(i,j)).

The requests and grants transmitted by the nodes are defined as follows.

Definition 1. Requestrm(i,j)(fs,fx,z), where(fs,fx,z)N3, is the request transmitted by node iat control-time slot mthat requests for link (i,j)the data-time slots of zconsecutive data-subframes starting at frame fsor any other frame afterfs. Request rm(i,j)expires at the onset of framefx.

Definition 2. Grantgm(i,j)(fs,fe), where(fs,fe)N2, is the grant transmitted by node jat control-time slot mthat assigns to link (i,j)the data-time slots of the series of frames that starts and ends with frames fsand ferespectively. Grant gm(i,j)expires at the end of framefe.

Definition 3. The length of grantgm(i,j), denoted by|gm(i,j)|, is the number of data-subframes assigned in the grant. Therefore,


In order to implement RBDS policies, each node maintains two tables per link that the node belongs to. These are the unavailable-data-time-slots table and the requested-data-time-slots table. The tables are updated with the grants and requests exchanged with the node's 1-hop neighbors. An unavailable-data-time-slots table contains the set of unexpired grants that interfere with the link that the table belongs to. This set is denoted by Tu(i,j)(m)for link (i,j)and is given by Equation 5, where (gm(x,y))feis the fecomponent ofgm(x,y), and fmis the current frame number (i.e., the frame that control-time slot mbelongs to). The requested-data-time-slots table contains the set of unexpired requests made for the link the table belongs to. This set is denoted by Tr(i,j)(m)for link (i,j)and is given by Equation 6, where (rm(i,j))fxis the fxcomponent ofrm(i,j). Tu(i,j)(m)and Tr(i,j)(m)are functions of mgiven that the tables are updated with the grants and requests transmitted at every control-time slot.


In RBDS policies, two grants overlap with each other if the frame ranges given by their respective fsand feframe numbers have one or more frame numbers in common.

2.2.1. RBDS Markovian system model

In order for RBDS policies to be mathematically characterized under the framework of network stability proposed in [10], it is necessary to show how networks that use RBDS policies can be modeled as Markovian systems [9].

In an RBDS network, each link has an input-queue and an output-queue as described in Section 3. The length of an input-queue (i.e.,Qi(i,j)(m)) is defined as the number of data packets in the queue. The length of an output-queue (i.e.,Qo(i,j)(m)) corresponds to the number of data-subframes in the following frame range: from the current frame to the last frame scheduled for the packets in the output-queue. Therefore, the length of output-queues does not depend on the number of scheduled packets waiting to be transmitted but on the schedules of those packets. The length of output-queues is given by Equation 7[1] -, where Tg(i,j)is the set of unexpired grants of link (i,j)(i.e.,Tg(i,j)(m){gl(i,j):(gl(i,j))fefm,lm}).


A node transmits scheduling packets by accessing control-time slots according to the election algorithm. The next control-time slot that node iis going to access is determined by this algorithm. This control-time slot is denoted byMi(m), i.e., at control-time slotm, the future control-time slot that node itransmits a scheduling packet is control-time slotMi(m).

Based on the previous definitions, RBDS wireless networkG=(N,), where Nand are the sets of nodes and links respectively, can be represented as a Markovian system whose state SGis given by the lengths of the input and output queues of all the links and the scheduling control-time slots of all the nodes. That is,


Within this framework for RBDS networks, the stability analysis of different RBDS policies can be performed. In the following, a greedy-maximal RBDS policy is considered.

2.2.2. The greedy-maximal RBDS policy and its stability region

The GM-RBDS policy is as follows. When any node iin Ntransmits a scheduling packet,

  • It grants the longest request among all the unexpired requests made by its incoming links, and sets the grant's fscomponent at the frame following the interfering grant that expires the latest.

  • For every of its outgoing links, it requests as many consecutive data-subframes as unscheduled data packets cover entirely, sets every request's fscomponent at the frame following the interfering grant that expires the latest, and sets every request's fxcomponent at the frame scheduled for its next scheduling-packet transmission.

When any node iin Nreceives a scheduling packet, it checks whether there is a grant in the packet and whether the grant is directed to one of its outgoing links. If that is the case, it confirms the grant only if the grant does not overlap with any of the grants in the link's unavailable-data-time-slots table.

The GM-RBDS policy is greedy maximal in the sense that the requests that are granted are the longest requests and each request corresponds to the maximum integer number of data-subframes that are covered by a link's unscheduled data packets (i.e., each request corresponds toQi(i,j)mds, where Qi(i,j)is the number of unscheduled data packets to be transmitted on link(i,j), and mdsis the number of data-time slots per data-subframe).

The size of the stability region of the GM-RBDS policy depends on the ability of the links to perform the three-way handshakes successfully. If the probability that a link finishes successfully a three-way handshake is low, the link's queue will decrease at a lower rate. Therefore, the link's ability to forward data packets within some time range is going to be lower (i.e., the highest packet rate supported by the link is lowered), and this reduces the size of the stability region. In [8], it was shown that the probability that a three-way handshake of link (i,j)is successful depends on the following aspects of the 2-hop neighborhoods of nodes iandj.

  • The set of active nodes that ican listen to but jcannot, where an active node is a node that either forwards data-packets or is the destination node for at least one flow. This set is given bySai\Saj, where Saiis the set of active 1-hop neighbors of nodei, and \refers to the relative complement, i.e.,Sai\Saj{kSai:kSaj}.

  • The degree d(i,j)of link(i,j), which is defined as the number flows that traverse link(i,j).

  • The direct 1-hop neighborhood of a node which is defined as the set of 1-hop neighbors that send data packets to the node. Therefore, the direct 1-hop neighbors of a node always precede the node in at least one flow's path. Node j's direct 1-hop neighborhood is denoted bySdj.

Based on the probability of successful three-way handshakes, sufficient conditions that guarantee queue stability under the GM-RBDS policy are given as follows[1] -.

Theorem 1. Let G=(N,)be a wireless mesh network that operates under GM-RBDS, shortest-path routing, and the 2-hop interference model, where Nand are the sets of nodes and links of the network respectively. Let λfjbe the maximum packet rate that node jcan support for each of the flows for which it is an intermediate or destination node. Gis stable if the packet rate λfjsupported by every node jin Nsatisfies Equation 9.


Therefore, in order to guarantee stability under shortest-path routing and GM-RBDS, the data-packet rate of a flow must be less than the following rate: the minimum packet rate among all the packet rates that nodes along the flow's path can assign to the flow. This is shown in Equation 10, where is the set of data flows in the network, fnis the nthflow in, pnis the path followed byfn, λnis the data-packet rate of flowfn, and λmaxjis the upper-bound for node j's rate λfjaccording to Equation 9 (i.e.,λmaxj(5iSdjd(i,j)|Sai\Saj|)1).


Remark. Notice that the sufficient condition for stability given by Equation 9 is of the same form of the condition for the non-RBDS greedy policies analyzed in [23] (Equation 4 in [23]). That is, the total packet-arrival rate of a set of interfering links needs to be lower than some constant in order to guarantee stability, and the constant depends on some characteristic of the network topology (i.e., Sai\Sajfor the GM-RBDS policy, and κfor the greedy policies in [23]). Other policies have the same behavior as well. For example, the stability properties of GMS [27] and the bipartite simulation (BP-SIM) [24] policies depend on the local-pooling factor[1] - and the maximum node degree[1] - of the network respectively, and these are determined by the network topology.

3. Stability-based topology control[1] -

In this section, we look at the problem of topology control for adapting the stability region of the backbone of the wireless mesh network to a given set of flows such that the total throughput is improved. This topology-control framework was originally studied in [34-36]. Specifically, we ask the question of what are the nodes' transmission powers (TP) that adapt the stability region to the flows in the network when a set of source-destination pairs, the routing algorithm, and the link-scheduling policy are given. Notice that by adapting the TPs of the nodes (i.e., wireless mesh routers and gateways), the topology of the network is being controlled due to the creation and elimination of links. Also, notice that the flows correspond to the traffic established across the wireless mesh routers and gateways of the network.

By adapting the stability region of the network, the queue lengths across the network are decreased in average for a given set of flows' data-packet rates. In this way, the flows among the source-destination pairs are able to maintain higher levels of end-to-end throughput and lower levels of end-to-end delay while guaranteeing queue stability. Therefore, the problem considered in this chapter is of particular interest for applications that establish non-bursty sessions between source-destination pairs such as audio/video calls.

In order to adapt the stability region, we propose an algorithm that is executed by the flows established between the source-destination pairs. The idea behind the algorithm is to adapt a lower-bound region of the stability region (i.e., a region covered by the stability region) by modifying the TPs. The lower-bound region is a widely accepted theoretical performance metric used for comparing different link-scheduling policies [23][1] -. In the algorithm, once the flows' paths are determined by the routing algorithm, the flows calculate the maximum data-packet rate they can support within the lower-bound region; then, each flow tries to stretch the lower-bound region by modifying the TP of nodes surrounding it. The effect that the stretch of the lower-bound region has on the stability region is another stretch on this region. Therefore, the result is a stability region adapted to the flows that allows them to support higher data-packet rates while guaranteeing the stability of the network. A graphical example of this adaptation was shown in Figure 5.

We consider IEEE 802.16 wireless mesh networks that operate under shortest-path routing and the GM-RBDS policy. However, our results can be readily extended to other networks, routing algorithms, and link-scheduling policies.

3.1. Stability-region expansion algorithms

The main idea presented in this chapter (i.e., adapting the stability region of a given link-scheduling policy by means of TP control) is based on the results obtained in [37, 38, 39]. In [37], the network is partitioned based on the notion of local pooling, and each partition is assigned to a channel of the network. In this way, the GMS policy is guaranteed to achieve the optimal stability region in each channel. In [38, 39], network topologies are identified for which distributed link-scheduling policies achieve the optimal stability region. However, these network topologies are not suitable for real scenarios [27] because of their sufficient conditions that guarantee the optimal stability region. These conditions include [38] 1-hop interference, 1-hop traffic, and a topology that is a graph that belongs to one of the following perfect-graph classes: chordal graphs, chordal bipartite graphs, cographs, and a subgroup of co-comparability graphs. In real scenarios, these conditions limit the suitability of wireless mesh networks. For example, only a few physical-layer technologies such as code-division-multiple-access (CDMA) can be approximated with the 1-hop interference model, and the traffic in wireless mesh networks is multihop by definition. Also, making the topology fall within the previous graph families imposes constraints on the locations and TPs of the nodes and the available routes. The multihop traffic case was considered in [38], and it was shown that only a subset of the previous graph families guarantee the optimal stability region in the multihop-traffic scenario. These were identified as forest of stars, where every connected component of the network graph is a star graph. Also, the results in [37, 38] are valid only for GMS policies under 1-hop traffic or backpressure routing-scheduling policies under multihop traffic[1] -. In [40], a random-power-selection algorithm for random-access scheduling policies was proposed. It is shown that it achieves maximal throughput in the following sense: the throughput achieved by any fixed power selection is at most equal to the throughput achieved by the random-power-selection algorithm.

Our approach is built upon the idea of [37, 38] that under certain topologies a link scheduling policy performs better. We modify realistically the network topology using TP control to adapt the policy's stability region to the flows. The algorithm receives any set of end-to-end paths, node locations, and scheduling policy, and adapts the policy's stability region to the paths. Such an approach is beneficial because it improves the end-to-end throughput and delay without the restrictions previously discussed. In this chapter, we consider the case of shortest-path routing, GM-RBDS scheduling, and randomly chosen source-destination pairs of nodes in IEEE 802.16 mesh networks.

Other heuristic algorithms have been proposed in the literature that improve the performance of the link-scheduling policy in terms of throughput by means of TP control. These algorithms include the ones reported in [41-43] whose basic idea is to increase the total throughput in the network by means of spatial reuse. The spatial reuse is increased by reducing the TP of the nodes. The algorithms differ between them in the way they are adapted to request-to-send (RTS)/clear-to-send (CTS) based protocols. In [44, 45], it is shown that better throughput improvements can be achieved not only by decreasing the TP to increase the spatial reuse but also by considering the hidden and exposed nodes. The algorithms proposed in [44] perform TP control with the objective of avoiding hidden nodes. In this way, the links in the network are able to sustain higher data-packet rates. In [46], a TP control algorithm for RTS/CTS-based protocols is proposed that decreases the area occupied by links during their transmissions, which is defined as the area in which other nodes must remain silent during the time the link is active. Then, it is shown that with this scheme, routing algorithms that favor short hops achieve higher levels of throughput. The goal of our algorithm is similar to the goal of the previous algorithms [41-46], i.e., to increase the data-packet rates that a given link-scheduling policy can support by means of TP control. However, our approach differs in that it is directly based on a quantitative metric which is the stability region. It is not based on qualitative observations of the operation of the link-scheduling policy such as the hidden and exposed nodes in RTS/CTS-based policies. Therefore, it can be readily adapted to any link-scheduling policy whose stability region has been characterized such as the ones discussed in Section 4.

A different type of TP control algorithms, which are based on optimization techniques, are discussed in [47, 48]. In [47], the problem of integrated link scheduling and TP control for throughput optimization is shown to be nondeterministic polynomial time (NP) complete. Therefore, a heuristic algorithm is developed. The goal of the algorithm is to minimize the schedule length necessary to satisfy all the link loads determined by a given routing algorithm. By minimizing the schedule length, the total throughput of the network is increased because more scheduling cycles can be performed per time unit. In [48], the problem of jointly optimizing the flow routes, link schedules, TP, modulation and coding schemes is addressed. This is a more general problem than the one considered in [47] given that it does not only include the calculation of TPs and link schedules but also includes the routing and physical layers (i.e., flow routes, modulation, and coding schemes). In our algorithm, we are only concerned in the TP control problem when the flows and link-scheduling policy are given. That is, for a given set of flows, we determine TPs that improve the performance of the link-scheduling policy in terms of throughput and end-to-end delay.

3.2. The HSRA-topology-control algorithm

The goal of our TP control algorithm is to expand the lower-bound region given by Equation 10. By expanding this region, the flow rates λncan take higher values while guaranteeing stability, and therefore, the maximum total throughput the network can support for the given flows is increased. Let the maximum total throughput be denoted by λTand defined in terms of the lower-bound region for the flows' data-packet rates given by Equation 10 as follows.


According to Equations 11, 10, and 9, λTdepends on the direct 1-hop neighborhoods (i.e.,{Sdj:jN}), the link degrees (i.e.,{d(i,j):(i,j)}), and the active 1-hop neighborhoods (i.e.,{Saj:jN}) as follows.


Given that the flows are determined by the shortest-path routing algorithm, the following parameters in Equation 12 are fixed:{pn}, {Sdj:jN}, and{d(i,j):(i,j)}. Therefore, in order to increaseλT, the only parameters that can be modified are the active 1-hop neighborhoods (i.e.,{Saj:jN}). They can be modified by means of TP control such that λTis maximized. This optimization problem, which we call stability region adaptation for throughput maximization (SRA-TM), is given as follows.

Definition 4. Given a set of flows calculated by the shortest-path routing algorithm, the SRA-TM problem consists of the maximization of λTby means of TP control such that none of the nodes exceed the maximum TP and none of the paths are broken. That is,

maximizepn(minjpn15iSdjd(i,j)|Sai\Saj|)subject to0rirmaxiNri,rj||i,j||iSdj,jN,E14

where riis the transmission radius of nodei, rmaxis the maximum transmission radius, and ||i,j||is the Euclidean distance between nodes iandj.

Remark. In the SRA-TM problem, the flow paths are given and left unmodified. Higher values for λTcould be achieved if the flow paths were modified by including them as decision variables. For example, a routing scheme can uniformly distribute the traffic loads across the links of the network so that links with high levels of congestion are avoided. This problem corresponds to a joint optimization of the topology and flow paths based on the stability region. This problem can be further studied due to its potential benefits onλT. However, this chapter deals only with the stability-region-based topology control as a first step towards the problem of stability-region-based joint topology and routing control.

Remark. If the data traffic in the network changes dynamically, the flow paths may change as well. In this scenario, the SRA-TM problem needs to be solved for every flow-path change. Therefore, the speed of convergence of algorithms that solve the SRA-TM problem is an important metric for such a scenario. The algorithms should be able to keep up with the rate of change of the flow paths. On the other hand, if the data-traffic levels of a set of flows change but the flow paths do not change, the SRA-TM problem does not need to be solved again. The reason is that the solution of the SRA-TM problem is the topology that allows those flows to support the maximum level of data traffic while guaranteeing stability. This means that the data-traffic levels in the flows may vary as long as they do not exceed such maximum levels (i.e.,min{λmaxj:jpn}fn), and this can be guaranteed by means of call-admission-control algorithms.

In order to solve the SRA-TM problem, the following TP algorithm is proposed. It is called heuristic stability region adaptation (HSRA)[1] -.

The following definitions are necessary for the operation of the HSRA algorithm.

Definition 5. The bottleneck node of flow fnis the node with the lowest maximum rate among all the intermediate and destination nodes of the flow, i.e., let jbe the bottleneck node offn, thenj=argmini{pn(m):2m|pn|}λfi, where pnis the set of nodes in the path of flowfn, pn(m)is the mthnode inpn, and |pn|is the number of nodes inpn.

Definition 6. Node his hidden from node jif and only if hSai\Sajfor someiSdj.

Definition 7. The MinPower setup is the set of minimum TPs whose transmission ranges guarantee that none of the links of the flows in is broken.

The operation of the algorithm is as follows. First, the nodes' TPs (i.e.,{ri:iN}) are set according to the MinPower setup (line 2 of the HSRA Algorithm). By reducing the TPs (Definition 7), the spatial reuse in the network is increased, and as a consequence, the total throughput is increased as well[1] -. Then, the maximum throughput that intermediate and destination nodes can support for the flows they belong to is calculated (line 3 of the HSRA Algorithm). This is done using Equation 9, which defines the nodes' maximum throughput. Based on these maximums, the total throughput the network can support is calculated (line 4 of the HSRA Algorithm).

Figure 6.

Once the total throughput under the MinPower setup is known, flows are selected randomly one-by-one for a number of fntimes (line 5 of the HSRA Algorithm). Every time a flow is selected, the maximum throughput the flow can support is increased if this causes that the total throughput be increased as well. Otherwise, the flow is left unmodified. The throughput of the selected flow is increased as follows.

Let the selected flow be denoted by fn(line 6 of the HSRA Algorithm). The bottleneck node of jis found first by tracking the node of the flow with the lowest maximum throughput (Equation 10). Let this node be denoted by j(line 7 of the HSRA Algorithm). The maximum rate of λfj(i.e.,j) is increased by increasing the TP of one of λT's 2-hop neighbors (lines 8 to 15 of the HSRA Algorithm). However, this TP increase is confirmed only if the total throughput (i.e.,j) is increased as well (lines 16 to 20 of the HSRA Algorithm). Otherwise, the TP of j's 2-hop neighbor is left unmodified (line 22 of the HSRA Algorithm). The total throughput may be decreased given that the TP increase of j's 2-hop neighbor may decrease the maximum rate of other bottleneck nodes in the network, and this maximum-rate decrease may be higher than the increase on j's maximum rate.

The 2-hop neighbor of node |Sai\Saj|whose TP is increased is selected so that the factor λfjon the denominator of the upper-bound for jis decreased (Equation 9). Qualitatively, this TP increase can be explained as follows. Node Sdj(i.e., the bottleneck node) has a set of 1-hop neighbors that are sending data packets to it (i.e.,i). Let (i,j)be one of these nodes, and consider the link Qi(i,j)and the input and output queues Qo(i,j)and iof node ias shown in Figure 3. In order for jto transmit packets toi, a reservation of future data-time slots is required. When nodes jand ifinish this reservation successfully, data packets in node Qi(i,j)'s input-queue (i.e.,i) are moved to node Qo(i,j)'s output-queue (i.e.,Qo(i,j)), and these packets are later pulled from Qi(i,j)for their transmission. Therefore, for the queues Qo(i,j)and jto have their lengths decreased, the reservation performed by nodes (i,j)and ineeds to be successful, i.e., the three-way handshake for scheduling data-packet transmissions on link jneeds to be successful. The probability that the handshake is successful and that the queues decrease their length depends on the grants received by node iand not received by nodej. In the following, we refer to these grants as hidden-grants. If irequests future data-time slots to jand a hidden grant is received by ibefore jtransmits its grant toi, j's grant may not be confirmed byj. This is because the hidden grant may interfere with j's grant. On the other hand, if iis able to listen to the hidden grant, jis able to generate its grant such that it does not interfere with the hidden grant, and jwill be able to confirm j's grant[1] -. Therefore, in order to increase the probability of handshake success and queue decrease, the TP of the node that transmits the hidden grant (i.e., the node hidden fromj) can be increased such that node jis able to listen to the hidden node's transmissions.

Node Sai\Sajmay have more than 1 hidden nodes in every incoming link from the nodes in its direct 1-hop neighborhood. The HSRA algorithm chooses only one of those hidden nodes for increasing its TP. The node that is chosen is the node that is hidden from the highest number of nodes (i.e., node Sai\Sajand all the other intermediate or destination nodes unable to listen to the hidden node). This is performed in lines 8 to 12 of the HSRA Algorithm. In this way, the maximum rate is increased for all those nodes so that, if one or more of those nodes are bottleneck nodes, higher improvements on the total throughput can be achieved.

The role that the objective function of the SRA-TM problem (Equation 13) plays in the HSRA Algorithm is the quantification of the throughput improvement by the TP increase on hidden nodes. By increasing the TP of a node hidden from a bottleneck node, the factor rmax=0.3in the denominator of Equation 13 is decreased for the bottleneck node, and as a consequence the bottleneck node's maximum rate is increased. However, the TP increase on the hidden node may also cause an increase on the rmaxfactor of other bottleneck nodes. Therefore, the objective function allows the algorithm to trade off between decreasing the number of hidden nodes by increasing TP and maintaining spatial reuse by not increasing TP. In the algorithm, this tradeoff is achieved by testing the improvement on the total throughput (lines 14 to 23 of the HSRA Algorithm).

4. Simulation results

The performance evaluation of the HSRA algorithm was performed by means of simulation using the simulator proposed in [49]. The simulated network is an IEEE 802.16 mesh network with distributed scheduling under the configuration shown in Table 1. The number of nodes was specified as a simulation parameter. The nodes were uniformly distributed in a square area such that the node density was always kept at 15 nodes per unit area. The maximum transmission range of the nodes was set at 0.3 (i.e.,rmax). The connectivity of the network under bidirectional links and with the nodes' transmission ranges set at was confirmed before executing the shortest-path routing algorithm. The number of flows was specified as a simulation parameter. The source and destination nodes of every flow were uniformly distributed among all the nodes in the network. The shortest-path routing algorithm calculated the flow paths under the MaxPower setup which is the power assignment when all the nodes' transmission ranges are set at the maximum (i.e.,rmax). Once the paths were calculated, the transmission ranges of the nodes were found using the HSRA algorithm. Also, the optimal transmission ranges (i.e., the solution to the SRA-TM problem (Equation 13)), which we call OptPower, were found in [34] using the formulation of the SRA-TM problem as a mixed integer program with non-linear constraints (MIP-NLC). The MIP-NLC was solved using the Branch And Reduce Optimization Navigator (BARON) Solver [50], which is a system for solving non-convex optimization problems to global optimality. Finally, the network was simulated under the MaxPower, MinPower, OptPower, and HSRA setups.

Frame length10 ms
Control-time-slot length63 µs
Number of control-time slots per frame4
Number of data-time slots per frame256
Link schedulingGM-RBDS

Table 1.

IEEE 808.16 mesh network configuration

[] This is a parameter of the election algorithm used t specify the frequency that nodes transmit scheduling packets.

Figure 6 shows the average output-queue length for three networks with 20 nodes each and increasing number of flows (i.e., 10 flows in Figure 6a, 15 flows in Figure 6b, and 20 flows in Figure 6c). The input-queues have been omitted because they are guaranteed to always be stable [8, 11]. The flow rates in each network were all set at the same value. These are 8, 6, and 5 packets per frame for the networks in Figures 6a, 6b, and 6c respectively. These values were set so that their corresponding HSRA network became unstable if they were increased by at least one point. In this way, the network operates at a point inside the stability region and close to its boundary. Therefore, when any of the rates is increased by at least one point, the network operates outside the stability region, and therefore, it is unstable.

Figure 7.

Average output-queue comparison for the HSRA, MinPower, MaxPower, and OptPower configurations

Close to the end of the simulation time, when the transient behavior of the queues is over, the average queue lengths of the different power setups (i.e., MaxPower, MinPower, OptPower, and HSRA) can be compared. In Figure 6a, the MaxPower setup has the worst performance (i.e., the largest average queue length), and the MinPower, OptPower, and HSRA have similar performance. Therefore, when the number of flows is low (i.e., 10 flows), the MinPower and the HSRA algorithms are able to achieve queue lengths that are close to the lengths achieved by the optimal solution (i.e., OptPower). On the other hand, when the number of flows increases, the MinPower algorithm does not achieve a performance close to the optimal one while the HSRA algorithm does. This is shown in Figures 6b and 6c. The MaxPower and MinPower algorithms have similar performance which is worse when compared with the HSRA algorithm. The HSRA algorithm achieves average queue lengths that are close to the lengths achieved by the optimal solution. Therefore, the HSRA algorithm enables the flows to carry more traffic while guaranteeing stability than the MaxPower and MinPower algorithms do. Also, it is confirmed that the technique of only maximizing the spatial reuse by reducing the transmission ranges (i.e., MinPower) does not perform well when the flow density increases (i.e., when the number of flows increases and the number of nodes is kept constant.). On the other hand, the technique of adapting the stability region to the given set of flows by means of TP control (i.e., HSRA) does perform well when the flow density increases.

5. Conclusion

A new framework for the stability analysis of scheduling policies for wireless networks that allow the reservation of future data-subframes has been proposed. The concepts of input-queue and output-queue were introduced into the framework in order to account for the packets waiting to be scheduled and the schedules assigned to these packets. Based on these concepts, sufficient conditions for the stability of RBDS wireless networks were found.

Within the proposed framework, an RBDS policy which uses the concept of greedy-maximal scheduling was analyzed. The nodes implement this policy by exchanging scheduling packets using the IEEE 802.16 election algorithm. A region in which the proposed reservation-based scheduling policy is stable was found using the framework. It was shown that the size of this region depends on a characteristic of the network topology (i.e.,).

The HSRA algorithm has been proposed for transmission power control. This algorithm increases the data-packet rates that flows can support and decreases the end-to-end delays. It is based on the adaptation of the stability region of a given link-scheduling policy when only the links that belong to a given set of flows are considered. The algorithm can be readily adapted to any link-scheduling policy whose stability region has been characterized, so it is not limited to any specific scheduling approach such as RTS/CTS-based policies. The improvement on throughput achieved by our algorithm was evaluated by means of. It was shown that it outperforms the classical solution of reducing transmission powers to increase spatial reuse.

Future lines of research include the development of a new framework for distributed topology-control algorithms. For example, this framework could based on a game-theoretical approach in which a given set of flows act as players that collaborate to maximize the packet rates they can support while guaranteeing stability. Also, based on the new framework, new distributed topology-control algorithms should be developed for IEEE 802.16 WMNs. Finally, the algorithms should be implemented and tested on WMN testbeds in order to evaluate the improvement in throughput they achieve in a real scenario.


  • In this chapter, topology control refers to the problem of controlling the creation and elimination of wireless links and the interference between them by controlling the transmission power of the nodes.
  • Actually, node j sends the data packet to its application layer so that the packet's content can be finally delivered to the user.
  • It should be noted that there is not an absolute definition for fairness. For example, the network operator may be interested in assigning the same maximum data-packet rates to all flows or different maximum rates to different flows depending on the demands of the users.
  • The actual length of has a more involved definition. However, for the sake of clarity, we do not consider the exact definition until Section 4.2.1.
  • In the theory of Markovian processes [9], is known as a Lyapunov function.
  • denotes the expected value of given .
  • The optimal stability region and the link-scheduling policy that achieves it were characterized in [10].
  • The material presented in this section is based on the material presented in [8, 11].
  • In the 1-hop interference model, only the links that the 1-hop neighbors of a node belong to interfere with the links that the node belongs to.
  • A multi-hop flow has a path that is at least 2 links long.
  • In the 2-hop interference model, only the links that the 1-hop or 2-hop neighbors of a node belong to interfere with the links that the node belongs to. The 2-hop neighbors of a node are the nodes that have a shortest path to the node of length 2 links.
  • The operation of the election algorithm for IEEE 802.16 mesh networks with coordinated distributed scheduling is described in detail in [32, 33].
  • It is assumed that in this handshake node grants node's request and that the data-packet-slot reservation is successful at both and .
  • is the positive-part operator.
  • The proof of Theorem 1 is given in [34].
  • The local-pooling factor is a topological property of the network that indicates how different the effectiveness of the different maximal link schedules is from each other [27]. When the different maximal link schedules are similarly effective, GMS policies are able to support packet rates that are closer to the boundaries of the optimal stability region.
  • The node degree is defined as the number of links that the node belongs to.
  • The material presented in this section is based on the material presented in [34, 36].
  • The reason for this is that the exact formulation of the stability region is not actually available. The stability region is usually characterized with the lower-bound region because its exact characterization is not feasible due to its complexity. See [8, 10, 11, 16, 18, 19, 23-25, 29, 30] for the literature on the problem of characterizing the stability region of link-scheduling policies.
  • It should be noted that the objective in [37, 38] was mainly to identify the topologies that enable the optimality of the GMS policy, and not to design topology-control algorithms.
  • The SRA-TM problem is formulated as a mixed integer program with non-linear constraints in [34]. This formulation is used in Section 6 for calculating the optimal solution of the simulated instances of the SRA-TM problem.
  • This spatial-reuse-based TP control is the basis of the algorithms proposed [39-43, 46].
  • The problem of node j not being able to listen to hidden grants is the hidden-node problem version for reservation-based distributed scheduling policies. This problem is studied in detail in [8, 11].

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Gustavo Vejarano (August 14th 2012). Stability-Based Topology Control in Wireless Mesh Networks, Wireless Mesh Networks - Efficient Link Scheduling, Channel Assignment and Network Planning Strategies, Andrey V. Krendzel, IntechOpen, DOI: 10.5772/48576. Available from:

chapter statistics

1110total chapter downloads

1Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Channel Assignment Using Topology Control Based on Power Control in Wireless Mesh Networks

By Aizaz U. Chaudhry and Roshdy H.M. Hafez

Related Book

First chapter

Optical Fiber Sensors

By Marcelo M. Werneck and Regina Célia S. B. Allil

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us