Performance of Cellular Multicast using the Mobile Ad- hoc Networks

D. B. Jagannadha Rao; Durgadevi Sathi

Performance of Cellular Multicast using the Mobile Ad- hoc Networks

D. B. Jagannadha Rao¹, Durgadevi Sathi²

Associate Professor, Department of C A, Sreenidhi Institute of Science and Technology, Hyderabad, India
Assistant Professor, Department of I T, Sreenidhi Institute of Science and Technology, Hyderabad, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

To overcome the limitations of cellular networks, cellular networks integrated with the ad hoc networks. The basic idea is to allow the cellular receivers experiencing poor channel conditions to use the ad hoc network to connect to those cellular receivers that are experiencing good cellular channel conditions. Base station manages multiple groups, whereas hybrid networks can be used when ad hoc networks cannot accommodate all the groups and base station has to select a subset of groups to maximizing bandwidth savings and utilization of the ad hoc networks. We proposed the group selection problem is formulated as a multidimensional knapsack problem, and an integer linear programming (ILP) formulation and a polynomial- time dynamic algorithms. Simulation studies demonstrate that the dynamic algorithm is able to achieve very good performance under various conditions than the ILP approach. ILP always gives optimal solutions, but it becomes time consuming for large groups and high capacities. The dynamic algorithm wins by distinguishing between good and bad groups using the utility function. It selects groups which consume less bandwidth or larger groups to optimize the objective function. We have to implement the distributed dynamic algorithm in real systems and checking the feasibility and performance of this approach.

Keywords

Ad hoc Networks, Cellular Networks, GSM, hybrid networks, Integer linear programming.

I. INTRODUCTION

A cellular network usually consists of a wired backbone formed by fixed base stations (BSs). Mobile users subscribe to a BS and communicate directly with it. The main advantage of cellular networks is large cell coverage. However, they often offer very limited bandwidth (e.g., 3G networks support a bandwidth of 384 kb/s to 2 Mb/s), and the BSs are potential performance bottlenecks when there is a large number of users in the same cell. To overcome the limitations of cellular networks, there has been extensive research on integrating ad hoc networks and cellular networks. In wireless ad hoc networks, mobile nodes form a network instantly without Headings infrastructure support. Each mobile node could act as a router in the network, relaying data packets for others over multihop wireless links. Thus, in a hybrid cellular–ad hoc network, mobile hosts can be used to relay packets for other nodes to increase the coverage of BSs or avoid dead spots [1], [2]. They can also redirect traffic within a congested cell to a neighboring noncongested cell [3], [4]. In addition, system throughput can be increased when BSs switch between ad hoc mode and cellular mode [5] or when mobile users experiencing good channel quality (called proxies) relay packets for other nodes. A number of hybrid architectures have been proposed to use “multicast” to send packets to multiple receivers [8]– [10].Multicast is an efficient mechanism for point (or multipoint) to multipoint communication, which has been widely used in both wired and wireless networks. It utilizes a tree or mesh data delivery structure to reduce identical packets on the network links and preserve link bandwidth. By exploiting the benefits of multicasting among mobile users (i.e., ad hoc multicast), these architectures can enhance network performance, especially for applications with heterogeneous receivers. Our paper, on the other hand, targets at the scenarios in which BSs manage multiple groups simultaneously. We consider all types of groups, namely 1) groups solely formed by local users in one cell, 2) groups consisting of users from other cells, and 3) virtual groups implicitly formed by users receiving the same content, such as web content and streaming media. To reduce multicast traffic load on BSs, we also propose using ad hoc multicast (called “ad hoc mode”). However, due to the capacity limit of the ad hoc network, if all the groups are routed in ad hoc mode, the network may become congested, and the performance of these groups may be degraded significantly. Thus, it is critical to determine which groups should be admitted into the ad hoc network so that the work load on BSs is minimized and the utilization of the ad hoc network (without exceeding its capacity) is maximized at the same time. We refer to this problem as the “group selection problem.”

In this paper, we formulate the group selection problem as a multidimensional knapsack problem by taking wireless interference among neighboring nodes into consideration and present an integer linear programming (ILP) formulation and a dynamic algorithm to solve the hard problem efficiently. We conduct simulations to evaluate the proposed algorithms. The results demonstrate that the ILP approach gives the optimal solution, but it is not feasible for large networks with high capacities. The proposed dynamic algorithm, on the other hand, can achieve near-optimal solutions, and it is more appropriate for online dynamic systems. By the end of introduction section include the paper organization. This paper is organized as follow: Section 1 gives the introduction of the Routing Efficient Opportunistic. Section 2 is helpful to understand the background of related work. Section 3 explains the System modeling. Section 4 show the performance of proposed technique and at last section 5 concludes the paper and followed by the references.

II. RELATED WORK

The tradeoffs between cellular and ad hoc networks has stimulated a lot of efforts to integrate these two types of networks for various purposes. Some proposals focus on increasing cell coverage or balancing load among cells [1]–[4]. In [1], Lin and Hsu use mobile nodes to relay packets between BSs and mobile nodes in order to reduce the number of BSs and increase cell coverage. In [2], an ad hoc global systems for mobile communications (GSM) network platform is developed to improve GSM coverage and avoid dead spots. Wu et al. propose a mobile-assisted data forwarding scheme to direct traffic in a hot cell to neighboring cold cells using an ad hoc overlay [3]. In [4], De et al. propose a load balancing scheme called iCAR for cellular networks, which places ad hoc relay nodes at strategic locations to relay traffic from congested cells to noncongested ones. there have been some recent proposals on enhancing cellular multicast performance using ad hoc networks. Hauge et al. propose a hybrid network architecture to increase the coverage of high-bandwidth group service [8], [9]. Park and Kasera develop a routing algorithm to find ad hoc paths from proxies to cellular multicast receivers [10]. Unlike these two schemes, which attempt to improve the performance of individual multicast groups, the goal of this paper is to maximize the performance of the whole network when there are many coexisting groups. Our basic idea is to minimize the load of BSs by selecting appropriate multicast groups to be handled by ad hoc networks.

III. GROUP SELECTION PROBLEM

3.1. PROBLEM DESCRIPTION

We consider a single cell with a BS serving a number of mobile nodes. Each mobile node has two wireless network interfaces, namely 1) a high-data-rate (HDR) interface and 2) an IEEE 802.11 interface. When there is a need for a set of nodes (including mobile nodes and the BS) within the cell to set up a group for communication among themselves, each mobile node connects to the BS, sending data to and receiving data from the BS using point-to-point links.1 We refer to this relaying scheme as the cellular mode. Alternatively, we have the ad hoc mode, in which group members can set up an ad hoc multicast tree using the 802.11 network interface. Mobile nodes in the cell can duplicate and relay packets for this group. In this way, the BS does not need to relay packets (or relays at most once if it is a member of the group), thus saving some bandwidth. The amount of bandwidth saved is proportional to the number of users within the group (i.e., the group size) and the group data rate.

For convenience, in this paper, we will only consider the case when all the members are mobile nodes. Our solutions can be easily adapted to the case when the BS is also a member of the group ad hoc mode. However, when there are multiple coexisting groups in the network, the ad hoc network may not be able to accommodate all the groups due to its limited capacity. In this case, the BS needs to determine how many groups and which groups need to be switched to ad hoc mode in order to reduce its bandwidth consumption while satisfying the QoS requirements of the groups. We call this problem the group selection problem, an example of which is given in Fig. 1. In the illustrated network, there are three multicast groups g1, g2, and g3 and their corresponding trees t1, t2, and t3. Group g1 has members {A, D, H}, g2 has members {A, B, C, E}, and g3 has members {A, B, E, G}. Obviously, node A is very likely to be overloaded, and the ad hoc network may not be able to accommodate all three groups. In this case, the BS has to select and accommodate one or two multicast groups (e.g., group g2) in order to maximize its bandwidth reduction without violating the capacity limit of each mobile node. To solve this problem, we have to compute first the amount of resource (i.e., bandwidth) usage for each multicast group and then select a subset of groups based on their bandwidth consumption and the ad hoc network capacity.

IV. ALGORITHM ANALYSIS

Our goal is to maximize the bandwidth savings without using too much resource for a single group, we prefer large groups that require a small amount of bandwidth, i.e., groups with higher utility. The utility metric is used by the dynamic algorithm as a major criteria to select groups in a “greedy” way.

Algorithms 1 and 2 show the dynamic algorithm as groups join and leave the network, respectively. As shown in algorithm 1, when a group g joins the network, we first compute the multicast tree, the required bandwidth vector, and the utility. The admit function is called to verify whether the ad hoc network has enough capacity to accept g. If so, g reserves bandwidth and switches to ad hoc mode. Otherwise, we try to find an appropriate candidate group g_ currently in the ad hoc network and swap it with g. Group g_ should satisfy the following conditions (lines 9 and 10): 1) g_ should have a smaller utility than g, 2) if g_ releases its reserved bandwidth, g should be able to be admitted by the ad hoc network, and 3) if there are more than one such candidate, the final g_ should have the minimum utility. The swap function in line 9 checks the second condition. After the best candidate g_ is found, g_ releases its resource and switches to cellular mode, whereas group g reserves bandwidth and uses ad hoc mode for multicast communication. Similarly, in algorithm 2, when a group g with ad hoc mode leaves, its reserved bandwidth is first released. Then, we try to switch a candidate group from cellular mode to ad hoc mode to reduce the work load at the BS. As shown in line 5, only those groups that pass admission control become candidates, and the one with the maximum utility is finally selected to switch to ad hoc mode.

A. MEMBER DYNAMICS

In the aforementioned dynamic algorithm, we basically consider the scenarios when group members join and leave a group at the same time. In reality, members may join or leave separately. To be more useful, the aforementioned dynamic algorithm needs to be extended to address this member dynamic issue. For example, when a member joins a group currently in ad hoc mode, if there is insufficient capacity to admit this member, we have the following two choices to comply with the capacity constraint. If a candidate group is found, the candidate group is switched to cellular mode to release the bandwidth required by the new member, and the new member can be admitted into ad hoc mode. Otherwise, this group itself is switched to cellular mode. Similarly, when a member leaves a group, we can try to switch a candidate group to ad hoc mode to take advantage of the released bandwidth.

B. NAIVE DYNAMIC ALGORITHM:

Here, we present a naive algorithm as a reference to evaluate the performance of the dynamic algorithm. It works as follows: When a new group joins, if the capacity of the ad hoc network allows, this groups is admitted and the bandwidth for it is reserved. Otherwise, the group is put in cellular mode. When a group in ad hoc mode leaves, its bandwidth is simply released. In essence, this naive approach is a simplified version of the proposed dynamic algorithm: it neither swaps groups in different modes nor differentiates groups based on their utilities.

V. CONCLUSION

In this paper, we have studied the multicast group selection problem in integrated cellular and ad hoc networks. We develop a simple and effective model for computing the bandwidth requirement of a multicast group in wireless ad hoc networks. Then, we formulate the group selection problem as a multidimensional knapsack problem and propose an ILP formulation and a utility-based dynamic algorithm with polynomial-time Complexity. In addition, we examine how the dynamic algorithm can be implemented in a distributed way and discuss node mobility issues. Finally, through extensive simulations, we find that the dynamic algorithm can achieve near-optimal solutions in most scenarios, and it is more appropriate for online systems than the ILP approach

References

Y.-D. Lin and Y.-C. Hsu, “Multihop cellular: A new architecture for wireless communications,” in Proc. IEEE INFOCOM,Tel Aviv, Israel, Mar. 2000, pp. 1273–1282.

G. N. Aggelou and R. Tafazolli, “On the relaying capability of nextgeneration GSM cellular networks,” IEEE Pers.Commun., vol. 8, no. 1,

H.-Y. Hsieh and R. Sivakumar, “Performance comparison of cellular and multi-hop wireless networks: A quantitativestudy,” in Proc. ACM SIGMETRICS, Cambridge, MA, Jun. 2001, pp.

H. Luo, R. Ramjee, P. Sinha, L. Li, and S. Lu, “UCAN: A unified cellular and ad-hoc network architecture,” in Proc. ACMMobiCom, San Diego, CA, Sep. 2003, pp. 353–367. p. 40–47, Feb. 2001.

J. C. Park and S. K. Kasera, “Enhancing cellular multicast performance using ad hoc networks,” in Proc. IEEE WCNC, LasVegas, NV, Mar. 2005, vol. 4, pp. 2175–2181.

H. Luo, R. Ramjee, P. Sinha, L. Li, and S. Lu, “UCAN: A unified cellular and ad-hoc network architecture,” in Proc. ACMMobiCom, San Diego, CA, Sep. 2003.

D. Zhu, M. W. Mutka, and Z. Cen, “QoS aware wireless bandwidth aggregation (QAWBA) by integrating cellular and ad -hoc networks,” in Proc. IEEE QShine, Dallas, TX, Oct. 2004, pp. 156–163.

M. Hauge, A. Hafslund, F. Y. Li, and O. Kure, “Multicast-service distribution on a cellular network assisted by local ad hocnetworks,” in Proc. Med-Hoc-Net, Bodrum, Turkey, Jun. 2004, pp. 68–80.

M. Hauge and O. Kure, “Multicast service availability in a hybrid 3G-cellular and ad hoc network,” in Proc. IWWAN, Oulu,Finland, May 2004, pp. 135–139.

S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L.Wei, “The PIM architecture for wide-area multicastrouting,” IEEE/ACM Trans. Netw., vol. 4, no. 2, pp. 153–162, Apr. 1996.

Ballardie, Core Based Trees (CBT version 2) Multicast Routing: Protocol Specification, RFC 2189, Sep. 1997.

J. Moy, Multicast Routing Extensions To OSPF, RFC 1584, Mar. 1994.

J. Xie, R. Talpade, T. McAuley, and M. Liu, “AMRoute: Ad-Hoc Multicast Routing Protocol,” ACM Mobile Netw. Appl.,vol. 7, no. 6, pp. 429–439, Dec. 2002.

S.-J. Lee, W. Su, and M. Gerla, “On-demand multicast routing protocol in multihop wireless mobile networks,”ACM/Kluwer Mobile Netw. Appl.—Special Issue on Multipoint Communications in Wireless Mobile Networks, vol. 7, no. 6,pp. 441–453.