A Cross-layer MAC Mechanism to Solve Performance Anomaly in MANET - SEMINAR

 

1. Introduction

 

           

            Mobile networking is one of the most important technologies supporting pervasive computing. During the last decade, advances in both hardware and software techniques have resulted in mobile hosts and wireless networking common and miscellaneous. Generally there are two distinct approaches for enabling wireless mobile units to communicate with each other: 

 

1) Infrastructured: Wireless mobile networks have traditionally been based on the cellular concept and relied on good infrastructure support, in which mobile devices communicate with access points like base stations connected to the fixed network infrastructure. Typical examples of this kind of wireless networks are GSM, UMTS, WLL, WLAN, etc.

 

2) Infrastructureless: As to infrastructureless approach, the mobile wireless network is commonly known as a mobile ad hoc network (MANET). A MANET is a collection of wireless nodes that can dynamically form a network to exchange information without using any pre-existing fixed network infrastructure. This is a very important part of communication technology that supports truly pervasive computing, because in many contexts information exchange between mobile units cannot rely on any fixed network infrastructure, but on rapid configuration of a wireless connections on-the-fly. Wireless ad hoc networks themselves are an independent, wide area of research and applications.

 

1.1 MANET Concept

            A mobile ad hoc network is a collection of wireless nodes that can dynamically be set up anywhere and anytime without using any pre-existing network infrastructure. It is an autonomous system in which mobile hosts connected by wireless links are free to move randomly and often act as routers at the same time. The traffic types in ad hoc networks are quite different from those in an infrastructured wireless network , including:

1) Peer-to-Peer: Communication between two nodes which are within one hop. Network traffic (Bps) is usually consistent.

 

2) Remote-to-Remote: Communication between two nodes beyond a single hop but which maintain a stable route between them. This may be the result of several nodes staying within communication range of each other in a single area or possibly moving as a group. The traffic is similar to standard network traffic.

 

3) Dynamic Traffic. This occurs when nodes are dynamic and moving around. Routes must be reconstructed. This results in a poor connectivity and network activity in short bursts.

 

1.2 MANET Features:

1) Autonomous terminal: In MANET, each mobile terminal is an autonomous node, which may function as both a host and a router. In other words, besides the basic processing ability as a host, the mobile nodes can also perform switching functions as a router. So usually endpoints and switches are indistinguishable in MANET.

2) Distributed operation: Since there is no background network for the central control of the network operations, the control and management of the network is distributed among the terminals. The nodes involved in a MANET should collaborate amongst themselves and each node acts as a relay as needed, to implement functions e.g. security and routing.

3) Multihop routing: Basic types of ad hoc routing algorithms can be single-hop and multihop, based on different link layer attributes and routing protocols. Single-hop MANET is simpler than multihop in terms of structure and implementation, with the cost of lesser functionality and applicability. When delivering data packets from a source to its destination out of the direct wireless transmission range, the packets should be forwarded via one or more intermediate nodes.

4) Dynamic network topology: Since the nodes are mobile, the network topology may change rapidly and unpredictably and the connectivity among the terminals may vary with time. MANET should adapt to the traffic and propagation conditions as well as the mobility patterns of the mobile network nodes. The mobile nodes in the network dynamically establish routing among themselves as they move about, forming their own network on the fly. Moreover,a user in the MANET may not only operate within the ad hoc network, but may require access to a public fixed network.

 

1.3. MANET Challenges

1) Routing. Since the topology of the network is constantly changing, the issue of routing packets between any pair of nodes becomes a challenging task. Multicast routing is another challenge because the multicast tree is no longer static due to the random movement of nodes within the network. Routes between nodes may potentially contain multiple hops, which is more complex than the single hop communication.

2) Security and Reliability: wireless connection, an ad hoc network has its particular security problems due to the feature of distributed operation requires different schemes of authentication and key management. Further, wireless link characteristics introduce also reliability problems, because of the limited wireless transmission range, the broadcast nature of the wireless medium mobility-induced packet losses and data transmission errors.

3) Quality of Service (QoS): Providing different quality of service levels in a constantly changing environment will be a challenge. The inherent stochastic feature of communications quality in a MANET makes it difficult to offer fixed guarantees on the services offered to a device. An adaptive QoS must be implemented over the traditional resource reservation to support the multimedia services.

4) Internetworking. In addition to the communication within an ad hoc network, internetworking between MANET and fixed networks (mainly IP based) is often expected in many cases. The coexistence of routing protocols in such a mobile device is a challenge for the harmonious mobility management.

 

1.4 MANET Applications

1) Military battlefield: Military equipment now routinely contains some sort of computer equipment. Ad hoc networking would allow the military to take advantage of commonplace network technology to maintain an information network between the soldiers, vehicles, and military information head quarters. The basic techniques of ad hoc network came from this field.

2) Commercial sector. Ad hoc can be used in emergency/rescue operations for disaster relief efforts, e.g. in fire, flood, or earthquake. Emergency rescue operations must take place where non-existing or damaged communications infrastructure and rapid deployment of a communication network is needed. Information is relayed from one rescue team member to another over a small handheld. Other commercial scenarios include e.g. ship-to-ship ad hoc mobile communication, law enforcement.

3) Local level. Ad hoc networks can autonomously link an instant and temporary multimedia network using notebook computers or palmtop computers to spread and share information among participants at a e.g. conference or classroom. Another appropriate local level application might be in home networks where devices can communicate directly to exchange information. Similarly in other civilian environments like taxicab, sports stadium, boat and small aircraft, mobile ad hoc communications will have many applications.

4) Personal Area Network (PAN). Short-range MANET can simplify the intercommunication between various mobile devices (such as a PDA, a laptop, and a cellular phone). Such an ad hoc network can also extend the access to the Internet or other networks by mechanisms e.g. Wireless LAN (WLAN), GPRS, and UMTS. The PAN is potentially a promising application field of MANET.

 

 

 

2. Literature survey

 

“A Rate Adaptive MAC Protocol for Multi hop Wireless Networks”

G.Holland , N.Vaidya

            RBAR (Receiver Based Auto Rate), as one of the most popular multi-rate MAC protocols, was proposed by Gaven. The novelty of RBAR is that its rate adaptation mechanism is in the receiver instead of the sender. Compared with its poor channel quality estimation and the dependence on RTS/CTS packet, more problems of RBAR came from performance anomaly.

 

Distributed Coordination Function (DCF)

            The Distributed Coordination Function (DCF) in 802.11 is an implementation of the RTS/CTS protocol, and is il- lustrated in Figure 4, which is a time-line portraying the sequence of events that occur for a single packet transfer. Here, the source Src has a data packet to transmit to the destination Dst with a duration of length L. Node A is in range of Src but not Dst, and node B is in range of Dst but not Src. The protocol proceeds as follows. When Src has a packet to send, it calculates the length of time it will take to transmit the data packet at the current data rate, and then adds to that the transmission time of the CTS and ACK packets, which forms the duration of the reservation (DRTS). The Src then transmits DRTS in the RTS to Dst, using one of the rates in the basic rate set. The basic rate set is the set of rates that all nodes are required to support, which ensures that all nodes that are in transmission range are able to receive and demodulate the RTS/CTS packets.

 

            Since node A is in range of Src, it overhears the RTS and summarily defers its own transmissions for the duration of the reservation in the RTS (DRTS), starting from the mo- ment that it received the RTS (T1). If Dst is capable of receiving the data packet, it responds by transmitting a CTS packet back to Src containing the time remaining in the reservation (DCTS), which it calculates by subtracting the transmission time of the CTS from DRTS. Node B, overhearing the RTS, learns of the requested reservation and, like A, defers for length DCTS.

            At this point, transmission of the data packet and subsequent ACK can now proceed without interference from A or B. However, in the off-chance that A did not receive the RTS, due to, for example, an RTS collision caused by another node, the data packet also carries the time remaining in the reservation Ddata to ensure that A defers during the transmission of the ACK.


Figure 4: Timeline showing the RTS/CTS protocol in the IEEE 802.11 Distributed Coordination Function (DCF) for transmitting a data packet.

 

Network Allocation Vector (NAV)

            Since a node may overhear many different, potentially overlapping, reservation requests, it needs a means by which it can efficiently manage them. This is the purpose for the maintenance of a structure called the Network Allocation Vector (NAV). The NAV is a data structure that stores the aggregate duration of time that the medium is presumed to be “busy" based on the reservation requests that have been received. Maintenance of the NAV is straightforward, since reservations are not allowed to change. Thus, nodes that overhear a reservation request are free to update their NAVs without regard to any further communication, such as if the reservation was actually granted by the receiver.

 

 

 

 

THE RECEIVER-BASED AUTO RATE (RBAR) PROTOCOL

            The core idea of RBAR is to allow the receiver to select the appropriate rate for the data packet during the RTS/CTS packet exchange. Advantages to this approach include:

  • Both channel quality estimation and rate selection mechanisms are now on the receiver. This allows the channel quality estimation mechanism to directly access all of the information made available to it by the receiving hardware (such as the number of multipath components, the symbol error rate, the received signal strength, etc.), for more accurate rate selection.
  • Since the rate selection is done during the RTS/CTS exchange, the channel quality estimates are nearer to the actual transmission time of the data packet than in existing sender-based approaches, such as the protocol in which attempts to predict channel conditions based on conditions experienced during previous data packet transmissions.
  • It can be implemented into IEEE 802.11 with minor changes, as we will show in a later section.

         In the remainder of this section, we present the RBAR protocol in more detail. Note that although our discussion is in the context of the RTS/CTS protocol in the DCF of the 802.11 standard, the concepts are equally applicable to other RTS/CTS based protocols such as SRMA, MACA, MACAW, and FAMA.

 

            In RBAR, instead of carrying the duration of the reservation, the packets carry the modulation rate and size of the data packet. This modification serves the dual purpose of providing a mechanism by which the receiver can communicate the chosen rate to the sender, while still providing neighboring nodes with enough information to calculate the duration of the requested reservation. The protocol is as follows

      

            The sender Src chooses a data rate based on some heuristic (such as the most recent rate that was successful for transmission to the destination Dst), and then stores the rate and the size of the data packet into the RTS. Node A, overhearing the RTS, calculates the duration of the requested reservation DRTS using the rate and packet size carried in the RTS.

“Performance Anomaly of 802.11b”

M.Heusse,Franck Rousseau,Gilles Berger-Sabbatel and A.Duda

 

            The IEEE 802.11b standard defines two access methods: the Distributed Coordination Function (DCF) that uses CSMA/CA to allow for contended access to the wireless media and the Point Coordination Function (PCF) providing uncontended access via arbitration by a Point Coordinator, which resides in the Access Point. The DCF method provides a best effort type of service whereas the PCF guarantees a time-bounded service. The DCF access method is based on the CSMA/CA principle, in which a host wishing to transmit senses the channel, waits for a period of time (DIFS – Distributed Inter Frame Space) and then transmits if the medium is still free. If the packet is correctly received, the receiving host sends an ACK frame after another fixed period of time (SIFS – Short Inter Frame Space). If this ACK frame is not received by the sending host, a collision is assumed to have occurred. The sending host attempts to send the packet again when the channel is free for a DIFS period augmented of a random amount of time.

 

            Let first consider that a single host in a 802.11b cell transmits a single data frame. If we neglect propagation times, the overall transmission time is composed of the transmission time and a constant overhead:

        T = ttr + tov                   (1)

Where the constant overhead

        tov = DIFS + tpr + SIFS + tpr + tack

            Is composed of the PLCP (Physical Layer Convergence Protocol) preamble and header transmission time tpr, SIFS = 10 μs, tack is the MAC acknowledgment transmission time (10 μs if the selected rate is 11 Mb/s, as the ACK length is 112 bits), and DIFS = 50 μs. ttr is the frame transmission time . tpr varies according to the bit rate used by the host. When it transmits at 1 Mb/s, the long PLCP header is used and tpr = 192 μs. If it uses 2, 5.5 or 11 Mb/s, then tpr = 96 μs (short PLCP header). For bit rates greater than 1Mb/s and the frame size of 1500 bytes of data (MPDU of total 1534 bytes), proportion p of the useful throughput measured above the MAC layer will be:

            

           So, a single host sending long frames over an 11 Mb/s radio channel will have a maximum useful throughput of 7.74 Mb/s. If there are multiple hosts attempting to transmit, the channel may be sensed busy and hosts enter a collision avoidance phase: a host executes the exponential backoff algorithm it waits for a random interval distributed uniformly between [0, CW] × SLOT. The congestion window CW varies between CWmin = 31 and CWmax = 1023, the value of SLOT is 20 μs (these parameters are for 802.11b). The host that chooses the smallest interval starts transmitting and the others hold counting down until the transmission is over. Each time a host happens to collide, it doubles CW up to CWmax. In the case of a single host that tries to transmit a sustained traffic (the host has always a packet to send), the carrier sense applies also to the host’s own transmissions, so that it inserts a random interval between each transmission.

 

“Performance analysis of IEEE 802.11 Multi rate WLANs: Time Based Fairness Vs Throughput Based Fairness”

A.V.Babu and Lillykutty Jacob

 

            In time-based fairness, each node receives an equal share of the wireless channel occupancy time. It is demonstrated in that the time-based fairness can achieve higher aggregate throughput. Several solutions are proposed to solve performance

 

Performance Analysis under Multi-rate Scenario

            To overcome unfairness of conventional CSMAICA in a multi rate scenario, we use priority control according to the data rate of the stations. By selecting appropriate priority depending on the data rate and giving more transmission opportunity for high data rate station, the system capacity can be improved. Consider a heterogeneous WLAN of nodes with two different rates, lower rate corresponding to slow station and higher rate corresponding to fast station, and assume that each station is in saturation, i.e., has always a frame ready for transmission. Let there be ns slow stations and nf fast stations and let n= n, + nf.

            The maximum back off stage, m, and the retry limit m, are assumed to be equal for the two priority classes. Let Wij represents the contention window (CW) size in the j-th retry/retransmission for rate-i station, je {O,l,...m}. For rate-i station, contention window size in the j-th  retry/retransmission, Wij, and the retry limit, m, are related as follows:

            

            Let si(t) and bi(t) be the stochastic processes representing the back off stage and the back off time counter value, respectively, for rate-i traffic flow. We assume that the frame collision process is Bernoulli which allows us to describe the state of each station, slow or fast, with two dimensional DTMC {s1(t), bj(t)} . The state transition occurs at the beginning of the next slot time, where a transition can happen after a transmission or an empty slot time. Let pc,i and pr,i , respectively, represent the frame collision probability and frame transmission probability for rate-i station. From the DTMC the frame transmission probability can be derived as follows. Let qi(j,k) = lim {P(si(t) = j,bi(t) = k)}, j E (O,m), k E (O,Wi j -1) be the stationary distribution for the chain. In steady state the following relations can be obtained:

 

            

Solutions for Performance Anomaly

            It has been proven that if there are two bit rates under the same channel conditions, the saturation throughput of any station will be equal to the saturation throughput of station with the lower data rate. To solve the throughput degradation occurring in a multi rate environment, we propose two mechanisms: In the first method CW, n of slow host is increased to decrease its transmission opportunity. In the second method the frame size of slow station traffic is reduced to decrease its transmission time for each transmission opportunity. Our objective is to make the long term channel occupancy time of slow and fast stations equal.


            As mentioned above, this is done in one of the two ways: (i) by increasing the CWmin of the slow stations, which causes the mean contention delay (E[Ds ] ) of slow station to increase; (ii) by reducing the frame size of slow stations, which causes successful transmission time (Ts,s) at each transmission opportunity to decrease. Therefore, According to Little's law, for any queueing system, the average number of customers in the system is equal to the average experienced delay multiplied by the average customer departure rate. Because each of the n, stations is contending with an HOL frame and Z,/E[L,] represents throughput in frames/seconds.

 

 “Resolving 802.11 performance anomalies through Qos differentiation”

H.Kim, S.Yun, I.Kang, and S.Bahk

 

            The idea of our differentiation scheme is to set CWmin for each bit-rate inversely proportional to the bit-rate. (Let l denote a bit-rate in the hierarchy, which we call class. In this letter, we will use the example of 802.11b, so there are 4 classes: 1 Mb/s, 2 Mb/s, 5.5 Mb/s, and 11 Mb/s. First, the highest bit rate terminals in the bit-rate hierarchy (i.e., 11 Mb/s) retain the current default value, i.e., CW(11) min = 32 (slots). Then CWmin of other bit-rate terminals is set to CW(x) min = CW(11) min · 11/x , where x = 1, 2, or 5.5. We will prove that through this simple configuration we can precisely create the throughput ratio corresponding to the bit-rate ratio. As a matter of fact, the readers should now notice, any throughput ratio can be created this way. For the ensuing analysis we make some simplifying assumptions as follows.

 

  • The number of terminals in the system, N, is large.
  • The maximum contention window size, CWmax, can be set high.
  • All nodes are within the receive range of each other. This assumption excludes the hidden terminal problem.

 

            Although these assumptions significantly simplify our analysis, they are not essential. In fact, the simulation results that corroborate the analysis are obtained in small N network.

            The second assumption is needed to ensure correct throughput ratio upon high contention, or equivalently, large number of back off. Since the payload size is independent of the nominal bit rate, the throughput ratio between different class terminals becomes the inverse ratio of the transmission times T(l). (The transmission time is what it takes until a class-l node to successfully transmit a packet).

            

Where Rij is the throughput ratio and K is the packet size in bits. so the packets are always transmitted in full size. To determine Rij , we just need to compute T(l) for each class l. T(l) is composed of several components:

 

1)      E[T(l)s ] : Packet transmission time of a class l terminal. With maximal packet size assumption, E[T(l)s ] = T(l)s =K/l.

2)      E[T(l)c ]: Average time wasted on a mangled packet transmission due to collision. It is a packet time, and does not contain the backoff times due to the collision.

3)      E[T(l)i ] : Average idle time between transmission attempts for a class l terminal. Since we assume that terminals are backlogged, this idle time is due to the backoffs for collision avoidance.

4)      E[T(l)o ]: Time of channel occupation by the terminals in classes other than l. In 802.11, when the terminal is detected busy, the backoff timer for the terminal in backoff is suspended. Therefore, this time is added to the total cost for the other terminals. Since “channel busy” could mean either successful transmission or collision, the possible collision time of other terminals is also accounted.

 


 “Ad hoc on demand distance vector (AODV) routing”

Perking C, Royer E B, and Das S

 

The Ad-hoc On-Demand Distance Vector Algorithm

            The basic proposal can be called a pure on-demand route acquisition system; nodes that do not lie on active paths neither   maintain any routing information nor participate in any periodic routing table exchanges. Further, a node does not have to discover and maintain a route to another node until the two needs to communicate, unless the former node is offering its services as an intermediate forwarding station to maintain connectivity between two other nodes.

 

The algorithm's primary objectives are:

·      To broadcast discovery packets only when necessary

·       To distinguish between local connectivity management (neighborhood detection) and general topology maintenance

·      To disseminate information about changes in local connectivity to those neighboring mobile nodes that are likely to need the information.

 

AODV uses a broadcast route discovery mechanism.

Path Discovery

            The Path Discovery process is initiated whenever a source node needs to communicate with another node for which it has no routing information in its table. Every node maintains two separate counters: a node sequence number and a broadcast id. The source node initiates path discovery by broadcasting a route request (RREQ) packet to its neighbors. The RREQ contains the following fields:

< source addr; source sequence #; broadcast id;

dest addr; dest sequence #; hop cnt >

 

            The pair < source addr; broadcast id > uniquely identifies a RREQ. Broadcast id is incremented whenever the source issues a new RREQ. Each neighbor either satisfies the RREQ by sending a route reply (RREP) back to the source or rebroadcasts the RREQ to its own neighbors after increasing the hop_cnt .

Reverse Path Setup

            There are two sequence numbers (in addition to the broadcast id) included in a RREQ: the source sequence number and the last destination sequence number known to the source. The source sequence number is used to maintain freshness information about the reverse route to the source, and the destination sequence number specifies how fresh a route to the destination must be before it can be accepted by the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of the RREQ. These reverse path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.

 

Forward Path Setup

            Eventually, a RREQ will arrive at a node (possibly the destination itself) that possesses a current route to the destination. If the RREQ's sequence number for the destination is greater than that recorded by the intermediate node, the intermediate node must not use its recorded route to respond to the RREQ. The intermediate node can reply only when it has a route with a sequence number that is greater than or equal to that contained in the RREQ. If it does have a current route to the destination, and if the RREQ has not been processed previously, the node then unicast a route reply packet (RREP) back to its neighbor from which it received the RREQ. A RREP contains the following information:

< source addr; dest addr; dest sequence #;

hop cnt; lifetime >

 

            By the time a broadcast packet arrives at a node that can supply a route to the destination, a reverse path has been established to the source of the RREQ. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination. A node receiving an RREP propagates the first RREP for a given source node towards that source.

            If it receives further RREPs, it updates its routing information and propagates the RREP only if the RREP contains either a greater destination sequence number than the previous RREP or the same destination sequence number with a smaller hop count .

 

Route Table Management

            In addition to the source and destination sequence numbers, other useful information is also stored in the route table entries, and is called the soft-state associated with the entry. Associated with reverse path routing entries is a timer, called the route request expiration timer. A mobile node maintains a route table entry for each destination of interest. Each route table entry contains the following information:

·         Destination

·         Next Hop

·         Number of hops (metric)

·         Sequence number for the destination

·         Active neighbors for this route

·         Expiration time for the route table entry

 

 


3. Problem definition

 

            Traditional solutions have some limitations when solving performance anomaly especially when dealing with multi-hop networks because in MANETs data rates of competitive nodes can not reflect the whole path’s rate information. We are now trying to apply the mechanism in unsaturated conditions and investigate the impact of mobility.

 

 


4. Proposed Methodology

 

A)  Motivation

            By introducing tiny modification to the IEEE 802.11 standard, nodes with higher bit-rate could have a more time share of channel than nodes with lower bit-rate.  

 

Two issues have been ignored.

i) Competition in MANETs usually occurs between multi-hop paths. At the intersection, the competition between different paths turns into a competition between nodes.


Fig. 1 Competition between two paths

 

            As shown in Fig.1, Node0 sends data to Node2 (denoted by Path1) and Node3 sends data to Node4 (denoted by Path2). Node 1 is needed for both paths as a route node. Traditional solutions make sure Node3 has absolute advantage to access the channel because Node3 select a much higher data rate than its competitive node. However, data rates can not reflect the whole information of two competitive paths. Although Node3 can take full advantage of the channel, congestion will occur on Path2 because the next hop (Node1 to Node4) is a low-rate link. Meanwhile, the multi-rate capability of Path1 has not been effectively utilized. In a multi-hop and multi-rate path, the overall throughput of a multi-hop path depends on the hop with the lowest throughput. In order to avoid unnecessary back-off, nodes on the same path should be taken as a whole.

ii) Initial contention window adaptation, as one of the solutions to solve performance anomaly, has some limitations, which come from the inefficient back-off mechanism. The main idea of initial contention window adaptation is adjusting CWmin according to equation (1):

 

                                                         (1)

 


 

            IEEE 802.11 standards support 1, 2, 5.5 and 11Mbps at the physical layer. As shown in Table , if two competitive nodes in an 802.11b network have chosen 11Mbps and 1Mbps separately as their data rate, as soon as collision happens, the high-rate node will initialize its CWmin with 32 and the low-rate node will initialize its CWmin with 352. This adjustment is necessary. On the other hand, when signal to noise ratio of channel is low, both nodes will choose 1Mbps as their data rate and initialize their CWmin with 352. Unnecessary back-off leads to a degradation of performance in both aggregate throughput and end-to-end delay.

 

B. Rate selection scheme of RBAR

            The rate selection of proposed mechanism is based on RBAR and can be incorporated into IEEE 802.11b. RBAR modifies the Duration field in RTS, CTS, DATA and ACK packets into Rate & Length (R&L). The R&L field defines 4 bits for Rate and 12 bits for Length. These changes will not conflict with the original definition in IEEE 802.11 standard. Moreover, the new R&L field can provide enough information for overhearing nodes to find out their own correct NAV value.

 

            The destination node selects the appropriate data rate based on the received power of RTS packet and stores the chosen rate and the size of the data packet into the CTS packet. After receiving the CTS packet, the source node responds to the receipt of the CTS by transmitting the data packet at the rate chosen by destination node. The new R&L field can also provide enough information for the overhearing nodes to update their NAV tables.

 

C. Proposed Protocol

            In the proposed mechanism, some other modifications are made based on RBAR.


Fig.2 Storage Structures

 

            We use “link” to refer to the point-to-point connections between two nodes through a wireless MAC, whereas we use “path” to refer to the end-to-end connections between two nodes through a routing protocol. As shown in Fig.2 (a), two new substructures are introduced to store its neighbor nodes’ MAC address and data rate. As shown in Fig.2 (b), a new structure, denoted by Path List, is introduced to store paths’ information. The first two substructures of Path List are used to store path’s source node and destination node’s IP addresses. The Path Rate substructure is used to record the reciprocal of the time that spent transmitting unit data packet from path’s source node to the destination node. Path Rate, which can be recognizes as the average data rate of the whole path, represents the whole path’s data transmission capacity so nodes on the same path have the same Path Rate. Competitive node’s competitive level (denoted by Path Level), which is the ratio of its own Path Rate to the competitive node’s Path Rate, is stored in Path Level substructure.


            Format of RTS and CTS remains unchanged because RTS and CTS packet play an important role such as helping overhearing nodes to update their NAV tables or estimating channel’s quality in RBAR. We use ACK packet and DATA packet for piggybacking messages between the nodes.

   


Fig.3 Modified MAC layer frame format

 

            As shown in Fig.3 (c), we modify the Rate&Length field in DATA packet into Rate&Pathrate in which the Path Rate subfield is used to piggyback the information stored in node’s Path Rate substructure. As shown in Fig3 (d), we modify the Rate&Length field in ACK packet into Rate&Pathlevel in which the Path Level subfield is used to piggyback the information stored in nodes’ Path Level substructure. In the following four sections, we give details of the proposed mechanism that is backward compatible with the legacy 802.11 DCF and RBAR scheme.

(1)   Estimation of Path Rate

            In order to acquire the whole Path’s rate information, the proposed mechanism always keeps tracks of two-hop neighbor’s state information. Similarly to most existing work node listens to all ongoing RTS and CTS packets. Node measures the channel quality between the sender or the receiver and itself by sensing the signal strength of RTS or CTS, respectively. Therefore, node estimates the transmission rate used to send data packet from itself to its neighbor node and stores them in its Neighbor List. Source node of a path needs to get the rate information of the whole path. The interactions between MAC and Routing layers are needed to achieve this approach.

    


Fig.4 A illustrative Example of Estimating Path Rate

 

            Take AODV a widely used ad-hoc routing protocol, as an example. We introduce a new subfield with the name of LD in the RREP packet of AODV. LD, with the default value of 0, is used to piggyback the information of Path Rate between nodes of the same path. After a successful routing, destination node sends RREP to source node via route nodes. After receiving RREP packet, node calculates the time spent transmitting unit data packet from itself to destination node based on the information stored in its Neighbor List and update the LD field of RREP. Only a source node of the path can update its Path List based on the information piggyback by RREP because only when receiving RREP, source node has acquired the whole path’s rate information. Source node stores the path’s information in its Path List which includes source node’s IP address, destination node’s IP address and the reciprocal of LD.

         Take a two-hop transmission as an example. As shown in Fig.4, Node3 sends data to Node1 using Node2 as a route node. After a successful routing, Node1 sends RREP to Node3 via Node2. After receiving RREP, Node2 updates RREP’s LD subfield from 0 to 0.091, which is the reciprocal of the data rate Node1 is using. After receiving RREP, Node3, as the source node of the path, stores the corresponding value of Path Rate, which is the reciprocal of LD, in its Path List.

 

(2)   Transmission of Path Rate

            Path Rate is piggybacked by the DATA packet of MAC layer to make sure all the nodes on this path can get it. Before transmitting DATA packet, node searches its Path List by source node and destination node’s addresses. If the path has been recorded, the DATA packet’s Path Rate subfield will be set to the corresponding value stored in Path Rate substructure. After receiving DATA packet, node searches its Path List by source node and destination node’s addresses. If the path has been recorded, node updates its Path List. Otherwise, add a new record in the Path List.

 

(3)   Calculation of Path Level

            When a node records more than one path in its Path List, it means collision occurs here and the node should calculate each path’s Path Level based on the Path Rate. Let N denote the number of paths that a node has recorded and PR_i represent the Path Rate of path_i. The Path level of path_ican be calculated by Equation (2).

 

   

 

            Path Level, which is the ratio of its own transmission rate to the average of its competitive paths’ transmission rates, represents a path’s competitive level. Path with higher Path Level can provide higher data transmission capability.

 


(4)   Adjustment of CWmin

            Before sending ACK packet, node searches its Path List by addresses and sets Path Level subfield of ACK packet to the value of corresponding Path Level. After receiving ACK packet, node updates its Path List and adjusts its CWmin. By adjusting CWmin, nodes on the path with higher Path Level have more opportunity to access the channel. Adjusted CWmin can be calculated by Equation (3).

 

     

            When there are no competitions in the network, all the paths’ Path Level is set to be 1 based on Equation (2), so we don’t adjust any nodes’ CWmin to make sure the proposed mechanism can be compatible with 802.11 DCF and RBAR scheme.

  


Fig.5 Illustrative Example of Adjusting CWmin


            Take the topology in Fig.5 as an example. Node3 sends data to Node1 using Node2 as a route node (denoted by Path2) while Node0 sends data to Node1 directly (denoted by Path1). Suppose that both of the source nodes, Node3 and Node0, have acquired all the information by the mechanism presented in Fig. 4 and have recorded the information in their Path Lists. Path Rate (denoted by PR in Fig.5) is piggybacked by DATA packet to make sure PR1 and PR2 can be acquired by Node1 and Node2. Collision happens between Path1 and Paht2 because Node1 records two paths’ information. Node1 calculates Path1 and Path2’s Path Levels (denoted by PL in Fig.5) based on Equation (2) and update its Path List. After receiving ACK packet, Node0, Node2 and Node3 update their Path List according to PL which is piggybacked by ACK packet and adjust their CWmin based on Equation (3). As shown in Fig.5, Node0 adjusts its CWmin from 32 to 55 while the other nodes keep their CWmin unchanged. This adjustment reflects the superiority and novelty of the proposed mechanism. We compare the proposed mechanism with some other approaches. RBAR [1] keeps all the nodes’ CWmin unchanged to make sure all the nodes have the same opportunity to access the channel leading to performance anomaly. Initial contention window adaption [5], which tries to solve performance anomaly by adjusting CWmin according to Equation (1), adjusts Node0’s CWmin from 32 to 352 and adjusts Node3’s CWmin from 32 to 176. This adjustment will lead to unreasonable allocation of channel because of unnecessary back-off. The proposed mechanism takes nodes on the same path as a whole and adjusts CWmin according to paths’ competitive levels to make sure nodes with a relatively higher competitive level have a higher opportunity to access the channel.

 


5. CONCLUSION

 

           

            Traditional solutions have some limitations when solving performance anomaly especially when dealing with multi-hop networks because in MANETs data rates of competitive nodes can not reflect the whole path’s rate information. The interactions between MAC and Routing layers are fully exploited to achieve higher performance. Source node of a path uses RREP packet to acquire the whole paths’ rate information and estimate the path’s data transmission capacity. When competition happens between paths, the proposed mechanism can reallocate the channel by adjusting competitive node’s CWmin based on each path’s Path Level. Simulation results show that comparing with RBAR, the proposed mechanism can not only solve the performance anomaly in multi-hop networks but also improve the overall performance by avoiding unnecessary back-off. Some problems remain unsolved in the proposed mechanism. We are now trying to apply the mechanism in unsaturated conditions and investigate the impact of mobility.

 

 


REFERENCE

 

[1]        G.Holland, N.Vaidya, “A Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks,” Proceedings of ACMMOBICOM '01,Rome,2001.

[2]        M.Heusse, F.Rousseau, G.Berger-Sabbatel􃧘and A.Duda,“Performance anomaly of 802.11b,” Proc.IEEE Int. Conf. Comput. Commun. (INFOCOM), pp.836–843, Apr.2003.

[3]        Tan, G., and GuRag, J., “Time-based Fairness Improves Performance in Multi-rate Wireless LANS,” Proceedings of USENIX’04 , USA, 2004.

[4]        A. V. Babu, and Lillykutty Jacob, “Performance Analysis of IEEE 802.11 Multirate WLANs:Time Based Fairness Vs Throughput Based Fairness,” Internaional Conference on Wireless Networks, Communications and Mobile Computing, 2005.

[5]        H.Kim, S.Yun, I.Kang, and S.Bahk, “Resolving 802.11 performance anomalies through QoS differentiation,” IEEE Commun. Lett., vol.9, no.7, pp.655–657, Jul.2005.

[6]        Yoo, S., Choi, J., and Hwan, J., “Eliminating the performance anomaly of 802.11b,” LNCS, 1055-1062, 2005.

[7]        Sadeghi,B., Kanodia,V., Sabharwal,A., and Knightly,E., “Opportunistic Media Access for Multi-rate Ad-Hoc Networks,” MOBICOM,2002:

[8]        Yongho S., Jaewoo P, and Yanghee C., “Multirate Aware Routing Protocol for Mobile Ad Hoc Networks,” Proc.IEEE Vehicular Technology Conf., pp.22-25, Apr.2003.

[9]        Hao Zhu, and Guohong Cao, “rDCF: A Relay-Enabled Medium AccessControl Protocol for Wireless Ad Hoc Networks 􃧘 ” IEEE Transations on Mobile Computing, Vol.5, NO.9, Sep.2006, pp.1201-1214.

[10]      Zeng W, Tan H, and Suda T, “A Relay Based MAC Protocol to Support Multi-rate Feature in Mobile Ad Hoc Networks,” Proc. of The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2005:145-154.

Comments

Popular posts from this blog

Chemical test for Tragacanth

Chemical test for Benzoin

Chemical test for Agar/Agar-Agar / Japaneese Isinglass