Printer Friendly

A distributed web-topology for the Wireless Mesh Network with directional antennas.

1. Introduction

The wireless mesh networks (WMN) can be thought as commercial extensions of mobile ad hoc networks [1], forming a wireless multi-hop backbone network with static nodes such as mesh routers and gateways. Wireless mesh networks have the properties of easy network maintenance, robust, self-configurable, reliable service coverage and low cost [2].

The communication with the pure directional antenna in the WMN differs from that of omni-directional communication [3]. Directional communication has properties, such as power saving, spatial reuse, shorter routes and smaller end-to-end delay [4]. IEEE 802.11 based networks also visualized using directional antenna due to its aforementioned properties and have increased signal quality through the beam forming gain [5][6][7]. Ref [6] has provided a detailed mathematical model and its advantages of using directional communication in the IEEE 802.11 environment. The use of directional antenna in WMN is beneficial to constructing backbone networks but it also adds complexity to the proces. The major challenges of directional communication are to discover the neighbors [8][9] to maintain the topology.

Much research has considered the formation and maintenance the topology using directional antennas [10][11][12][13][14]. By creating a topology we focus enhancing the performance of the network. The topology control protocol of ref. [10] tries to enhance the traffic delivery ratio in wireless mesh networks equipped with directional antenna. Ref. [11] and [12] tried to enhance the topology control and maintenance protocol for the wireless ad-hoc networks. When the numbers of links with neighbors are restricted, there is a high chance that the network would be partitioned in a sparse network. In a sparse network, the communication link is difficult to establish if the network is constrained with the number of links with its neighbors. Each research study in directional communication uses the power control mechanism as the solution to this problem. The main disadvantage of the power controlled mechanism is that the nodes at the physical boundary of the network are reached by other nodes by extending the power of directional transmission. These nodes at physical boundaries of the network might have limited neighbors to obtain connections. Most of the past research focused on getting connected to these nodes but not the other way around. We feel that these nodes should not be isolated for the long time to get connected to the main network. These boundary nodes could be key players in some of the network such as tactical network. In our research we tried to form the topology from the boundaries of the main network. Referring to Fig. 1, Nodes 5, 34, 61 63, 66 are at extreme nodes of the network. The construction of the topology starts from these nodes and moves towards the center of the network.

In this paper we propose a protocol to construct a node degree constrained topology that bounds all the nodes from the network boundaries. The node degree is the number of possible links by nodes with its neighbors. Since the links start from the network boundaries, we term these links as circum-links. The topology formed by such links is termed circum-topology. We modify this circum-topology to have extra links from the 3rd links, as to have bridge links between the circum-links. These bridge links are termed web-links and the overall topology with these web-links are termed Web-topology. The basic construction of web-topology is to have a predefined path for the communication. Wireless communication requires having a connection established to maintain communication [11].

The motivation behind our approach is to limit the node degree, whilst reducing processing complexity and still maintaining the network connectivity. Our protocol limits the number of connections to a maximum of three links, where two links are used to form circum-links and the remaining one is used to form the web-link, in the backbone network forming the robust topology [15]. The first contribution of our research is a design of an algorithm to construct degree constrained topology giving the priority to connect nodes at the boundaries of the network without much performance degradation. The algorithm design tends to reduce the chances of partitioning the network by adjusting transmission power of the directional antenna. Thus our topology is scalable and performs better in terms of end-to-end delay and throughput. Our next contribution is a recovery process of the lost path that affects the network performance. If the node fails for any reason, then the localized neighbor will perform a safety test to recover the broken links or create a new link to maintain the two degree link with the neighboring nodes. Any node joining or leaving the network can have seamless inclusion or deletion from the network by using the algorithm.


2. Background and Related Work

Our work on topology control requires an understanding of the directional communication used in wireless networks. Traditional communication via omni-directional antenna in wireless networks gives full connectivity to neighboring nodes as shown in Fig. 1. In this figure it is obvious that full connectivity comes with large interference from neighboring links. Extensive review of past research notes that most of the research focused on minimizing the interference; thus, creating only wanted links in the network that is achieved by directional communication. Various designs in Medium Access Control (MAC) and routing protocols have been proposed to have full control on the network. Much of the work on directional antenna focused on power control to reduce energy consumption.

Topology control is widely affected by the transmission power and the beam width of the directional links. Basel Alawieh et. al. in [16] provided a solution to control the transmission power of the directional links. The power of CTS/DATA/ACK can be adjusted by observing the power of the RTS packet and the node will have the optimum transmission power for successful communication. This can ensure the precise transmission power required for the communication compared to traditional power control transmissions. The RTS/CTS handshake mechanism for directional transmission has a known deafness problem when the node is currently engaged in communication [17].

Nodes with directional antenna need to have precise directional information to successfully communicate with their neighbors or at least be aware of possible communication. Ref [7] researched the impact of using the directional antenna model for simulation accuracy. This paper is one of the major works to find an accurate directional antenna model for simulation. Their basic research is on the availability of the antenna elements to the nodes for effective transmission and receiving. They calculate the directional gain of each transmission to direct the antenna sector towards the direction of the transmission. The location information provided by each of the nodes via HELLO messages will let neighboring nodes select the precise antenna sector for data communication. Gelal et. al. in [16] studied the topology control scheme Di-ATC, distributed topology is constructed with the angular information from the discovered nodes. Di-ATC is a time slotted synchronous model for neighbor discovery with directional communication. The main focus of Di-ATC is to limit the upper bound on node degree and observe network performance. This upper bounding reduces the path length and average hop count. However, as the node degree increases, the complexity of the network also increases. If the node degree is limited to the minimum possible links to decrease the network complexity, then the network can become partitioned. Therefore, there is a tradeoff between network complexity and node degree.

Q. Dong et. al. in [15] researched forming a robust topology by giving two different schemes Backlink-Based Algorithm (BBA) and Backlink shifting and tree edge removal Algorithm (SRA). Both schemes described in their paper tried to build an efficient topology with a small hop count between nodes and gateway. The main disadvantage of this topology was a consideration of the available links between the neighbors, as given by BBA, which had a large number of redundant links. Whereas, SRA removed the redundant links and still kept the network connected without having a partition in the network. The major disadvantage of the SRA algorithm was a limited 2-degree connection with the neighboring nodes; thus, yielding a large hop count due to the reduced links in the network. Both the described algorithms form a robust topology.

Building robust networks requires a bounded topology for reliable wireless network [15]. Multi-radio WMN has multiple radios for data communication. Research concentrated on the point-to-point connections between the neighboring nodes bounded by the number of directional radios the node has. The fully connected graph in a multi radio environment might be definitely robust but practically difficult to maintain. The obvious reasons were the interference from different radioes using the same channel and the complexity to control the multi radio environment.

Recent research on wireless networks with directional antenna [10] tried to maximize the delivery ratio by adjusting the orientation of the directional antenna appropriately. The basic research concept was to have a connection of the antenna to multiple nodes. The formation of topology was time consuming but the overall delivery of traffic was improved by 40% ~ 280%. The drawback of the algorithm was to require adjustments on the connectivity thus by changing the network topology continuously. This condition requires constant updates on the topology that require large control packet exchanges in the network. This may raise the congestion level in the network. In [14], authors used sectorized antenna to obtain topology control in IEEE 802.11 based wireless networks. Their approach was to reduce the interference posed by the links in the dense environment using the Received Signal Strength (RSS) value. The coordination between 802.11 MAC and Routing layer to construct and maintain the topology performed near-optimally. The increment in the performance compared to the omni-directional antennas is given by their test bed results. E. Anderson et. al. in [19] tried to model the environmental effects on directionality and study its effect on wireless networks. They performed a mathematical analysis of their system.

Several topology control protocols studied during this research such as [4][11][12][13][20], tried to improve network performance. Most of these protocols used a directional antenna based network. While doing so they had high connectivity among the neighbors, which is good when the path to the destination is broken and a new path is available for the communication. The main disadvantage of large connectivity is that the links are not fully utilized, so that they can have similar or better performance by limiting the connectivity of the nodes. DM Son et. al. in [21] found that the links can be limited to some K-degree and still have better performance. They provided simulated results in sensor networks, showing that by limiting the connectivity by the sensors, one can have efficient performance in the system. Another advantage of having limited connectivity is to conserve valuable energy resources. They suggested that the optimum value of K is 2, so that the network can still have better performance. In the case of directional antenna, the limitng degree of connectivity in the network is to limit the number of active sectors for a node. If the number of active sectors is limited, this will obiviously lead to the conservation of energy. We have bound the degree node in our network and still form the backbone links with the neighbors. In our scheme, even though we bound the degree of connectivity, the network is still well connected and efficient. To the best of our knowledge, there is no topology control with minimum degree connected to the network that is robust and efficient.

3. Proposed Scheme--Distributed Web-Topology Formation with Directional Antenna

The web-topology in WMN creates backbone links with the directional antenna. A topology similar to SRA is created with a 2-degree link to each node in the network. We term this circum-topology. The extra bridge links are added in this circum-topology to some of the nodes in the given topology. Circum-topology with bypass links is termed web-topology. Our topology reduces the network hop count from SRA based topology, thus improving message delay, buffer usage and thereby improving network throughput. All the links are backbone links of the network. We considered mesh routers and gateways equipped with GPS and x directional radios. We limited the upper boundary of the value to x = 3 for robust topology. The Minimum k-connected network is considered for better utilization of network resources. Two of the available directional antennas were used to create backbone links. The remaining radio was used for the web-topology formation. We use the term node for mesh routers and mesh gateways in this paper.

The directional antenna was configured with a beam width of 360[degrees]/n having n sectors. All n sectors, n = 6 in our case, were required to periodically broadcast HELLO messages. These HELLO messages are used to discover the neighbors and update the network information to their neighbors. Each of the HELLO messages included node ID, transmitting antenna sector, location information and 1-hop neighbor information. Each node maintained its own neighbor table from the received HELLO messages. By processing these HELLO messages for each node, neighboring nodes were discovered and the topology formation was initiated. The following two sub-sections discuss the process of discovering the neighboring nodes and topology formation.



3.1 Phase I--Two Degree Link Formation

This two-degree link formation is the basic phase in our web-topology formation process. The link establishment process was initiated after analyzing the information contained in the HELLO messages by the nodes. You can connect with all the neighboring nodes to form the fully connected topology without topology control similar to that shown in Fig. 1. The figures clearly show that topologies may not be suitable for effective communication due to interference from neighboring nodes.

The main objective of two-degree link formation is to have a degree bounded link formation among one hop neighboring nodes. This will avoid the possibility of interference among the 1hop neighboring nodes. The process to establish the links in the network is designed in a way to avoid partitioning of the network by following two-degree formation process. In this two-degree formation process, the formation of the links within 1hop neighboring nodes was initiated at the extremities of the networks. This can also be referred as a Circum-link formation. The end of the network means that that there are no nodes further than this position. The selection of such a node is done by counting the number of unique HELLO messages from the neighboring nodes.

The nodes receiving the least number of hello messages are selected to initiate the two-degree link formation process. These nodes are given the chance to form the links with the neighbors. This will help these nodes to be included in the network due to the least available neighbors. We form only two links between the nodes at this phase. We can term this two-degree link formation due to the formation of 2-links. We have implemented an angular method to find the appropriate two nodes for the link establishment, as shown in Fig. 2. In angular method, the localized central point is found for the neighbors of the node. For example, the central point of node [N.sub.15] is calculated among its neighbors. A virtual line is passed from this central point to node [N.sub.15], as shown in Fig. 2. The extended line passing through the localized central point and node [N.sub.15] will be used to find the orientation of the other nodes with respect to node [N.sub.15] and the central point.

Once the node [N.sub.15] gets its orientation of its neighboring nodes, it needs to find the minimum deviated nodes (MDNs) from its neighbors. The MDNs are calculated from the anti-clock wise direction from the virtual central line. For the evaluation we shifted the central point 180[degrees] along the axis towards the evaluating node, [N.sub.15], giving the reference to the angular orientation of all the nodes. The angular orientation of all the nodes will be evaluated along this virtual line. The nodes with minimum angular deviation from the central line in both clockwise and anti-clockwise direction will be considered as MDNs. The node with minimum neighbor node count will be given the first priority to establish the link with MDN neighbors. As shown in Fig. 3, the Link_Establishment_Request is sent by [N.sub.15] via the Hello message receiving sector of Node N2, updated in the neighbor table. It must go to the random delay, R_Delay for all the nodes to send the Link_Establishment_Request. x is least wait time period by the node before sending the Link_Establishment_Message. We have set the value as 1 ms, so that all the nodes within the neighbors can receive HELLO messages from their neighbors. If there are no neighbors, then the node will increase the transmission range, so that it can resend HELLO message to reach a longer distance.


R_Delay = x x Neighbor_count (1)

Referring to the Fig. 3, node with the least neighbor ([N.sub.15]) count will expire its' custom back-off time first before unicasting Link_Establishment_Request to its MDNs nodes, N2 and N3. Fig 3-(a) shows the node [N.sub.15] sending the link establishment request to its MDNs, Node N2 from the received antenna sectors. Other nodes overhearing this message at this sector will avoid sending any message. If more than one Link_Establishment_Request from the equidistant nodes is received by the node then it follows the right-hand rule to form the link. Once the node receives this message, acknowledge message is sent and thus will establish two-way links. All the nodes need to send this message to form a link with two neighboring nodes. Another Acknowledgement message is transmitted in all the sectors of node N2 to inform the neighbors about the link formation.

There are cases where nodes may not be receiving any Link_Establishment_Request or will receive this message even if it has already made its two-degree connection. If the Link_Establishment_Request message is not received, that means there are no MDNs in the area. Section 3.1.1 will resolve this situation. In the second case, node N18 is already connected with two links with its neighbors N13 and N19 and receives more link request message from node N12, as shown in Fig 3-(b). In this case, node the N18 should acknowledge this message and the link should be provided to the request node N12. This will be done by breaking one of the current two links which is near to this node N12. The node N13 is near to N12, so the breaking message by node N18 is sent to the node N13 and the link is broken. Node N12 will also be informed about this change. The Node N12 will send the Link_Establishment_Request to node N13 and will be acknowledged, as node N13 is currently having one link. The algorithm for link establishment process is shown in Table 1. The resultant topology after two-degree link formation is termed as circum-topology.

3.1.1 Node having no MDNs

A node has no Minimum Deviated Nodes (MDNs) if there are no neighbors within range of this node or all the neighbors are equidistant from each other, as in grid topology. The solution for the first condition would be an to increase the transmission power by a factor of x set at the beginning of the simulation and by checking if any node is included as its neighbors. The minimum increment is set beforehand and repeated increments are used to include new nodes from the network to its neighbor. This process is repeated until the required two-degree link, as explained in sub-section 3.1, is formed for the node. The solution for the 2nd case is to send the Link_Establishment_Request message to all its neighbors using all the required sectors of the directional antenna. Each receiver will decide according to its current link status whether to incorporate this new link.

If there are any request for the link formation from the nearby neighbors that does not have MDNs, the node receiving the link request will evaluate the condition of the link request. If the sender does not have two-degree links with it, then it will establish the link with the sender. If the requested node already had two-degree links from its neighbors then it will break one of the already established links and then connect the links with the requested node. The previous link is broken; links between nodes N18 and N13 and the new link is established between nodes N18 and N13. When there is more than one node, equidistant from the receiver, it sends the link request message, and then it follows the right-hand rule to form the link. This is in the case encountered in grid topology.

Fig. 4. shows topology formation after the first phase. This topology is a minimally connected network. We term it circum-linked topology without partition in the network. This topology does not have redundant links for data communication, since there are only two links in a node to be connected to the neighbors. Clearly, it requires fewer directional radios and more hop counts for a packet to reach the destination if any of the intermediate link breaks. This topology is the optimum solution in terms of the cost of the directional radio with minimum network maintenance.

3.1.2 Link Threshold

In this topology, we have a case where the nodes within the closed range given by the threshold value, T, are formed with the circum-links, as of the links between nodes [N.sub.0] and N9 as shown in Fig 4-(b). This is a waste of resources due to the close proximity of the nodes and can give rise to interference to the neighboring nodes. So after formation of the 2-degree links, it is evaluated with the nodes within the threshold value T. This value T is the transmission range of the omni-directional antenna. The minimum decrement of the transmission range is set the same as in section 3.1.1. The current link with the range and the existing link need to be broken and the link with the node whose distance is greater that threshold, T, established. If the distance to the neighbor is less than T, then further decrement is halted. In Fig 4-(b), node [N.sub.9] can reach node [N.sub.7] from the same sector. Here, nodes [N.sub.0] and [N.sub.9] are broken down and the new links are made with nodes [N.sub.9] and [N.sub.7]. Node [N.sub.0] can now be excluded from the backbone nodes. This node will be considered as a normal node that has the potential of being a backbone node. If a problem arises with node [N.sub.9], then node [N.sub.0] can later upgrade itself to the backbone node with the backbone facility.

This topology is not always good for all types of traffic. Most of the links are required to have a backup link in case of link failures. If more links are broken then the network is partitioned to two or more sub-networks. If having one more radio can solve the partitioning problem and improve the performance of the network then it is worth for a researching. The added radio network and one more link to some of the nodes could make the link robust. This is one of the reasons for us to propose a phase II to make a robust topology with the minimum possible radios.

3.2 Phase II--Web-Link Formation

In this phase, all the nodes may choose one additional link from the remaining neighbor nodes. This link is an extra link to have an extra backbone link towards all the possible nodes. After completing 2-degree link formation, any node having the highest neighbor count (i.e., all the nodes having eight neighbors in Fig 5-(a) and N10 in Fig. 5-(b) will initiate the web link formation process.


The Web_Link_Establishment message is used for a special link establishment process to link extra links from the available neighboring nodes if possible, as all the nodes have their link table upgraded with the information received from the acknowledge message. On receiving this Web_Link_Establishment message, the receiver will evaluate the following four conditions before sending the ACK message for the web-link establishment:

* There is no link in the same sector as the request;

* It does not have a third link;

* Request node is not two-hop neighbors;

* If the circum-links are formed within the very short distant routers, then drop the status of the router to the normal node.

An ACK message to be issued only when all the conditions above are met, will be sent in all directions, so that all the 1-hop neighbors are informed about the web-link formation. The other receiving nodes will now wait for their turn to send the Web_Link_Establishment message after the expiry of their backoff timing. Our approach is based on a distributed algorithm with local synchronization among the nodes by broadcasting a control packet in the network. Local synchronization is information exchange between the neighbors about the completion of the link formation. Without all nodes completing phase I, it is difficult to start phase II, as it is based on a previous phase. In the distributive algorithm, it is difficult to find the end of phase I, so the node in the localized neighbor with the largest back off time will broadcast the control packet after forming the links. The broadcast of control packets from all the nodes might cause congestion but the probability of being chosen as a node sending a web link establishment message is very low. For instance in Fig. 5-(a) and (b), only five and four nodes are capable of having web-topology in phase II, respectively.

We have used the right-hand rule to construct the complete topology. Fig. 5-(a) shows web-link for the grid topology with five nodes having the web-links. These links are special backbone links by which the packet can be routed to the destination with a shorter hop count. If the packet coming to Node [N.sub.7] needs to go to Node [N.sub.12] as the next hop, then this web-link can save several long hops. Phase I is also termed circum-link formation. We tried to cover all the nodes in the network to have a 2-degree link among its neighbors. In addition, the links from the web-link made a bridge to reduce the hop count. Fig. 5-(b) shows one possible web-topology with 16 nodes random topology, considering the right hand rule to construct the web topology. We can have many possibilities of web-topology following different rules to construct Phase II. All of the cases would perform in similar ways. Web-topology is a distributed topology formation scheme with a maximum node degree of three. Fig. 5 illustrates that web-topology reduces the hop count compared to SRA topology.

3.3 Link Failure

The nodes constantly update information from the network to keep up-to-date network information. If any node finds a missing link due to node failure or any other reason, then it tries to re-gain the link that has been broken. The regular updates of the network information from the periodic HELLO messages will keep track of the available nodes for the connection in case of any node failures. This helps the node to update its information and resume the network connectivity. Phase I is triggered with the information available from the HELLO updates, as soon as any node detects such link failure. After Phase I, Phase II will try to check for any possibility of having the web-link to the new topology by sending the Web_Link_Establishment message. If no links are updated then the normal process of work is resumed. If the network is added with new web-links then the updates are sent in the next HELLO message to inform the network. During this process, the topology will maintain the links and will not have the partitioned network unless large nodes in the network fail at once.

4. Performance Evaluation

We used control packet overhead, delay and queue usage as our metrics to evaluate our protocol. Control packet overhead is the average count of all control packets exchanged to form a topology. Control packet overhead gives a picture about control message exchanges to maintain the network. We used a routing protocol to add to our topology information. Then, we evaluated these two routing protocols with and without topology control. We count all the control messages exchanged in the network, while routing the data packet to the destination. The end-to-end delay and queue at each hop is recorded, while data are routed towards the destination. The queue value is the time that the data packet spent in the queue before being forwarded. We evaluated our topology formation with two different (proactive and reactive) routing protocols in two different environments. Routing Information Protocol (RIP) [22] was chosen for the proactive routing protocol and Ad Hoc On-demand Distance Vector (AODV) [23] was chosen for reactive routing protocol. From this point onwards, routing protocol with web-topology control is represented by RoutingProtocolNameWTC, e.g. AODVWTC and routing protocol without web topology control is represented by RoutingProtocolNameWOTC, e.g. AODVWOTC. We have considered the worst-case performance in both the routing protocols specifying several node failures, thus causing link failures. We also tested the recovery time of the topology in these scenarios.

4.1 Simulation Environment

We evaluated our web-topology formation in both the grid and random network using simulation with QualNet Simulator 4.5 [24]. The simulation areas measure 3000m x 3000m. All the nodes are equipped with three directional wireless radios and exposed to constant random mobility of 10m/s. All the radios strictly operate in directional mode for the transmission and reception of the packets, unlike in [25] where reservation based TDMA system was implemented for topology formation. The increment for the power adjustment of antenna is set to 1% of the initial transmission range of the directional antenna. The power of the directional communication set is 550 m. This range may change due to power control. The minimum transmission range allowed is 250 m, equivalent to omni-directional transmission. The scenarios were run with CBR and VBR traffic with packet size of 512 bytes at different packet sending rates from 1packet/s to 30 packets/s. QualNet has SUPER APPLICATION as VBR traffic. We have configured SUPER APPLICATION as VBR traffic. The transmission range of the directional antenna can be varied depending upon the requirements. This was set manually by the user due to the static nature of the network. All the nodes were connected with a fixed power source, so that the energy is not depleted in the middle of the transmission and the network is always connected. The performance of our protocol was also compared to the shifting and tree edge removal Algorithm (SRA) protocol [15]. The results are discussed in the following sections. All the results are the average of 20 simulations, with each simulation running for 600 sec with the combination of multiple source-destination pairs.

4.2 Simulation Results a) CBR Traffic

We simulated the given environment in two different conditions, one without topology control and other with web-topology overlaid over it. First, we would like to show the effect of topology control implemented in routing protocol. When the packet is transmitted in the multi-hop environment, packets need to travel from intermediate nodes towards the destination. The packet might experience some delay while relaying due to the intermediate nodes being pre-occupied with the ongoing transmission. This may lead to broken links. The number of broken links is added in the entire simulation time. Fig. 6 compares the link failures between the routing protocol with web-topology, AODVWTC and without web-topology, AODVWOTC. The broken link creates both delay and a large queue in the network. The number of links broken is highly reduced when topology control in overlaid in the routing protocol. As the volume of traffic increases, the rate of broken links increases in routing protocol without topology control. Both CBR and VBR traffic showed similar trends. Conversely, the routing protocol with topology control did not exhibit many broken links and did not show degradation when traffic increased. The routing protocol without web-topology control gives on-demand links to traffic that is temporary and can change depending upon the condition of the network. For the next transmission, these links are not guaranteed but for the routing protocol with web-topology control, the link exists. If any problem is detected, then the broken links are immediately repaired, as explained in section 3.3. The exchange of the control messages is about 24% higher in AODVWTC than AODVWOTC. The constant update of the network information in routing protocol with web-topology control is required to have extra message overhead, as shown in Fig. 7.

Distributed web-topology keeps itself up-to-date by exchanging network information via HELLO messages. These messages help to detect probable link failure or the failure of the nodes. As soon as failure is detected, the node will try to retrieve the failed link or establish a new link, according to Phase I, explained in section 3.1 and then followed by Phase II. The number of messages exchanged is recorded in all of the simulations and averaged over the number of nodes. Fig. 7 shows the number of control messages exchanged in AODVWOTC and AODVWTC. The number control messages increased, although the number of broken links is lower in AODVWTC than AODVWTC. The web-topology enabled routing protocol constantly monitors the network with the updated information.



Fig. 8 plots the average of the end-to-end delay for both topologies enabled routing protocol and routing protocol without web-topology. The delay is prominent in routing protocol without web-topology with almost 0.2 sec on average. The reason behind the rise in end-to-end delay is due to the waiting for the route for each of the transmitted packets. As discussed earlier, AODV requires finding the routing path for the data packet before transmission. Until the destination is discovered, the packet is queued in the network. This delay is cumulated until the final delivery of the packet to the destination.


While the packet waits for the node to be free and is relayed to the destination, it also has to be queued in the buffer. The size of the queue buffer should be sufficiently high to capture every packet that is transmitted and not dropped due to a full buffer. The size of the buffer available in each node will also affect the network performance. This creates unnecessary delivery delay. We analyzed the buffer usage in our protocol. We gave a large buffer size for each node and the buffer activities are monitored. Fig. 9. plots the maximum buffer size used during the simulation. It shows that when traffic increases the buffer usage is also increases prominently in AODV without web-topology control in CBR traffic, whereas AODV with web-topology control does not record much change in its buffer usage, as shown in Fig. 9-(a). This shows that the routing protocol with web-topology control required far less buffer space compared to the routing protocol without web-topology control. Fig. 9-(b) shows both routing protocol, with and without topology control, records an increase in buffer usage for VBR traffic. The buffer usage in AODV without topology control is larger than AODV with topology control. This is due to the nature of the VBR that is not predicted, as any of the nodes have random traffic generated at different time frames. This increase in unpredicted traffic causes increased usage buffer.


Analyzing the above graphs reveals that the routing protocol with web-topology control performed well in terms of number of broken links, control packet overhead, average end-to-end delay and buffer usage. Most of the metrics showed that routing protocol with web-topology performed better and is resilient to errors. We want to check the throughput of the network, as this is not the major metric of our protocol. Fig. 10 shows that AODVWOTC control does not furnish high throughput compared to the AODVWTC routing protocol. With backbone links provided by the web-topology, it is easy to get uninterrupted link transmissions. As shown in Fig. 8, there is not much delay in delivering data packets. Since there are no delays, the throughput should also increase for both CBR and VBR traffic. This is also supported in Fig. 10. There was about 43% increment in the throughput with our web-topology control scheme in AODV.

Fig. 11 shows the performance of RIP routing protocol with and without web-topology control protocol. We first performed the network without topology control with both CBR and VBR traffic and then repeated the same with our web-topology protocol. The result had the similar performance to that of AODV. The network without the topology did not perform well compared to the network with our web-topology.


Fig. 12 shows the throughput comparison between SRA algorithm and web-topology algorithm implemented in AODV routing protocol. In SRA enabled routing protocol, the data packet has a long hop distance to cover to reach its destination. It clearly shows that the additional web-link between some of the nodes will increase the throughput due to the reduced hop count. From Fig. 5 it can be seen that the number of hops is reduced from 3-hops to 1-hop at least by having the web-link. The only disadvantage of the web-link is that not every node is capable of forming this link, as explained in section 3.2. As the network size increases, the number of web-links also increases, thus yielding the required performance enhancement. The greater the number of nodes, the better the performance of the network in terms of throughput. At the lower node counts, the number of web-links created is less, so the improvement in performance is not visible compared to the situation with a large number of nodes.



5. Conclusions

Fully directional communication in WMN requires constant information exchange to track the neighboring nodes. Our web-topology protocol forms topology based on system limitations, such as a limited number of antennas and neighbors. The protocol is distributed in nature with two major steps to create the topology. We designed the circum-link formation protocol to have the circum-topology that is capable of including all the nodes in the network. The formation of the circum-link topology is distributed, as all nodes fulfilling the criteria can send messages to join the network.

We also designed the process to form the web-link by creating a bridge link in the circum-topology, thus creating web-topology. Not all the nodes are authorized to form this link. Due to the limited degree to form the links, the web-topology is easy to maintain and scalable. We have also formulated the protocol to form topology, including the nodes reachable by all the nodes in the network. We tested our protocol by superimposing our topology control protocol with proactive and reactive routing protocols. We compared our web-topology protocol to the routing protocol without topology control and found that our assumption holds true. The metrics that we set gave positive assessments regarding our protocol. We also compare the results from the SRA protocol and found that our web-topology is superior.

DOI: 10.3837/tiis.2011.01.011

Received September 2, 2010; revised November 27, 2010; accepted December 25, 2010; published January 31, 2011


[1] Myung J. Lee, Jianliang Zheng, Young-Bae Ko and Deepesh Man Shrestha, "Emerging standards for wireless mesh technology," IEEE Wireless Communications, vol. 13, no. 2, pp. 56-63, Apr. 2006. Article (CrossRef Link).

[2] Martin Duke, Guangyu Pei and Jae H. Kim, "Topology formation in degree constrained directional antenna network," in Proc. of Military Communications Conference Military Communication Conference 2007, pp. 1-6, October 29-31, 2007. Article (CrossRef Link).

[3] Guoqing Li, L. Lily Yang, W. Steven Conner and Bahareh Sadeghi, "Opportunities and challenges for mesh networks using directional antennas," in Proc. of First IEEE Workshop Wireless Mesh Networks (WiMesh '05), September 26, 2005. Article (CrossRef Link).

[4] U. Kumar, H. Gupta and S.R. Das, "A topology control approach to using directional antennas in wireless mesh networks," in Proc. of IEEE International Conference on Communication (ICC '06), pp. 4083-4088, June 11-15, 2006. Article (CrossRef Link).

[5] Vivek Jain, Anurag Gupta, Dhananjay Lal and Dharma P. Agrawal, "A IEEE 802.11 DCF based MAC protocols for multiple beam antennas and their limitations," in Proc. of IEEE Mobile Adhoc and Sensor Systems Conference (MASS 2005), pp. 474, 7-10 Nov. 2005. Article (CrossRef Link).

[6] F. Babich and M. Comisso, "Throughput and delay analysis of 802.11-based wireless networks using smart and directional antennas," IEEE Transactions on Communications, vol. 57, no. 5, pp. 1413-1423, May 2009. Article (CrossRef Link).

[7] E. Anderson, G. Yee, C. Phillips, D. Sicker and D. Grunwald, "The impact of directional antenna models on simulation accuracy," in Proc. of 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt, 2009), pp. 1-7, June 23-27, 2009. Article (CrossRef Link).

[8] Gentian Jakllari, Wenjie Luo and Srikanth V. Krishnamurthy, "An integrated neighbor discovery and MAC protocol for ad hoc networks using directional antennas," IEEE Transactions on Wireless Communications, vol. 6, no. 3, pp. 1114-1024, March 2007. Article (CrossRef Link).

[9] E. Felemban, R. Murawski, E. Ekici, SJ Park, KW Lee, J. Park and ZH Mir, "SAND: Sectored-antenna neighbor discovery protocol for wireless networks," in Proc. of The Seventh Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON2010), pp. 1-9, June 21-25, 2010. Article (CrossRef Link).

[10] Jun Zhang, Zhongming Zheng and Xiaohua Jia, "Improved topology control method for maximizing traffic delivery ratio in wireless mesh networks with directional antennas," in Proc. of IEEE International Conference on Communication (ICC 2009), pp. 5437-5351, June 14-18, 2009. Article (CrossRef Link).

[11] Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy and Neal E. Young, "Topology management in directional antenna-equipped ad hoc networks," IEEE Transactions on Mobile Computing, vol. 8, no. 5, pp. 590-605, May 2009. Article (CrossRef Link).

[12] Z. Huang, C. Shen, C. Srisathapornphat and C. Jaikaeo, "Topology control for ad hoc networks with directional antennas," in Proc. of. 11th IEEE International Conference on Computer Comm. and Networks (ICCCN '02), pp. 16-21, Oct 14-16, 2002. Article (CrossRef Link).

[13] Qin Liu, Xiaohua Jia and Yuan Zhou, "Topology control for multi-channel multi-radio wireless mesh networks using directional antennas," Wireless Networks 2010, Springer Netherlands, pp. 1022-0038, Computer Science, July 2010. Article (CrossRef Link).

[14] P. Subramanian, H. Lundgren, T. Salonidis and D. Towsley, "Topology control protocol using sectorized antennas in dense 802.11 wireless networks," in Proc. of Network Protocols, 2009. ICNP 2009. 17th IEEE International Conference on, pp. 1--10, Oct. 13-16, 2009. Article (CrossRef Link).

[15] Qunfeng Dong and Yigal Bejerano, "Building robust nomadic wireless mesh networks using directional antennas," in Proc. of IEEE INFOCOM 2008, pp. 1642-1632, April 13-18, 2008. Article (CrossRef Link).

[16] B. Alawieh, C.M. Assi and W. Ajib, "Distributed correlative power control schemes for mobile ad hoc networks using directional antennas," IEEE Transaction on Vehicular Technology, vol. 57, no. 3, pp. 1733-1744, May 2008. Article (CrossRef Link).

[17] Masanori Takata, Masaki Bandai and Takashi Watanabe, "A MAC protocol with directional antennas for deafness avoidance in ad hoc networks," in Proc. of IEEE GLOBECOM 2007, pp. 620-625, Nov. 26-30, 2007. Article (CrossRef Link).

[18] Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy and Neal E. Young, "An integrated scheme for fully-directional neighbor discovery and topology management in mobile ad hoc networks," in Proc. of IEEE Mobile Adhoc and Sensor System (MASS) 2006, pp. 139-149, October 9-12, 2006. Article (CrossRef Link).

[19] Eric Anderson, Caleb Phillips, Douglas Sicker and Dirk Grunwald, "Modeling environmental effects on directionality in wireless networks," Mathematical and Computer Modeling (2010), In Press. Article (CrossRef Link).

[20] Li Li, J.Y. Halpern, P. Bahl, Y.M. Wang and R. Wattenhofer, "A cone-based distributed topology-control algorithm for wireless multihop networks," IEEE/ACM Transactions on Networking, vol. 13, no. 1, pp. 147-159, Feb. 2005. Article (CrossRef Link).

[21] Dong-Min Son and Young-Bae Ko, "k+ Neigh: An energy efficient topology control for wireless sensor networks," in Proc. of Symposium on Systems, Architectures, Modeling and Simulation Samos (SAMOS VII), pp. 454-463, July 16-19, 2007. Article (CrossRef Link).

[22] G. Malkin, "RIP version 2," RFC 2453, 1998. Article (CrossRef Link).

[23] Charles E. Perkins, Elizabeth M. Royer and S. R. Das, "Ad-hoc on-demand distance vector (AODV) routing," IETF Internet Draft, draft-ietf-manet-aodv-05.txt, March 2000. Article (CrossRef Link).

[24] QualNet Simulator version 4.5, Scalable Network Technologies, Article (CrossRef Link).

[25] Zhensheng Zhang, "Pure directional transmission and reception algorithms in wireless ad hoc networks with directional antennas," in Proc. of IEEE International Conference on Communications 2005, pp. 2286-2290, Vol. 5, May 16-20, 2005. Article (CrossRef Link).

* Corresponding author: Young-Bae Ko

Arun Ranjitkar and Young-Bae Ko

School of Information and Communication, Ajou University

Wonchundong, Youngtonggu, Suwon, S. KOREA

[e-mail: {arun, youngko}]

A preliminary version of this paper appeared in the 4th Int'l Conf. on Networked Computing and Advanced Information Management (NCM 2008). This research was supported by the MKE(The Ministry of Knowledge Economy), the Korean government, under the ITRC (Information Technology Research Center) support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2010-(C1090-1021-0011)).

Arun Ranjitkar received a B.S. degree from N.E.D. University, Pakistan in 2000, a M.S. degree from Tribhuvan University, Nepal in 2003. He is currently working towards a Ph.D. degree at the Graduate School of Information and Communication, Ajou University, South Korea. His research interests are routing and MAC in wireless networks equipped with directional antennas.

Young-Bae Ko is an Associate Professor in the School of Information and Computer Engineering at Ajou University, Korea, leading the Ubiquitous Networked Systems (UbiNeS) Lab. He was also a visiting professor of the Coordinated Science Lab in the University of Illinois at Urbana Champaign (UIUC) for the 2008-2009 academic years. Prior to joining Ajou University, Dr. Ko was with IBM T.J. Watson Research Center (New York) as a research staff member in the department of Ubiquitous Networking and Security. He received his Ph.D. degree in computer science from Texas A&M University, USA, and B.S and M.B.A from Ajou University, Korea. His research interests are in the areas of mobile computing and wireless networking. In particular, Dr. Ko is actively working on mobile ad hoc networks, wireless mesh networks, ubiquitous sensor networks, and tactical networks. Also, he is an expert on various wireless access technologies, such as WLAN, WPAN, and WMAN. He is one of the BEST PAPER award recipients from the ACM MobiCom (in 1998). He served on the program committees of several conferences and workshops, such as IEEE Infocom, SECON and ICC. See for further details.
Table 1. Algorithm for the formation of web-topology.

1. Let V = {v|v [member of] Neighbor Nodes}


3. Hello Message sending process()

4. Prepare to send HELLO

5. While notAllVerticesVisited(V) do

6. send the periodic HELLO messages

7. end while


9. Hello Message reception process()

10. While notAllVerticesVisited(V) do

11.   receive HELLO messages

12.   Calculate Maximum Deviated Nodes (MDNs)

13.   If MDN then

14.     select the nearest neighbor node after some backoff timer

15.   Custom backoff timer Co_BO_Time = R_SIFS x (Neighbor Number)

16.     Co_BO_Time expire

17.     send Link_Establishment_Request to MDNs

18.   else

19.     send Link_Establishment_Request to all neighbors

20.   end if


22.   Start Link Formation process()

23.     If node without any links then

24.     Accept the link request and Send acknowledgement

25.     else if one link exists then

26.     Accept the link request and Send acknowledgement

27.     else if two links exist then

28.     Calculate the link nearest to requesting node

29.     Send message to break the link and Remove the link

30.     Establish the new link to the requesting node

31.     Send acknowledgement

32.     end if


34.     Start Web-Link process()

35.     While V <= 2 degree nodes do

36.     Check if the web link is possible

37.     If possible then

38.     Create the weblink

39.     End if

40.     End while

41. End while
COPYRIGHT 2011 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ranjitkar, Arun; Ko, Young-Bae
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Jan 1, 2011
Previous Article:Analyzing moderating effects of WiBro user experiences.
Next Article:Efficient 3D model based face representation and recognition algorithm using pixel-to-vertex map (PVM).

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |