In IEEE 802.11-based mesh networks, throughput distribution among nodes is not fair. The traffic originating from nodes that directly communicate with the gateway obtain higher throughput than all other traffic. Single-hop nodes fully utilize the gateway‟s resources, due to which all other nodes communicating with the same gateway will attain very little throughput. In this paper, we show that it is not just sufficient to rate limit the single-hop nodes in order to give transmission opportunities to all other nodes. If we just rate limit the single-hop nodes, it is not scalable to larger networks and it does not take load into consideration while allocating bandwidth. The present rate limiting mechanisms are also limited by single radio based nodes, our approach works well with multiple radio based wireless nodes also. We present our study with the help of two algorithms which remove the bias with the help of frequency based allocation and demand based allocation. Moreover, we use simulations to evaluate the proposed rate limiting mechanism.
Keywords |
| In recent years 802.11 based Mesh Networks have emerged as a successful architecture for providing cost-effective, rapidly deployable network access in a variety of different settings. A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks may consist of mesh clients, mesh routers and gateways [1]. A wireless mesh network is a special type of wireless ad-hoc network. The mesh routers are mobile, and they can be moved according to specific demands which are arising in the network [10]. Often the mesh routers have access to unlimited resources compared to other nodes in the network and thus can be expected to perform more resource intensive functions [2]. In 802.11, these distributed mesh nodes contend for access to the wireless medium. This contention for medium access produces a structural asymmetry in the network. Data from flows multiple hops have to contend for the medium at each intermediate hop, as compared to data from flows that originate in the vicinity of the gateway. Data at the nodes near the gateway is allotted more priority than data from other nodes. This means that current WMNs based on the IEEE 802.11 MAC and standard network-layer protocols cannot provide fairness to each node in the network.[4] In particular, it has been demonstrated that nodes close to the gateway can starve those that are more hops away[3]. A number of studies have described the uneven distribution of bandwidth among flows in multi-hop wireless networks [6, 7, 8]. |
| Although significant research has been done to address fairness issues within a single-hop, very little research has been done to address the problem in multi-hop wireless networks. It has been shown that network-layer fairness can be achieved by knowing the fair-share bandwidth each node can receive, and limiting the nodes to that rate [5].However, while this approach is possible, it requires that all mesh routers be modified to operate the relevant source-rate-limiting protocol.
In this paper we develop a new rate limiting mechanism which removes bias in wireless mesh networks. The rate limiting mechanism here takes the network load into consideration. It first finds out the topology of the network. It allots a frequency to all the nodes from a range of available frequencies based on our frequency based allocation scheme. |
| Secondly it then waits for data requests. It forwards the data requests according to the frequency allotted before. Now it measures the performance of the network. The network will show some bias. Some nodes have many data requests and some have less. Some nodes have requests for larger data. So according to the various requests, instead of forwarding the data to the nearest router as in the case of many algorithms, here a demand based allocation scheme is implemented. Finally the network performance is measured and through graphs proved to be better than the earlier biased allocation scheme. The rest of the paper is organized as follows. Next we see the network model and in the next section we review the related work. After that we propose our rate limiting mechanism. Next, we evaluate the performance of the proposed scheme through graphs. Finally we conclude the paper. |
NETWORK MODEL |
| For our paper we consider wireless networks that are non-mobile and multi-hop. The wireless routers forward traffic to and from gateway nodes. The physical topology of the mesh networks need not show any particular structure. The forwarding topology is structures as a set of trees whose root is gateway nodes. Thus, we consider networks with unconstrained physical topology, which embed a forwarding tree of degree N ≥ 1 and depth D ≥ 2 per gateway. In particular, we focus on a single-gateway mesh, in which a routing protocol establishes a set of forwarding links yielding a tree structure. Note that since the gateway capacity is of the order of few tens of Mbps, due to the 802.11maximum transmission rate, typical values of D are 2 to 3, and N ≤ 10 to ensure sufficient per-node resources. |
| For a particular tree, mesh nodes other than the gateway node can be classified into two sets: a set N of nodes that are directly connected to the gateway, and a set R which are the remaining nodes not directly connected. Fig. 1 depicts an example of data forwarding tree network topology. We consider wireless nodes equipped with multiple radio. Nodes in the two sets N and R compete for gateway access through a shared wireless interface. We can logically decompose the network into groups of wireless transceivers with the wireless router having the same frequency and all the remaining nodes separate frequency.
We assume that no peer-to-peer traffic is allowed within the mesh, i.e., all non-gateway nodes can open with the gateway or with remote Internet nodes only. Since we are only interested in those performance factors that are originating in the mesh network, we do not consider the effects of the connection path between the gateway and any other remote Internet node. Hence, for the sake of simplicity, we model all downstream flows as originating at the gateway, and all upstream flows as terminating at the gateway node.
However, in the rest of the paper we focus on the performance of upstream flows only. This assumption is motivated by the fact that previous work already showed that downstream traffic impairments do not arise in case of UDP, and TCP performs very similarly both upstream and downstream [2]. |
 |
| Figure 1. Network Model. |
RELATED WORK |
| GAP framework is based on two fundamental ideas. First, they have all nodes in the spatially advantaged node set agreeing that the combined gateway airtime utilization of their locally generated traffic, not including forwarded traffic, is limited to a particular threshold, rather than the entire gateway airtime. Consequently, spatially disadvantaged nodes‟ traffic can always use the residual gateway airtime for successful data transmissions (either from a two-hop node in M to a node in S, or a node in S forwarding a multi-hop packet to the gateway). Since all nodes in S know that their traffic‟s should not exceed a predefined threshold, nodes in S interpret the excess gateway airtime utilization as only due to transmissions of multi-hop traffic[9].
Hence, the only piece of information that nodes in S need is whether the gateway airtime utilization exceeded the threshold. This information might be encoded into a 1-bit message that is high when the traffic threshold is exceeded, and otherwise is low. This message might be sent from the gateway to all nodes in S, e.g., by encoding the bit into a currently unused subtype value in the Frame Control field of the 802.11 ACK, or by including a traffic indicator field in beacons regularly transmitted by the gateway, or also by allowing the gateway to transmit a new type of management frame, newly defined for traffic indication. Another way to obtain the same information on the gateway airtime utilization might consist in letting single-hop nodes estimate the gateway activity by overhearing gateway‟s ACKs.
This approach is in principle possible at single-hop nodes, but is particularly prone to estimation errors due to frame collisions and failures in decoding some ACKs, e.g., due to variations in the SNR, not all single-hop nodes might be able to decode gateway‟s ACKs transmitted at the highest modulation rate. Each single-hop node obtains a gateway utilization indicator IU, whose binary value is high if the bandwidth reserved for multihop traffic is in use. |
| They define the disadvantaged-flow Signaling Bandwidth, BD = γU, γ << 1, as a small portion of the system‟s resources that nodes in S collaboratively agree not to use for the transmission of their locally generated traffic to the gateway. Instead, this bandwidth will be used exclusively by the set of spatially disadvantaged flows. Any flow originating at a node in M will use this bandwidth to transmit data, thereby, expressing that its current demands would like more bandwidth, if possible, to the spatially advantaged node set S. Consequently, the distributed single-hop proxy controller will have all nodes in S collaboratively adapting their rates to realize the rate control objective.
The second part of the GAP framework is to prevent the spatially disadvantaged flows from misusing BD to get more than their minimum guaranteed rate if backlogged. In fact, if they would allow the single-hop nodes to unboundedly reduce their rates as long as BD is partially of fully utilized, backlogged multi-hop nodes could use BD to exclusively capture the system‟s resources, irrespective of the system‟s approximate priority behavior. Thus, they design GAP to not allow nodes in S to reduce their rates if their gateway utilization does not exceed a minimum guaranteed rate.
The Minimum Guaranteed Single-hop Rate, US*, is defined as the minimum bandwidth to be guaranteed for the node set S under saturation load conditions achieving a specific distribution of the gateway airtime. Adopting a minimum guaranteed rate for nodes in S, not only prevents disadvantaged flows from misusing BD, but also allows to tune the bandwidth effectively reserved for signaling according to the utilization of nodes in M. In fact, as nodes in M receive more bandwidth, less bandwidth is needed to indicate unserved demands. Thus, even though in a heavily utilized network the maximum unutilized bandwidth is BD , the actual unutilized bandwidth can be reduced as soon as more disadvantaged demands are served. The US* minimum guarantee is the tool that they use to allow the signaling bandwidth to be partially used by data flows originating at M. For instance, at saturated load conditions, all of the system‟s resources are fully utilized and both traffic types will receive their guaranteed rates—i.e., nodes in S will receive their minimum guaranteed rate US , while modes in M
will take all the rest—and no bandwidth is left for additional
signaling.
The above approach works well with single radio, but our
proposed approach works well with multiple radio. The entire
algorithm here is based on allocating bandwidth to the nodes 1
hop away and n hops away. Some of the bandwidth is reserved
for n hop nodes. The major drawback of this approach is that
they did not consider the load on the nodes. It may happen that
some nodes have very heavy load and some may have less load.
Our approach takes this into consideration and hence increases
the efficiency. |
PROPOSED ALGORITHM |
| Our proposed Rate limiting algorithm has multiple radio
interfaces. The major problem here is unequal distribution of
load, so we have developed a simple approach to solve this
problem. |
 |
| Fig. 2: Architecture of the System |
| Viewer is the front end of the system. User configures the
system as well as the view the output results using the viewer.
User will configure the number of nodes to be in simulation
and the time slot for BW allocation to the Gateway. Nodes
communicate with each other using wireless radio channels.
Node must use the radio channel allocated by the gateway and
the bandwidth allocated by the Gateway. Gateway allocated
radio channel to use for each node to avoid interference. It uses
the frequency allocator module to do this work. It also
processes the bandwidth request from the nodes and allocates
them using the Bandwidth allocator module. |
| The proposed algorithm is as follows: |
| A. Construct a Tree |
| B. Allocate frequency to all the nodes. |
| C. Allocate bandwidth to all the nodes. |
| D. Measure performance of the network |
| E. Reallocate bandwidth to the nodes. |
| Finally we measure the performance of the network again
and prove it has improved by using graphs to show the
improvement in performance of the network by using our
algorithm. The initial network is created as shown in fig. 3,
which has a router/gateway and nodes. All the nodes have to
connect to gateway to send data. |
A. Construct a Tree |
| We first start by constructing a tree before assigning
frequency and bandwidth. The router is taken as the root node.
As we have given the radio range of all the nodes, the router
finds the neighboring nodes. These are considered as leaf nodes. |
 |
| Fig.3: A network with routers and nodes |
| For each leaf node, find the neighboring nodes, make the leaf
node as parent node or intermediate node and add the
neighboring nodes as leaf nodes. Now again take one of the
parent or intermediate node and find its neighboring nodes
which are not reached yet. Continue above procedure for all the
nodes till no more nodes are left. |
 |
| Fig.4: Final Tree using the Algorithm |
| We now have a tree with router as root, some nodes as
intermediate nodes and other leaf nodes as shown in fig.4 |
B. Allocate frequency to all the nodes |
| The frequency allocation algorithm is used to allocate
frequencies to all the nodes. A range of 5 frequencies are used.
Wireless mesh networks can operate between 5.2 GHZ and
5.8GHZ. So we can select any 5 frequencies out of that. The entire tree has many levels, with router being at level 0. Further the nodes connected to the router are at level 1 and so on. All the level 1 nodes are allotted same frequency, at level 2 another set of frequencies and so on.
The use of this algorithm is that as different nodes have different frequencies there is no collision and all the nodes can receive and send data at the same time. |
| entire tree has many levels, with router being at level 0. Further the nodes connected to the router are at level 1 and so on. All the level 1 nodes are allotted same frequency, at level 2 another set of frequencies and so on.
The use of this algorithm is that as different nodes have different frequencies there is no collision and all the nodes can receive and send data at the same time. |
C. Allocate bandwidth to all the nodes |
| The next step after allocating frequency is allocating bandwidth. The total bandwidth is divided equally amongst all the nodes irrespective of their proximity to the router. Find out the number of nodes connected to the router at level 1, consider value as n. If the total bandwidth is B, then the bandwidth ‟BW‟ allotted to each of the „n‟ nodes at level 1 or the parent node or intermediate node will be: |
| BW = B/n |
| If the parent node has no child nodes then no further divisions are done for that node. If the node has leaf nodes, find the number of immediate child nodes and again divide the bandwidth equally amongst the immediate child nodes. Continue the same procedure till the algorithm reaches all the leaf nodes. |
 |
| Fig.5: Bandwidth allocation if the total bandwidth allocated is 1000 MB. |
| Fig.5 explains the bandwidth allocation algorithm. The entire bandwidth is not allocated only to the nodes which are directly connected to the gateway. All the nodes get some bandwidth from the entire bandwidth spectrum and the nodes as they have different frequencies can send data at the allotted bandwidth easily. |
D. Measure performance of the network |
| Finally, we measure the performance of the network. It can be seen that some of the leaf nodes are starved of the bandwidth, as the bandwidth allotted to them is less. We need to reallocate bandwidth to these leaf nodes, which is the next step. |
E. Reallocate bandwidth to the nodes |
| After evaluating performance log, we can see that even though the leaf nodes have some bandwidth allotted to them, it is less. So they can send data at a lower rate. Whereas the intermediate nodes or the parent nodes can send data at a higher rate. So the bandwidth allotted to them is again redistributed to the leaf nodes, and the leaf nodes now have a higher bandwidth. The reallocation algorithm keeps on allocating to leaf nodes according to their demands and decreases bandwidth allotted from nodes that have no data to send. |
EVALUATE PERFORMANCE |
| The experimental setup is done using Java as the programming language. JProwler is a discrete event simulator similar to Prowler but written in Java. The simulator supports pluggable radio models and MAC protocols and multiple application modules. JFreeChart is used for displaying the results in a graphical manner. The entire algorithm was coded and simulated using 50 sensor nodes and the results are as shown in fig.6. The results are for all the nodes irrespective of their proximity to the gateway, whether they are 1 hop or n hops away. As can be seen from the graph, all the nodes are requesting some bandwidth to send data and initially some bandwidth is allotted to them.
Over a time period it can be seen that the bandwidth allotted to them is more than or equal to the bandwidth requested by them. Even though not all the nodes get the requested bandwidth as soon as they demand, over a small time of seconds they get their demanded bandwidth. This graph proves our algorithm improves the performance of the network over a period of time and removes the bias towards the 1 hop nodes. |
 |
| Fig.6: Bandwidth requested and allocated graph. |
CONCLUSION |
| We present a rate control mechanism in which the set of nodes with spatial advantages, in terms of gateway access, locally share the gateway sources with other spatially disadvantaged nodes. We present a simple algorithm that removes this bias. Finally, we use simulations to show that our algorithm achieves comparable performance against this bias and allocates the bandwidth equally to all the nodes requesting their demands. We have achieved this using multiple radio nodes. Even though the results are proved for a 50 node network it can be proved even for a larger network. There is no added overhead for the nodes for this algorithm, only the router has some overhead, for allocating frequency and bandwidth. |
| [1] http://en.wikipedia.org/wiki/Wireless_mesh_network |
| [2] K.G.S. Venkatesan and V. Khanaa “Inclusion of Flow Management for Automatic and Dynamic Route Discovery System by ARS” in nternational Journal of Advanced Research in Computer Science and Software Engineering, Dec 2012 |
| [3] J. Jun and M. L. Sichitiu. “The nominal capacity of wireless mesh networks.” IEEE Wireless Communications, October 2003. |
| [4] K. Jamshaid, L. Li, and P. A. Ward. Gateway rate control of wireless mesh networks. In Proc. of WiMeshNets, August 2006. |
| [5] L. Li, S. Jakubczak, A. T. Lau, and P. A. Ward. “Achieving fairness in 802.11-based wireless mesh networks.” AdHoc Networks, May 2006. |
References |
- http://en.wikipedia.org/wiki/Wireless_mesh_network
- K.G.S. Venkatesan and V. Khanaa âÃâ¬ÃÅInclusion of Flow Management for Automatic and Dynamic Route Discovery System by ARSâÃâ¬Ã in nternational Journal of Advanced Research in Computer Science and Software Engineering, Dec 2012
- J. Jun and M. L. Sichitiu. âÃâ¬ÃÅThe nominal capacity of wireless mesh networks.âÃâ¬Ã IEEE Wireless Communications, October 2003.
- K. Jamshaid, L. Li, and P. A. Ward. Gateway rate control of wireless mesh networks. In Proc. of WiMeshNets, August 2006.
- L. Li, S. Jakubczak, A. T. Lau, and P. A. Ward. âÃâ¬ÃÅAchieving fairness in 802.11-based wireless mesh networks.âÃâ¬Ã AdHoc Networks, May 2006.
- M. Garetto, J. Shi, and E. Knightly, âÃâ¬ÃÅModeling media access in embedded two-flow topologies of multi-hop wireless networks,âÃâ¬Ã in Proceedingsof ACM MOBICOM, Cologne, Germany, Aug. 2005.
- M. Garetto, T. Salonidis, and E. Knightly, âÃâ¬ÃÅModeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks,âÃâ¬Ã ACM/IEEE Transactions on Networking, vol. 16, no. 4, Aug. 2008.
- L. Qiu, Y. Zhang, F. Wang, M. Han, and R. Mahajan, âÃâ¬ÃÅA general model of wireless interference,âÃâ¬Ã in Proceedings of ACM MOBICOM, Montreal, QC, Canada, 2007.
- V. Mancuso, O. Gurewitz, A. Khattab, and E. Knightly, âÃâ¬ÃÅElastic Rate Limiting for Spatially Biased Wireless Mesh Networks,âÃâ¬Ã in Proc. IEEE INFOCOM 2010, June 2010.
- http://p2pfoundation.net/Wireless_Mesh_Networks
|
Menu