Appraisement of IEEE 802.11s based Mesh Networks with Mean Backoff Algorithm

Published Online October 2015 in MECS DOI: 10.5815/ijmecs.2015.10.03

Wireless Mesh Networks comprise of mobile nodes form a dynamic network that organizes and configures itself. The mesh networks are formed using two types of nodes, mesh routers that perform routing functions in the network and mesh clients. These are enhanced ad hoc networks providing more robustness, reliable service coverage using multi-hop communication and easy network maintenance [1]. The working of these type of networks is mostly not centralized, which implies that different nodes take part for routing purposes for communication between the senders and the receivers [21]. These can be Infrastructure based, in which the traffic is redirected through the gateways, or Client mesh networks, which support peer to peer networking among the clients or a hybrid approach can be adopted for implementing them. Being advantageous over many other type of wireless networks, in terms of cost, reliability, coverage etc, they have been deployed in various applications [2]. The most common applications include broadband services, enterprise networking, community and enterprise networking etc [12].

The implementation of wireless mesh networks can be done using wireless technologies like 802.11, 802.15, 802.16 etc [2]. The IEEE 802.11 family of standards has specified many extensions for improvements in wireless connectivity. IEEE 802.11s is an extension to this standard which specifically corresponds to mesh networking that helps to improve coverage. There are three types of architectures specified by IEEE 802.11 that suggest the different ways of communication among the devices. An IBSS (Independent Basic Service Set) is composed of nodes that can directly communicate with one another as shown in Fig. 1. This type of configuration is formed randomly when the devices are in range and ready for communication with one another [3].

Fig.1. IBSS

In a BSS (Basic Service Set), the stations don’t communicate directly but through Access Points as shown in Fig. 2. The access points distribute the data and act as gateways in the network [3].

The ESS (Extended Service Set) is a collection of numerous BSSs connected with one another through a central system often described as Distributed system (DS) as depicted in Fig. 3. A distributed system is responsible for transporting MAC service data units among various communicating entities in the network. An ESS acts as a single integrated system like BSS. Portals are the logical points specified in this type of configuration that allow MSDUs from other type of LANs to be accessible into the system.

Fig.2. BSS

The differences between IBSS and ESS can be therefore summed up as given in table 1 [4]:

Table 1. Difference between IBSS and ESS

S. No.	ESS	IBSS
1	Multiple      BSSs      are interconnected   through   a Distributed set (DS).	There is a single BSS in this configuration.
2.	There are portals that allow the MSDUs from other type of LANs to enter into the DS.	There is no provision of portals or integrated wired LAN.
3.	It has provisions for client support and internet access.	It cannot provide client support or internet access.

Fig.3. ESS

IEEE 802.11s standard is based on an architecture that contains both the features of ESS and IBSS. The BSSs in DS are not connected by wired LANs but in a wireless fashion and use multi-hop communication. The portals are also required for interaction between wired and wireless networks. This standard provides support for both single channel and multi-channel operations. It is also compatible with the legacy nodes and conventional networks. Further improvements have been made with regard to MAC layer congestion control, power management, service area coverage etc [4].The overall architecture of IEEE 802.11s mesh networks can be summed up as in Fig.4.

The routers can be provided with multiple interfaces to increase the capability of these networks. It helps to utilize the bandwidth of the network more efficiently. Different standards support different number of channels and multiple assignment techniques have been developed which can be utilized for varying requirements of the networks. The use of multiple channels has also been proved effective for the reduction of interference and has been considered as a better approach for carrying out multiple transmissions [17].

The channel assignment techniques have been categorized as static, dynamic and hybrid techniques. In static techniques, there is a fixed channel specified for each interface. This is not a flexible approach as it does not consider the traffic and load conditions according to which the channels could be switched during communications. For dynamic channel assignment, the interfaces can switch among different channels for communication depending on the different conditions of the network. While the Hybrid approach has the characteristics of both static and dynamic approach. In this, some of the interfaces can be assigned fixed channels while others can switch among different available channels based on the underlying scheme [18].

The routing protocol specially provided for IEEE 802.11s standards is Hybrid Wireless Mesh Protocol (HWMP), which incorporates both reactive and proactive features. The underlying mechanism of this protocol is based on standard AODV protocol with some amendments. The proactive feature is used when the network behaves statically while reactive for dynamic behavior of the network. The AODV protocol employs IP addresses for its working while HWMP uses MAC addresses for routing purposes [19].

Fig.4. IEEE 802.11s Networks

The rest of the paper contains the following sections. Part 2 contains the problem definition derived from the current work. Part 3 contains the related work for the proposed work. The actual proposed algorithm is contained in Part 4 and finally The part 6 discusses the experimental evaluation of the proposed work.

• II.    Problem Definition

The nodes communicating within transmission range work in shared wireless medium [5]. All the nodes compete for the access of medium in order to transmit data to their requisite destinations in the network. The concurrent access of the shared medium by multiple nodes leads to collisions in the network. It affects the performance of network by degrading its throughput, increasing delays and congestion in the network [7]. MAC (Medium Access Control) protocol is responsible for managing the concurrent access to the medium by multiple nodes. A Distributed Coordinated Function (DCF) is specified as a MAC technique for efficient shared medium access in IEEE 802.11 standard. It works on the concepts of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). In this mechanism, nodes can access the medium after waiting for specific time interval that is determined by back-off period. The concept of back-off waiting time intervals has been specified in MAC as Binary Exponential Backoff algorithm [6].

The IEEE 802.11 BEB algorithm increases the waiting time period of a station in case of busy medium, while the waiting period of a station is set to minimum for a successful transmission. It has also been termed as memory-less algorithm since it does not consider the network conditions while setting the waiting period for a station [5]. This does not provide a collision free access to the medium since it does not ensure fairness among the stations [6]. The sudden reset to minimum value of waiting period may further be responsible for more collisions in the near future because the same station would again be eligible for medium access very soon

• [5] .Various researchers have devised different solutions for overcoming this flaw of BEB algorithm.

• III.    Related Work

Federico Cali et al have presented a dynamic protocol for IEEE 802.11 in which an enhancement was made to the conventional p-persistent protocol. In this the value of probability p was not taken as a constant value but which dynamically changed with the change in network configuration and load in the network. Secondly the backoff interval was also made dependent on the channel status. It would decrease only when the channel was found to be idle. All these computations were made by taking into account the no of active stations in the network at that particular time. Hidden node problem was not considered in this research work [8].

Maali Albalt et al had proposed an adaptive back-off algorithm which maintained a track of previous successful transmissions in the network. Two new factors were introduced in this history based approach, a multiplicative factor to update the value of contention window and a channel state to store the historical state of the channel. There was an overhead in the practical implementation of this algorithm since extra space was required to store the history of channel states [5].

Mohammed Al-Hubaishi et al had presented an enhancement to the actual Binary Exponential Back-off algorithm. An effort was made to enhance the fair access of the medium by the contending nodes. The size of the contention window was adjusted in accordance with the no. of successful frames sent. A formula was proposed to quantify the fairness factor based on the no. of same priority flows and the throughput of the corresponding flow [6].

Tahiry Razafindralambo et al had designed a simple back-off algorithm to improve the efficiency and fairness in accessing the shared medium. This algorithm takes into account the local information and works on two contention window sizes. The first contention window is same as the actual algorithm while the second refers to the one that is taken into account for the next time interval based on some computations [9].

Yi-Hua Zhu et al had developed a mathematical model packet that determined the probability of collisions, backoff distributions, no. of backoffs of a node, average of contention window size and the packet delay. Based on these computations, an favorable value of contention window was derived in order to maximize channel utilization [10].

Yingxia Sun et al proposed an improved algorithm based on RTS/CTS mechanism. A backoff value was selected different from other stations in accordance with the previous packet results and current backoff value of other stations in the network [11].

• J. A. Moura et al had given a solution by decreasing the size of contention window exponentially in case of successful transmission. But this solution offered a fixed factor for setting the contention window size without considering the network status in terms of congestion, load etc. [13].

Sartthong J et al had proposed a Contending stations Backoff Algorithm based on mathematical optimization function theory. The new algorithm was realized and its performance was set against existing BEB algorithm, Double Increment and Double Decrement Backoff algorithm using mathematical computations which in result provided stable performance [14].

Chun Shi et al had presented a backoff algorithm using the concept of linear contention window based on the node numbers. The contention window was selected as a linear function of no. of active nodes. For a larger no. of nodes it was derived the collision probability was independent of contention window and the no. of nodes [15].

• IV.    Proposed Work

The proposed work aims to control the shared access of medium by multiple nodes in the network. It provides for a methodology so as to prioritize the nodes for accessing the medium based on their contention window size and backoff time. Based on this algorithm, the communicating nodes are made to wait for specific time intervals before they can actually transmit data on the network. The waiting period for each node is different in the network which reduces the chances of simultaneous access of medium by multiple nodes to a greater extent. Therefore, the contention is reduced since each node optimistically would access the medium at a different time period. Moreover, collisions are reduced, thereby reducing the no. of retransmissions and packet drop outs. This also makes the network performance efficient in terms of congestion. The mechanism of Binary Exponential Algorithm and the proposed Mean Backoff Algorithm has been discussed in the subsections below.

• A.    BEB Algorithm

MAC layer requirements have been provided by IEEE 802.11 standard for shared medium control which uses the concepts of DCF (Distributed Coordinated Function)

and BEB algorithm [5]. The BEB algorithm specifies rules to be followed by the stations in while communicating in the network.

When a station requires to forward data in the network, it firstly checks whether there is any ongoing transmission in the network. If there is no transmission going on by any station in the network, the medium is found to be idle. The station that needs to transmit keeps on sensing the medium for a certain amount of time interval same as DCF Interframe space (DIFS) and latest value of backoff timer [5]. DIFS can be computed using the formula given below in (1):

DIFS = SIFS + ( 2* SlotTime ) (1)

In the above formula, SIFS is the Short Interframe Space which is equal to the time interval between the frame sent and its acknowledgement is received. Backoff time, as given in (2) is arbitrarily selected in the bounds of current contention window of the station [6].

Backoff Time = Random [ 0, CW ] * SlotTime (2)

If the station is found busy during this interval, it has to wait for backoff time interval. This waiting procedure continues till the station finds it to be idle for transmission [5].

If the medium remains idle for DIFS interval, actual transmission procedure can be started. The DCF mechanism has been extended to solve the hidden node problem using extra control packets to reduce collisions [4].RTS, Request to send and CTS, Clear to send, are the control packets used in the communication process for this purpose. [5]. The station sends RTS packet before sending the actual data and then waits for an acknowledgement in the form of CTS packets. After receiving the CTS packets, actual data can be transmitted.

After transmission of data, the station waits for an acknowledgement. In case of no acknowledgement, it assumed that data frame is lost and then re-transmission procedure is scheduled. The retransmission limit for long frames is 4 while for short frames is 7 [5]. Also, the contention window size in case of transmission failure is reset as in (3) [6]:

CW new = min [ 2* CW ^, C ^] (3)

If an acknowledgement is received, it marks the successful transmission of data and the size of contention window is reset as in (4) [6]:

^CW = CW min ⁽⁴⁾

• B.    Mean Backoff Algorithm

In BEB algorithm, abrupt reset of contention window size to least value in case of acknowledged transmission does not cut down the collisions. In fact the same station gets access to medium again after a short period of time which adds to the no. of contending stations after a short interval. This also creates unfairness among the stations contending for the medium access for very long time period. This increases the chances of collision and congestion in the network. So the proposed solution is Mean Backoff algorithm that resets the contention window to a convenient value so that better network performance with reduced no. of collisions is achieved. The Mean Backoff algorithm resets the contention window to the mean of its maximum size and minimum size value on successful transmission by a station as follows.

CW mean = ( C^ min + CW max ) /2   (5)

The mean size of contention window is neither too large as the maximum value that it can have nor as small as the minimum specified value. It acts as an convenient value which when set the station waits for an appropriate time for getting the access to shared medium again.

The Mean Backoff algorithm is summed up as in Fig 5.

Fig.5. Mean Backoff Algorithm

• V.    Experimental Evaluation

A dynamic wireless mesh network has been considered based on IEEE 802.11s standard which is specially incorporated for mesh networking. The simulation have been carried out using NS2 simulator with the experimental scenario composed of 44 nodes spread in

1000x1000 area as shown in Fig. 6 below. This figure represents the initial position of 36 nodes and remaining 8 nodes join the network randomly after short time period as new stations joining the already established network. Random way point is the mobility model which determines the node movements. In this type of model, the nodes move among uniformly distributed waypoints one after another. The velocities of the moving nodes are randomly distributed within some specified range [20]. After some time interval the nodes stop moving and come to a stationary state [16]. When the simulation starts, the nodes are randomly distributed to different positions within the specified area. The simulation parameters have been summed up in Table 2.

Table 2. Simulation Parameters

Parameter	Value
Number of nodes	44
Network Interface Type	Wireless Phy/IEEE 802.11
Simulation Time	50 sec
Area (m*m)	1000 *1000
Mobility Model	Random Way Point
Routing Protocol	HWMP
Packet Size	1024 bits

Fig.6. Experimental Scenario

The routing protocol that supports IEEE 802.11s mesh specific standard is Hybrid Wireless Mesh Protocol (HWMP). This protocol consists of four main elements: Route Announcement, Path Request, Path Reply and Path Error. With the help of these information elements, the routes are created and managed in the mesh network [4]. Network throughput and delay have been evaluated and a comparison has been made between the actual algorithm and proposed algorithm considering both parameters.

• A.    Throughput

Throughput refers to the amount of data transferred per unit time. More the throughput of the network better is its performance. Fig. 7 displays the throughput of the network for both actual algorithm and proposed algorithm. The throughput in case of simple BEB algorithm is significantly lesser as compared to the proposed Mean Backoff algorithm. Since the BEB algorithm resets the contention window size abruptly for an acknowledged transmission, it cannot be held accountable for considerable reduction in contention and congestion in the network. The throughput thus gets reduced due to collisions and retransmissions. But in case of proposed algorithm, an effort that has been made to improve the previous algorithm is clearly indicated by the result graph. It is because after a successful communication the node still waits for a considerable amount of time before taking the charge of shared medium again. It ensures that many other nodes can have their chance of accessing the medium before it again gets to access the medium. The maximum throughput of the network achieved in case of BEB algorithm as depicted in the result graph is about 130 kilobits per second while it has increased to 225 kilobits per second in case of proposed Mean Backoff algorithm.

Fig.7. Throughput

• B.    Delay

It denotes the time interval that takes it to transfer data from source to destination. There must be less delay in the network so that the data gets delivered fast, thereby reducing the chances of packet dropouts and retransmissions. Since the BEB algorithm provides the last successful sender with the chance of access of medium very soon in the near future the no. of contenders increase again after a short period of time. This increases the congestion and collisions, due to which the medium doesn’t get freely available to any of the stations. Even the data that is being transmitted gets affected because of the inability of the medium to transmit it within the required time constraints. So the acknowledgements get delayed and the number of retransmissions increases making the medium busier.

This adds to the delays in data transmission from sender to receiver. But the proposed Mean Backoff algorithm sets the contention window of the last successful transmitter effectively neither to a very low value as minimum nor to a higher value as maximum. Each station gets it access to medium effectively after waiting for a considerable amount of time period, during which the transmitted data can easily be transferred to its requisite destination. There are less chances of timeout and retransmissions, thereby reducing the delays. Fig. 8 shows delay comparison for both actual BEB algorithm and proposed BEB algorithm. It clearly depicts that delay has been reduced significantly by the use of proposed algorithm as compared to previous one.

Fig. 8 Delay

• VI.    Conclusion

Wireless mesh networks provide effective networking solutions owing to better characterstics than adhoc networks. These networks have been deployed practically in many projects for providing cost economic services. Therefore, it becomes necessary for these networks to provide best services so that the quality of communication is not compromised at any cost. The proposed work presented in this paper is an effort to provide a better performance considering the collisions among the competing stations in wireless mesh networks. A Mean Backoff algorithm has been developed in order to boost up the performance of network in terms of throughput and delay. This algorithm aims to refine the BEB algorithm favored by IEEE 802.11 standard. The changes were introduced in the size of contention window for successful transmissions. This new algorithm has been implemented on IEEE 802.11s mesh networks with HWMP as the routing protocol. The simulation results have shown a significant increase in network throughput and decrease in delays caused in the network.

Acknowledgment

This research work was supported by Dr. Parminder Singh, Assistant Professor, Department of Information Technology, Chandigarh Engineering College, Landran (Mohali), Punjab, India.