# Distributed Resource Reservation for Beacon Based MAC Protocols

Frank Leipold, Jörg Eberspächer

► To cite this version:

Frank Leipold, Jörg Eberspächer. Distributed Resource Reservation for Beacon Based MAC Protocols. 16th EUNICE/IFIP WG 6.6 Workshop on Networked Services and Applications - Engineering, Control and Management (EUNICE), Jun 2010, Trondheim, Norway. pp.217-225, 10.1007/978-3-642-13971-0_21. hal-01056494

HAL Id: hal-01056494

https://inria.hal.science/hal-01056494

Submitted on 20 Aug 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Distributed resource reservation for beacon
based MAC protocols

Frank Leipold¹ and Jörg Eberspächer²

¹ Sensors, Electronics & Systems Integration
EADS Innovation Works Germany
frank.leipold@eads.net

² Institute of Communication Networks
Technische Universität München
joerg.eberspaecher@tum.de

**Abstract.** Wireless connected devices become increasingly popular in a large variety of applications. Consumer electronics most certainly is the field with the most wireless innovations in the past years; but also other areas, such as medical equipment, vehicular on-board networks or maintenance services, experience an increasing demand for wireless communication. Additionally the networks should *just work* and require as little maintenance as possible. Hence future WLAN and WPAN must be self-configuring, self-healing and distributed to provide flexible usage. Assuming a homogeneous distributed MAC protocol with a beacon based reservation mechanism, a radio resource reservation algorithm is developed to fulfil the delay and data rate requirements from the devices. It uses a game theoretic approach to achieve infrastructure-less design and still provides fair resource allocation. Changes in the radio channel, failing devices or links and mobile nodes are detected and a reorganisation of resources is calculated.

# 1 Introduction

The constantly increasing performance demands for wireless high speed connec-
tions is the motor to further enhance existing technologies and to invent new and
innovative communication interfaces. For wireless local area networks (WLAN)
several candidates have been developed in the past years. The recently approved
IEEE 802.11n standard achieves up to 600 Mbits/s, by using MIMO (multiple-
input-multiple-output) technology.

High data rates can also be easily achieved by using ultra wideband (UWB) as
the bandwidth of more than 500 MHz provides plenty resources. The WiMedia
standard [1] is capable of 480 Mbit/s with one single channel. The recently
published upgrade even allows 1024 Mbit/s. This is done with one single antenna
(hence no MIMO), which implies less complex transceivers.

One significant difference between WiFi and high-speed UWB is the transmit
range. Due to the strict power limitations of at most -41.3 dBm/MHz for UWB,
defined from the FCC [2], and mostly followed by other regulatory organisations,
high data rate UWB has a typical range of about 10 meters. It also underlies
more intense spatial limitations given by walls and other obstacles. This is often
interpreted as a handicap of UWB, but it actually also implies two significant
advantages. First it reduces the congestion in the wireless channel. For instance
the IEEE 802.11b/g technology is currently often used in home applications.
But the standard has only three non-overlapping channels (respectively four in
Japan). Thus in apartment houses, where most flats have their own WiFi access
point (AP), the channels are very crowded as the technology can achieve 20 to
100 meters transmit range even in indoor scenarios. With UWB the radio sig-
nals are almost confined to the individual apartments and the contentions for
the wireless channels get relaxed. There will be less wireless systems sharing the
common resources. The second advantage is the reduced risks of being eaves-
dropped. The attacker must be in very close proximity to successfully receive
the UWB signals. Eavesdropping becomes much more difficult and the risk of
falling victim to an attack declines.

Even though WiMedia is a fully distributed algorithm, without any coordi-
nating nodes such as a WiFi-access-points, the network still has service providing
access points, for instance a node that is connected to a LAN and operates as
a bridge between the LAN and the WiMedia network to enable access to the
Internet. These WiMedia (or UWB) APs do not have any special role in terms
of the PHY or MAC protocol.

Using UWB for WLAN applications requires a larger number of APs. For
the office scenario about each room requires at least one AP, depending on
the size of the room. This makes the network management more complex. For
now usually the WiFi networks are managed by maintenance personnel, but
with a large number of APs to manage, this becomes a very complicated task.
Several automated resource management algorithms for WLAN systems have
been proposed yet. For WiMedia little work has been done on this subject. With
its completely distributed algorithms the existing approaches can not be used
efficiently.

In an earlier work [3] an integer optimization algorithm was presented to
calculate the optimal AP placement and resource allocation plan for WiMedia
networks. It is very complex and time consuming algorithm that will run during
the design phase of the network. But during the operation of the network changes
to the wireless channel will occur and a fast adaptation to the new conditions
must be made. Depending on the size of the network a centralised optimisation
may take too long. A distributed approach is preferred.

Our applications target wireless on-board networks for public transportation
vehicles, such as aircraft. Cabin management systems, containing reading lights,
signs, speakers, small displays, shall be connected wireless to reduce produc-
tion and maintenance costs and to make the cabin layout more flexible. UWB
currently is the most promising technology that provides a very robust radio
channel for the aircraft environment [4], high data-rates and no licensing prob-
lems. Furthermore the network shall have self-healing capabilities and adapt
quickly to failures and changes. Therefore the resource management algorithm
should be distributed and enable the network to operate with the best possible configuration even when some parts are failing completely.

The network management of the public transportation scenario is not very different from an office environment or home consumer electronics. Therefore the gained results in this paper can be easily applied to other situations, where devices must be connected to service access points.

The rest of this paper is organised as followed. Section 2 describes features of WiMedia relevant to this work. Section 3 describes briefly game theory and some related research. In section 4 the distributed resource management algorithm is presented. Finally section 5 concludes this paper.

## 2 Unique WiMedia features

The WiMedia standard and also other possible standards that use a distributed beacon based MAC implementation, has some unique features, which are of value for the resource management.

WiMedia is completely infrastructure-less, meaning all nodes have the same physical and MAC capabilities. Unlike in other common protocols there is no coordinator or MAC level access point. The protocol uses periodic superframes containing a beacon period and a data period; see Figure 1(a). All nodes allocate a beacon slot in the beacon period, regardless if they have to transmit user data or not. This slot is fix over time and changes only in rare conditions. For DRP (distributed reservation protocol) channel access the beacons are used to announce transmissions and reserve parts of the data period, the so called MAS (media access slots). Conflicts are identified early and collisions can be mostly avoided. The only collisions may occur in the beacon slot allocation process.

The beacons contain details of all upcoming transmission in the data period. This means a single node knows when a neighbour communicates with another node. This feature makes WiMedia not susceptible to the *hidden station problem* and it does not need RTS/CTS messages.

With the beaconing a hard limitation of WiMedia applies. The beacon period has only 96 beacon slots with two slots reserved for special functions. This means no more than 94 nodes must be within range on the same channel. The group of nodes within transmit range of a subject node is called *beacon group* (BG). Each node includes the members of the BG and the respective beacon slot ids into its own beacon; hence it is broadcasting this information to the surrounding nodes. Furthermore the standard also defines the *extended beacon group* (EBG), which is the set of nodes representing the neighbour's neighbours. Figure 1(b) shows the BG and the EBG of a node. A newly activated node picks a beacon slot that is not occupied by a node of the BG nor from the EBG. This rule implies that for any given node the beacon slot ids of the BG members must be unique, otherwise they would cause collisions. For the EBG members the ids can be identical, because the subject node can not listen to them, but must not transmit at the same time as it would cause collision at the node that has the subject node and the EBG-node in its BG.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** WiMedia beacon groups: Figure (a) shows the beacon period and data period of a superframe. In (b) the relation of the beacon group and the extended beacon group are shown.</figcaption></figure>

The consequence of overlapping areas in WiMedia is the extension of the EBG. When a border node is within range of two APs, it will add parts of the second AP nodes to its BG, which again appear in the EBG of the first AP. Hence overlaps increase the extended beacon group size and therewith limit the maximal node density.

The beacon group size is directly related to the node density and transmission range as slots may only be occupied by one node. The extended beacon group size additionally depends on the activation sequence of the network, as for a single node the neighbour's neighbours beacon slots may be identical.

## 3 Game theory for resource management

For the distributed resource management algorithm presented in this work, one key feature is to have a fair resource allocation. Nodes should not act selfishness and occupy wastefully available resources. The objective of the algorithm is to maximize the overall efficiency of the network. Hence nodes must not only take their own situation into account, but also those of the surrounding nodes.

The game theory is capable of defining fair and distributed algorithms. It originates from economics in the 40's, but has also been applied to biology, engineering, political science, computer science, and philosophy. The problem is
defined in a strategic game with a set of rational players. Each player tries to
maximise its payoff function by choosing the best strategy and also by taking the
actions of the other players into account. Usually the players strategies will result
in an equilibrium, for instance the Nash equilibrium, where no player can change
the own strategy without decreasing its payoff. Many different types of games
have been developed: cooperative or non-cooperative, symmetric or asymmetric,
zero-sum or non-zero-sum, simultaneous or sequential, just to name a few.

Game theory has been proposed for resource management in wireless networks for all kinds of technologies. For IEEE 802.11 the authors of [5] present a game to share the available radio channels. The payoff function based on transmission delay, channel access length and throughput. In [6] an algorithm for OFDM based communication is described that minimizes the transmission power, while still achieving the QoS requirements of the system. For IEEE 802.16 networks [7] presents a game definition to control the amount of bandwidth given to new connections, with respect to delay, throughput and other QoS parameters in the network.

Even though the amount of available resource management algorithms based
on game theory is huge, no one handles a comparable system to that of a Wi-
Media network. The distributed beaconing mechanism and DRP channel access
scheme is unique. The priority for a WiMedia network lies in the efficient MAS
allocation. To utilise the WiMedia features a new resource management algo-
rithm is required.

## 4 Algorithm

The resource management algorithm assumes APs with fix locations. Further-
more the network consists of a wired backbone that connects the APs. The APs
provide the service for wireless end devices to get access to the wired back bone
network.

The MAC mechanism for the WiMedia nodes shall be DRP. For the aircraft
scenario DRP is essential, as it provides guaranteed resources to the end devices.
The QoS requirements for end devices are defined in required data rate and max-
imum time delay. Assuming only one MAS is reserved per end device and taken
into account the 64 ms of a superframe, the delay of an message over the UWB
link can be nearly 64 ms. For applications with smaller delay requirements, the
resource management algorithm must reserve two or more MAS per end device
with maximum gaps between the MAS. The possible delays will be reduced.

Despite the mentioned DRP reservation scheme the network may also use the
alternative channel access PCA (prioritized contention access) for non critical
applications. MAS that are not completely used by the owing device can be
released and used for PCA, a CSMA like access scheme. This way the unused
MAS sections can still be used for applications where collisions can be tolerated.

The following two lists show input and output parameters of the algorithm:
**Input parameters**

* Link quality

* Devices per AP

* BG/EBG size

* Bandwidth utilisation

* Delay requirements

**Output parameters**

* Channel allocation

* MAS reservation

The link quality is given in RSSI (received signal strength indicator) or LQE (link quality estimator). Both are defined in the WiMedia standard and should be accessible from the application layer.

It is assumed that an optimal configuration of the network is known. This can be obtained from calculations in the design phase of the network. These calculations are usually very intensive and take a long time. Therefore they can not be performed in-time during the operation of the network.

Efficiency in a WiMedia network using DRP can be defined as the configuration with the minimal used MAS, which again implies the minimal usage of resources and maximum remaining bandwidth. In the following notation $O_n$ stands for the number of owned MAS from node $n$. A node owns a MAS when it has reserved this MAS for transmissions or reception in the beacon period. $R_n$ stands for the number of reserved beacon slots in the beacon period of node $n$. This can be owned MAS, MAS owned by surrounding nodes or MAS marked as occupied from alien nodes. Furthermore the raised indices $o$ and $e$ indicate if the value is the optimal solution, or the effectively current allocation. Finally the second raised indices $r$ or $i$ show if the value must be an integer or a real. The integer notation represents the number of owned or reserved MAS. The real notation indicates how much of that MAS will actually be used according to the data rate requirements. Two examples will demonstrate the notation: $O_n^{o,i}$ are the owned MAS slots by node $n$ for the optimal solution and integer counting, $R_n^{e,r}$ are the effectively used MAS of node $n$ in real counting.

The effectiveness of the nodes is defined in two different ways. For the end devices the effectiveness is:

$$E_n^{ED} = \begin{cases} \frac{O_n^{o,r}}{O_n^{e,r}} & \text{0, if data rate or delay requirements fail} \\ 0 & \text{, if data rate or delay requirements fail} \end{cases} \quad (1)$$

An effectiveness of 1 is the optimal solution; for sub-optimal solutions the numerator increases and the effectiveness closes zero. The notation in real values is used, to get a difference in the equations for increased transmit data rates, but still only using one MAS. For instance a node with low bandwidth requirements must always reserve at least one MAS. This can mean that even for the lowest possible and highest possible data rate still only one MAS is required. To reward nodes switching to a higher transmit data rate and thereby less occupy the channel, a real notation for the number of owned MAS is used. A higher data rate $E_n^{ED}$ will change the efficiency of that end device to the positive.

For APs the effectiveness uses the sum of the number of used MAS (integer counting). An AP has to maintain reservations to the end devices, which can
only be done in complete MAS slots. Consider a node with low bandwidth requirements, but strict timing delays. Optimally it could operate with two MAS slots. But due to already existing reservations no combination of two MAS might be available to satisfy the timing requirements. Hence a combination of three MAS must be used. If using the real counting of MAS, as for the end devices, no difference of the AP effectiveness would be measurable; the summed effectively used MAS portion would stay the same. But with the integer counting the extra MAS is measurable. The effectiveness of an AP is defined as:

$$E_n^{AP} = \begin{cases} \frac{R_n^{o,d}}{R_n^{o,d}} & \text{if 90-100\% of the available MAS required} \\ \frac{R_n^{o,d}}{AR_n^{o,d}} & \text{if more than 100\% of the available MAS required} \end{cases} \quad (2)$$

The parameter A in the numerator for the case of 90-100% MAS utilisation must be greater 1. It artificially degrades the efficiency and prevents an AP of being overloaded and shifts AP assignments from end devices to surrounding APs if possible.

The utility function of each node is the sum of the efficiency of all nodes (end devices and APs) within range. Each node tries to maximize the utility function. For an end device the utility function is:

$$U_n = E_n^{ED} + \sum_{o \in D} E_o^{ED} + \sum_{p \in A} E_p^{AP} \quad (3)$$

For an AP the utility function is:

$$U_n = E_n^{AP} + \sum_{o \in D} E_o^{ED} + \sum_{p \in P} E_p^{AP} \quad (4)$$

D is the set of end devices on the same channel that are in range of node n. In analogue P is the set of APs on the same channel in range of node n.

Each node (AP and end device) has an algorithm implemented to calculate the MAS reservations, depending on the selected channels. This algorithm takes the APs as subject nodes and iterates the end device nodes in range and on the same channel. The end device with the earliest delay requirement will be served first and gets assigned the closest MAS to or below the delay. This is repeated, until all nodes have enough MAS to satisfy the delay, afterwards random MAS are assigned, to match possible data rate requirements. Each node must have at least one MAS per superframe.

To provide the required information of the surrounding nodes, the QoS requirements, neighbourhood relation and currently superframe structure is exchanged on a two-hop distance.

Each end device can choose which AP in range it selects. The decision uses the utilisation function. An end device compares the existing utilisation value and the to be obtained value when changing the AP by calculating the MAS reservations and utilisation value of the new setup. An access point change is only done, when an utilisation gain exists.
Analogous the APs also recalculate the MAS reservation and utility value, with changing channel selection.

Finally the processes for the end devices and APs of the distributed resource management algorithm based on game theory are as followed:

**End device**

1. Scan all channels for APs

2. Calculate MAS reservations and $U_n$ for channels with APs in range

3. Select the channel with the best $U_n$

4. Periodically rescan other channels

**Access point**

1. Select channel (no AP or AP with worst RSSI)

2. Try to increase $U_n$ by investigating possible channel change

3. Select channel with best $U_n$

4. Periodically recalculate

Mobile nodes are also supported. Therefore the optimal solution is calculated without them. Later, the mobile nodes are included in the system as a regular end device. They will lead to a constantly higher utilisation value, but still the algorithm finds the same fair solution.

**5 Conclusions**

In this work a resource management algorithm based on game theory for high data rate UWB networks was presented. The network consists of service access points, which provide access for wireless end devices to a wired network, such as LAN or Internet. The algorithm achieves a fair distribution of resources and adapts to changes in the radio channel or topology. Network efficiency is based on the number of used MAS slots, which also encompass bandwidth and timing requirements. The MAS reservation algorithm is essential for scenarios with high MAS utilisation, as the efficiency of the overall algorithm is tightly coupled to the efficiency of the MAS reservation for large loads.

The distributed approach does not require a dedicated node to compute the network parameters. Hence whatever parts of the network are failing, the network still tries to connect as many nodes to the APs as possible. The algorithm can be used in various applications: on-board networks, office and home WLAN or ad-hoc communication.

**References**

1. ECMA International, "ECMA-368: High Rate Ultra Wideband PHY and MAC Standard - 3rd Edition," December 2008.

2. FCC, "Report and Order. FCC 02-48," April 2002.

3. F. Leipold and S. Bovelli, "Requirements for Radio Resource Management in Multi-cell WiMedia Networks," in *ICT-MobileSummit*, 2009.
4. J. Chuang, N. Xin, H. Huang, S. Chiu, and D. Michelson, "UWB Radiowave Propagation within the Passenger Cabin of a Boeing 737-200 Aircraft," in *Vehicular Technology Conference, 2007. VTC2007-Spring. IEEE 65th*, April 2007.

5. L. Berlemann, G. Hiertz, B. Walke, and S. Mangold, "Radio resource sharing games: enabling QoS support in unlicensed bands," *Network, IEEE*, vol. 19, July-Aug. 2005.

6. Z. Han, Z. Ji, and K. Liu, "Power minimization for multi-cell OFDM networks using distributed non-cooperative game approach," in *Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE*, vol. 6, Nov.-3 Dec. 2004.

7. D. Niyato and E. Hossain, "Radio resource management games in wireless networks: an approach to bandwidth allocation and admission control for polling service in IEEE 802.16," *Wireless Communications, IEEE*, vol. 14, Feb. 2007.