Interference Estimation and Automated Generation of Spatial Re-use Map for Wireless Mesh Networks

Inter-link interference is one of the major factors that affects the performance of Wireless Mesh Networks. An {\em interference map} indicates possible spatial reuse, which can help improve the throughput of a TDMA-based network by reusing the same time slot for different non-interfering links. It is also a key input in both channel assignment and routing algorithms for the TDMA-based networks.

In this work, we have first performed various controlled measurements to study interference in realistic outdoor settings and determined the relation between the RSSI and interference. Based on the observations, we have developed a three way classification strategy to classify link-pairs according to the interference values. The classification strategy also takes care of the inherent RSSI variability observed in outdoor wireless links. It uses the SIR values approximated from the individual RSSI measurements, requiring only O(N) broadcast measurements for a network with N nodes.

We have also developed an automated mechanism, which performs these measurements periodically and generates an interference map. The time period of the measurements and the duration of each measurement is determined by time-series analysis of 24/48 hour long duration data. The work done is specific to outdoor TDMA-based networks.

[attachment=15211]
Introduction
1.1 FRACTEL
A Wireless mesh network(WMN) is a co-operative set of wireless nodes, organized to form a
communication network. These nodes together form a mesh topology, where any node can
reach any other node in the network either directly or through some other nodes that have
additional forwarding capabilities and act as mesh routers. One or more nodes in the mesh
network may act as a gateway to the backbone network such as Internet, cellular network
or some other communication network. Any node that wishes to communicate outside the
network, sends its packets to the gateway either directly or with the help of mesh routers
forming a multi-hop wireless network. WMNs are termed to be 'exible' and 'scalable' networks.
Flexible because the links need not be planned and scalable because of the fact that
its size may vary from small indoor settings to large community networks with links ranging
upto to tens and hundreds of kilometers [1, 2] and hundreds of nodes.
802.11 based wireless mesh networks has recently emerged as cost-eective solution for
providing last hop Internet access. Past few years have seen many deployments [1, 4, 2] of outdoor
and community mesh networks. These networks dier from the traditional wireless LANs
in many ways and pose many research problems relating to the routing, channel assignment
and MAC schemes that needs to be specically designed for these kinds of settings.
FRACTEL (wi-Fi based Rural ACcess TELephony) [7] is an 802.11 based rural wireless
mesh network, for providing cost-eective Internet connectivity to the Rural regions. It uses
CHAPTER 1. INTRODUCTION 2
Figure 1.1: FRACTEL example [14]
o-the-shelf 802.11 hardware and a right combination of external antennas and tall towers
to form a long distance wireless communication network. Because of the cheap availability
of 802.11 hardware and relatively low establishment and maintenance costs of wireless links,
these networks are ecient communication alternatives to their wired equivalent, especially
when the user base is quite sparse like in rural settings.
FRACTEL network is a combination of long distance links and local access links. Long
distance links connect wired back bone network to the central node in each village called local
gateway. They also connect one local gateway to the other local gateways forming a multi-hop
long distance network (LDN). These links are typically of tens of kilometers in length. Local
gateway is then connected to several points (like schools and hospitals) in each village using
what we call as local access links. These local access links are typically less than 500 meters.
Each node in the village is connected to the local gateway by single-hop or through multiple
hops of other village nodes. These nodes form a Local Access Network (LACN). Figure 1.1
depicts LDN and LACN in an example deployment setting in Ashwini network [14].
FRACTEL aims at providing voice and video capabilities for services like remote education
and tele-medicine. It proposes the use of a TDMA based MAC designed specically for
providing these kind of services on long distance Wi-Fi links.
CHAPTER 1. INTRODUCTION 3
1.2 Motivation and Problem Statement
Wireless Mesh Networks are often unplanned and have dynamically changing links. The performance
of these networks depends on eective management of these links. Inter-link interference
is one of the key factors that aect the performance of wireless mesh networks. Many
intelligent channel allocation and routing mechanisms try to work around the interference
by operating the interfering links on separate orthogonal channels, and routing packets using
separate non-interfering routes. The TDMA scheduling also tries to improve the throughput
by spatially reusing the time slots by scheduling the non-interfering links on the same cycle.
Thus, an interference map or spatial re-use map gives information relating to the inter-link
interference, and the possibility of spatial reuse in a wireless mesh network.
There has been lot of work done to develop these intelligent routing and channel assignment
schemes. Most of these schemes either assume that the required interference information is
already present or use some pessimistic and inaccurate RF models to estimate the interference
map. These RF-models like distance based path loss models and packet loss models which try
to estimate the interference based on the RF - characteristics of a page link are highly incapable
of modeling the real world scenarios and cannot be used for generating the interference map.
However, measuring interference is also non-trivial. An N-node network will have O(N2)
links and would require up to O(N4) measurements to measure pair-wise interference. Owing
to the fact that the wireless links exhibit some degree of RSSI variability, the interference
measurement may not be a one time issue and adds to the complexity. Periodic repetition of
the interference measurement also allows dynamic changes in the network and takes care of
the inherent RSSI variability.
The main aim of this work is