Cluster Based Multi Hop Wireless Network Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract. Multi-path routing has been studied widely in wired networks. Multipath routing is known to increase end-to-end throughput and provide load balancing in wired networks. However, its advantage is not obvious in wireless

multi-hop network because the traffic along the multiple paths may interfere with adjacent paths. In the paper, we introduce a new multi-path routing scheme, Cluster-Based Multi-Path Routing for multi-hop wireless networks. The main idea of the proposed routing scheme is to extend the hop-by-hop multi-path to a cluster-by-cluster multi-path. In cluster network, each cluster can work independently from other clusters and hence reduce interference. The purpose

of the proposed scheme is to find a less interfering path for wireless multi-hop networks. We also showed the throughput improvement of the proposed scheme through simulations[3].


Multi-hop ad hoc networks or sensor networks are increasingly essential for commercial infrastructures, military settings, crisis monitoring, and public safety. Our objective in this paper is to make these networks more powerful by increasing their overall throughput, service capability, and individual unit flexibility. This work provides further benefits by improving the power efficiency of the network nodes, which implies smaller, more affordable units, permitting the deployment of more units[2].

We consider a large collection of autonomous nodes or terminals that communicate with each other by forming a multi-hop wireless network and maintaining connectivity in a decentralized manner. Cooperation among nodes can be done in different communication layers. Fig.1 shows cooperation in the physical layer and in the link layer[1].

Recently, with the proliferation of mobile communication services, a lot of routing schemes have been proposed in wireless networks. Some of them used multiple routing paths to obtain load balancing and make transfer speed faster. It is known that multi-path transporting may decrease the end-to-end delay and increase the whole throughput between source and destination[3].

Fig. 1. Transmitting nodes group into cooperative clusters to relay the information from the source to the destination. (a) The information source reaches the first relay cluster. (b) The nodes in the relay cluster share their information for diversity gain. Then they relay the information to the next cluster. (c) The next cluster has a reliable channel with the destination node, hence there is no need of physical layer cooperation. A single node can relay the information to the final destination node. [1],[2]

However, in the multi-hop wireless networks such as ad-hoc network, transmission over multiple paths is not as efficient as in wired networks because of the RTS/CTS interference between paths, merged path, signal collision, hidden node, and exposed node problem [7].These problems may cause data loss, delay or low throughput[3].

In multi-hop wireless networks, it is important to design a routing algorithm to alleviate these interference problems[3]. In the paper, we investigate the effect of interference between routing paths in a wireless multi-hop network by simulation and then propose a new scheme to set up improved multiple paths between source and destination leveraging the cluster-based routing. The proposed cluster-based multi-path routing (CBMPR)[3] will achieve maximum throughput and low delay by selecting multiple paths with little interferences among them.

Review of work on multi-path routing

Multi-path routing can be classified into three types according to the purpose of the multiple paths.

The first one is to get a back-up path for emergency. The back-up path is set up simultaneously as the main path. When the main path is down, the source node uses the back-up path. AOMDV (Ad hoc On-demand Multipath Distance Vector) is a typical example of this type[4].

Secondly, multiples paths can be used to handle congestion and keep load balancing. When a path has heavy traffic, other paths will be utilized to reduce the congestion[5-6].

Finally, multiple paths can be used to increase the end-to-end performance (e.g., high throughput and low delay) by transporting data through multiple paths. The proposed routing protocol in this paper can be classified into this category. The efficiency of this type is shown in Fig. . In 802.11, a sender node sends a Request To Send(RTS) message before establish a transmission, if the receiver node is idle to receive data, it sends back a Clear To Send(CTS) message, anyone sides in sender or receiver's transmission range which sense the RTS or CTS, have to set Network Allocation Vector(NAV) and stop all communication. RTS/CTS handshake algorithm is good for avoiding signal collision for a wireless network, but also, it brings unexpected delay from NAV waiting time[3].

(a) (b)

Fig.2 (a). RTS/CTS interference in single multi-hop path. (b). Decrease of transmission interval for load utilization in multi-path.[3]

In Fig2.(a), packet is relayed through a multi-hop path from node 1 (source) to node 5. The source must wait 3 transmission time to successfully send next packet because of the RTS/CTS interference. While node 2 is receiving packet, node 3 has to keep silent because it senses node 2's CTS, so node 3 cannot transmit packet to node 4.

Therefore node 1 can send next packet only when node 2 does not sense any transmission from node 3.

Fig2.(b) shows a multiple path case, where source and neighbor nodes suffer less interference than the single path case because of the enough distance between the paths. In the multi-path case, the waiting delay to send the next packet at source will decrease from 3 transmission time (4t-t) to 2 transmission time (3t-t), resulting in 50% throughput gain.

Inherent Problems in Multiple Transporting

In multi-hop wireless networks, it is shown that channel utilization becomes nearly 1/3 or 1/4 of channel's capacity at best due to the RTS/CTS interference between neighboring nodes. While a node is sending data to the next node, other nodes within the source and neighbor's transmission range must set NAV and keep silent. Certainly, this kind of interference also happens between two or more nearby paths as shown in Fig. 3. In the upper path of Fig 3, the 4th node does not have any interference from 2nd node in the same path, however it have CTS interference from the node in the below path.

Fig. 3. Interference between two paths. The dotted-circle is the node's transmission range. Nodes within each range sense other node's RTS or CTS and keep silent.[3]

If several paths pass through a node to get a destination, the joining node will experience a heavy congestion and produce large end-to-end delay. If we choose a multiple paths routing algorithm without any means to prevent the path joining problem, there will be very high probability to meet the path joining problem. It is because routing algorithms search the best path using same metrics. In order to investigate the effect of inter-path interference and path joining, we have simulated multi-path transportation for three cases; 1) paths are mutually interfering, 2) two paths merge at the third node, 3) all paths are apart far enough to interfere each other. We used GlomoSim simulation package[8].

Simulation result is shown in Fig. 4. As we can see from the figure, using several paths is of no use if there is interference between paths or the paths merge. The endto- end throughput decreases when an interfering path is added to the main path. On the other hand, the end-to-end throughput increases by adding multiple paths if the paths are free from transmission interference. Finding multiple disjoint paths with little or no mutual interference is thus very important. In the next section we present an approach to find efficient multiple disjoint paths.

Fig.4. Throughput for various number of hops for three cases: (a) without any interference, (b) with joining paths, (c) RTS/CTS interference between neighboring paths[3].

Cluster-Based Multi-Path Routing

Fig. 5. (a) Multiple Paths established with conventional multi-path routing protocol (b) Multiple Paths established with CBMPR[3]

The proposed cluster-based multi-path routing (CBMPR) combines cluster-based routing and multi-path routing efficiently.

The CBMPR makes use of cluster network to find multiple paths that provide independent paths. Fig. 5 compares an example of conventional multi-path routing and the CBMPR. Fig 5(b) shows an example of multiple paths which will suffer less interference by choosing routing paths through different clusters.

The main advantage of CBMPR over conventional multi path routing is less interference. Another strong point of CBMPR is its simplicity. Each path in the CBMPR just passes through the heads of clusters, resulting in a simple cluster level hop-by-hop routing. This makes CBMPR convenient and simple reducing the burden of interference calculation needed at every intermediate node[3].

Route-Id Algorithm

Even though the proposed CBMPR can mitigate the interference problem efficiently, path joining problems may occur because path joining can be easily created while choosing cluster-by-cluster link. With the path joining, the throughput will be worse seriously.

As a solution to avoid the path joining problem, a algorithm[3] is proposed here

Sender choose the neighbour clusters for forwarding the message.

Sender node allot a Path ID(PID) to the chosen clusters.

These PID and sender cluster ID(CID) stored in a register RRQ.

Forward the information of RRQ to the next cluster.

Gateway node which received the RRQ advertises the PID to other members then the PID will be stored in each member node of current cluster .

On Receiving a new RRQ, the source address and PID are compared with stored information in the node’s routing table.

If (new RRQ=stored RRQ)

then the request will generate path joining, and should be dropped.

Repeat the above process till destination address will found.

Destination verifies there is no path joining among the multiple path it sends back a RRP to the source.

Simulation results and discussion

We have simulated the CBMPR to investigate how cluster based multi paths is selected. In simulation, we assume each cluster has four nodes. In each cluster, cluster head and gateway nodes are assigned for cluster-level communication. We used static routing and selected paths manually according to the CBMRP. Each path passes three clusters through cluster heads. Link bandwidth are set to 5, 10, 20 and 50Mbps. Nodes are placed in a 1200m x 1200m area and 1024 bytes CBR packets are generated with an interval of 5ms. Simulation result is shown in Fig. 6 respectively[3].

Fig. 6. Throughput of CBMPR.[3]

With bandwidth of 20Mbps and 50Mbps, throughput increases about 5~8% for each additional path, finally reaching at 20~24% increase with four paths. This result is same with the case of the 1st line in Fig.3, the throughput without any interference. From this result, it can be said that the CBMPR selects almost interference-free paths from source to destination. It is also noted that the throughput saturates when there are two paths if the radio bandwidth is 5 Mbps, and addition of more paths does not improve the performance. With bandwidth of 10Mbps, throughput increase slowly when 3rd and 4th path are added. This might be the result of the congestion due to inter-path interference at the source and destination node where paths should be merged. The saturation point increases as the radio bandwidth increases.


Most of multi-path transporting researches are focused on wired network. Wired networks have no interference between each path and the efficiency of multi paths is great. For multi-path transmission over wireless multi-hop networks, efficiency is dependent upon the interference among the paths. The traffic is disturbed by RTS/CTS interference and suffers from the congestion at the path joining points. proposed routing protocol CBMPR is shown to alleviate these problems. We simulated the CBMRP and found out its improvement. It is also noted that CMNPR can be realized with less complexity compared to conventional multi-path routing schemes which usually requires measuring the interfering signal strength.