Analysis Of Resource Allocation Schemes In Wireless Relay Networks

Analysis Of Resource Allocation Schemes In Wireless Relay Networks

J.Deepa,

Assistant Professor, CSE, Panimalar Institute of Technology, Chennai, Tamilnadu, India.

Abstract-In this paper, the multicast routing problem in wireless relay networks is considered. We discuss the resource allocation problem in IEEE 802.16j WIMAX Networks. The relay stations are used to improve the transmission quality in WIMAX networks. Most existing approaches try to reduce the energy consumption of a multicast tree. In contrast, the maximization problem to increase the number of recipients within the given resource is addressed. In recent years various resource allocation schemes for maximization problem is discussed. To have a comprehensive understanding of resource allocation schemes, a comparison of these schemes is discussed detail in this paper.

1. INTRODUCTION

   In the last few years there has been significant growth in the area of wireless communication. IEEE 802.16 (WiMAX) [1] is the network which is designed for providing high speed wide area broadband wireless access. It consists of a base station (BS) and multiple subscriber station (SSs).BS transmits data to the SSs through broadcast channel. The SSs are linked to BS through multiple access channels. IEEE 802.16 standard utilize new nodes called relay stations (RSs). The RSs relay data between the BS and the SSs in upward and downward direction. WiMAX is an emerging wireless technology for creating multi-hop Mesh network. Future generation networks will be characterized by variable and high data rates, Quality of Services (QoS), seamless mobility both within a network and between networks of different technologies and service providers. A technology is developed to accomplish these necessities is regular by IEEE, is 802.16, also called as WiMAX (Worldwide Interoperability for Microwave Access). WiMAX supports Long range connectivity, High data rates, High security, Low power utilization and Excellent Quality of Services and squat deployment costs to a wireless access technology on a metropolitan level. Due to broadcast nature of the wireless medium, multicasting do not need more resources compared to unicasting. Multicast is used to transmit the data from the source to multiple receivers. It is useful because it allows the construction of truly distributed application, and provides important performance optimizations over unicast transmission. There are a number of existing applications for real-time audio and video conferencing which can make good use of a multicast service when it is available. Due to heterogeneous channel conditions, each recipient may experience different bit error rates and the amount of resources required may vary for

   J.Sutha,

   Professor & Head, CSE, Sethu Institute of Technology,

   Virudhunagar, Tamilnadu, India

   each recipient. Most modern technologies utilize adaptive modulation and coding scheme to suit the channel conditions. When there are more recipients to serve, the sender tends to consume more resources. Since the wireless medium has limited resource, it is not always possible to provide multicast services for all the subscriber stations. Within the resource budget of a multicast service, resource utilization should be done to serve as many recipients (i.e., SSs) as possible. WiMAX provides better platform for Multicast. When a network only consists of a BS and SSs, this maximization can be done by allocating the entire resource budget to the BS. However, if RSs are considered, this problem becomes much difficult because resource should be allocated among the BS and RSs.

   Figure 1.1: WiMAX Network Architecture

   As in Figure 1.1, WiMAX network architecture consists of Base Stations, Subscriber Stations and user terminals. WiMAX has a point-to-point range of 30 miles with a throughput of 72 Mbps. It has a non-line-of-sight range of 4 miles in a point-to-multipoint distribution, and can distribute nearly any bandwidth to almost any number of subscribers, according to the subscriber density and network architecture.

2. RELATED WORK

   In [2],the resource allocation for the OFDMA based two- hop relay network was proposed, which consists of a multiple source nodes, multiple relay nodes and a single destination node. It ensures fairness in orthogonal frequency division multiple access relay networks. Also in

   [2], the resource allocation for the OFDMA based two-hop relay network which consists of a single base station, dedicated fixed relay stations and subscriber stations was studied. But these works focus on unicast transmission in relay networks.

   In [3], a reliable multicast scheme based on the Code Division Multiple Access (CDMA) codes was proposed. The packet error rate and required uplink resources were compared with the unicast ARQ feedback messages against various channel environments. By this approach lot of resources can be saved.

   In [4], proposed a decentralized scheme, which forms a broadcast topology that can reduce the transmission power and satisfy the connectivity constraint. Although this type of scheme can effectively be implemented in ad hoc network, it may not be suitable for an infrastructure based wireless relay networks.

   In [5],a multiplex-multicast scheme is presented that resolves the transmission bottleneck between IEEE 802.16 and IEEE 802.11.General resource allocations of multicast over wireless networks such as MEB and MEM are also discussed. In MEB, each node is allowed to forward broadcast transmissions to other nodes. The objective is to minimize the total energy required for broadcasting a stream to a given set of subscriber nodes. To further reduce the total energy requirement, a more general problem called MEM (Minimum-Energy Multicast) even allows other nodes that are not subscribers to relay data.

   The energy consumption of the multicast tree is studied in the literatures [e.g.6, 7, and 8]. These approaches tried to minimize the energy consumption. Though these problems may appear similar to our problem initially, they are substantially different. First, MEB and MEM try to minimize the resources required to serve all subscribers, whereas our goal is to maximize the number of recipients with a given budget. Second, MEM and MEB allow each recipient node to forward data, but only RSs can relay data in our problem. Although the assumptions of MEM and MEB may be applied in adhoc networks and sensor networks, it does not fit the reality of relay networks which we aim to deal with.

   One of the few schemes developed for multicast resource allocation over relay networks is discussed in [9]. The scheme considers two classes of nodes: relay nodes and receiving nodes. By finding the minimum spanning tree, the total energy required to conduct multicast can be minimized. Although the scheme is suitable for wireless relay networks, it only decides whether or not to activate a relay node during the multicast. The transmitting power of each relay node is assumed to be pre-determined and cannot be adjusted dynamically, thus limiting the systems flexibility and performance. Moreover, instead of trying to maximize the number of recipients, the goal of this approach is to minimize the total energy requirement of the broadcast tree.

   In [12], Multicast subscriber selection scheme was proposed to solve the maximization problem based on the given resource budget and the channel quality conditions. The results proved that the existing unicast approach was inefficient under different budget and the channel conditions.

   In [13], a resource-allocation scheme is proposed for multicast service in dowlink transmission for IEEE 802.16j WiMAX relay networks. Dynamic station selection (DSS) scheme is used to solve the maximization problem based on the proposed auxiliary graph. DSS more efficiently utilizes resources as the node density increases, resulting in more efficient resource allocation.

3. SYSTEM MODEL

   The system is modeled as follows. Let RS0 be the BS, and let 1 y Y, RSy denote the RSs, where Y is the number of RSs in a WiMAX network. Next, we mark each SS by SSn

   , 1 n N , where N is the number of SSs requesting the multicast stream. In WiMAX, the resource that can be distributed to different transmissions is the time slots in a time division duplexing super frame. The budget of a multicast program means its maximal usable resource. Let the bandwidth of the multicast stream be M, and the interval between each frame be T; then, the total amount of data transmitted in the stream of a frame is MT. We denote the data rate of the burst profile used between RSy and SSn by bn,y. Similarly, we use ry to represent the resource required for RSy to receive the stream from the BS. Each SS accesses the BS either directly or through an RS, and its route to the BS can be predetermined by any existing path- selection scheme. The routing of each SS is assumed to be decided previously, because it is not possible that the whole multicast tree can dynamically be formed and adjusted as the channel condition of any recipient changes. We define the resource requirement of a receiver as the total amount of resource required to receive the stream. If an SS needs an RS to relay the stream, the resource requirement includes the resource for transmitting from the BS to the RS and from the RS to the SS.

   Fig.4.3 Nodes in a WiMAX relay network

   To denote the sender of each group, let RS0 be the sender of group 0 (i.e., the BS), whereas RSm denotes the mth RS

   and the sender for group m, m > 0. Since the RSs have to receive the multicast stream from the BS before relaying it, we also include all RSs in group 0.

4. RESOURCE ALLOCATION SCHEMES FOR MULTICAST

   1. Multicast Subscriber Selection (MSS): Given a resource budget and the channel quality (i.e., the minimal resource requirement) of each link, the MSS allocates the resource to the BS and the RSs to maximize the total number of SSs that receive the stream successfully. The input for resource requirement of SSs, RSs and total resource budget are given and MSS computes a heuristic resource allocation for SSs and RSs. MSS searches for an allocation with an incrementally better performance to serve more recipients in each round.

      The algorithm is as follows.

      Step1: All the SSs are placed in a queue q and sorted by the value of rn,0 in the decreasing order.

      Step 2: The entire budget is allocated to the BS.

      Step 3: The allocation having better performance is stored in each round.

      Step 4: All the SSs that can receive from the BS directly are copied to another queue .

      Step 5: The resource is allocated to the SSs which are popped from the queue. The resource released by the BS is given to each RS in and temporary allocation is done.

      Fig 4.1 SSs, RSs and the resource requirement of the links Step 6: Temporary allocation and Maximal performance \

      allocation are compared and the better performance is considered for the next round.

      Step 7: The procedure is repeated until no more SSs can be popped.

      Since MSS begins the allocation process by assigning the whole budget to the BS and then finds the maximum performance in each loop.

      Fig. 4.2 The Pseudo code of MSS

      4.2. Dynamic Static Selection (DSS):

      Given a fixed topology, the time-variant channel conditions can still be reflected by periodically executing the scheme. The objective of DSS is to maximize the total number of served SSs. Since SSs may be served by different senders (i.e., the BS or the RSs), they are classified into different groups according to their senders. Let the SSs directly served by the BS be classified as group 0 and the SSs that receive data via the mth RS be placed in group m, where m

      > 0.

      Fig.4.3 Auxiliary Graph of a wireless relay network

      To denote the sender of each group, let RS0 be the sender of group 0 (i.e., the BS), whereas RSm denotes the mth RS and the sender for group m, m > 0. Since the RSs have to receive the multicast stream from the BS before relaying it, we also include all RSs in group 0.

      A wireless relay network can be represented as an auxiliary tree. All elements of group 0 (i.e., the RSs and SSs directly served by the BS) are placed in the main branch, and the elements of groupm > 0 are placed in a side branch connected to the main branch. With this placement, for each node, the total distance (i.e., the sum of weights of edges) to the root is equal to the number of resource that it requires.

      Given such a graph, we can easily determine the additional resource required to serve a node by finding the distance to the nearest served node. The MRM involves finding a spanning tree rooted at the BS that maximizes the number of SSs covered, subject to the constraint that the total length of the tree is not greater than the resource budget.

      The algorithm is as follows.

      Step 1: For a given network structure, auxiliary tree is constructed.

      Step 2: DSS starts allocating resources from the root, by considering nodes in group 0 one by one.

      Fig 4.4 The Pseudo code of DSS

      Step 3: Once the RSs are included and their members become available to be served, DSS compares the allocation utility factor among the unserved available nodes and chooses the node with the maximal one.

      Step 4: DSS includes one more node in this group and subtracts the required resource from the residual resource.

      Step 5: This process is repeated until all nodes have been served or until the residual resource is insufficient to serve any more nodes.

      4.3 Base Station Approach:

      Our problem is to maximize the number of recipients within the given resource budget and the channel conditions. Each BS provides SSs with a broadcast channel in the downlink direction. The budget of a stream can be simply given to the BS because it is the only transmitting node.

      Fig 4.5 Resource budget required by each link.

      Figure 4.5 shows a network composed by two RSs and two SSs. The number of each link in this figure refers to the required resource.

      In the conventional approach, each SSs route consuming the least resources is determined independently. Since the two RSs receive the stream from the BS through a multicast channel, and the two SSs receive it from the RSs separately, the total amount of resources consumed by this method is 3+3+1=7.

      Fig 4.6 Resource allocation using BS approach.

      The resource requirement can be further reduced to 5 if the two SSs receive the stream from the BS directly as shown in figure 4.6. Given a certain amount of the budget, say 5, both SSs can be served if the BS scheme is used. But only one SS can receive the stream if the conventional method is used. In maximization problem of WiMAX, Multicasting focuses the whole topology of the network.

5. PERFORMANCE EVALUATION

   1. Simulation Settings:

      No Of Served SSs

      The simulation scenario is set as follows. On a two- dimensional plane, the coordinate of the BS is set as (0,0).

      120

      100

      80

      60

      40

      DRA

      MSS BS

      20

      0

      10

      20

      30

      40

      50

      60

      70

      Resource Budgets in Percentage

      Fig 5.1 Available Resources vs. SSs

      In each run, the positions of all SSs are randomly distributed in a circular area whose center and radius are (0,0) and 100 respectively. Unlike SSs, which are usually distributed randomly, the RSs are deployed by the system carrier in order to maximize the relay effect. Hence, all the RSs are placed randomly in circular region whse radius ranges from 40 to 60 such that each RS is located between the BS and some SSs. Having acquired the channel conditions we compare the allocations of three schemes, namely: MSS,BS and DSS

      5.2. Simulation Results:

      In the first simulation, we compare the performance of the allocations of the two schemes under different resource budgets. The value of N and Y are fixed at 100 and 5 respectively, where N is the total number of subscriber stations and Y is the number of relay stations. The resource budget is varied in the range 0 to 1,000,000. The result is shown in Fig. 5.1. We observe several phenomena in the results. For all allocations, as the budget increases more SSs are served. BS approach when compared to DSS provides better performance .But MSS achieves a better performance than DSS method and Base station approach. With the use of relay stations, Mss effectively utilized the resources and served more subscriber stations

6. CONCLUSION

   In this paper, we study the resource allocation problem of multicast over WiMAX networks. We demonstrate that existing routing approaches do not perform well when conducting multicast services. To address this issue, we have studied and compared three resource allocation schemes namely DSS,BS and MSS. Through simulations, we show that MSS scheme can utilize RSs effectively and outperform both the BS and the DSS scheme. Since this common problem is modeled in very proposed scheme can be adapted to different kinds of wireless relay networks.

7. REFERENCES

1. Baseline Document for Draft Standard for Local and Metropolitan Area networks, IEEE Std. 802.16j- 06/026r2, 2007.

2. G. Li and H. Liu, Resource allocation for OFDMA relay networks with fairness constraints, IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp. 20612069, Nov. 2006.

3. H. Lee and D.-H. Cho, Reliable multicast services using CDMA codes in IEEE 802.16 OFDMA system, in Proc. IEEE VTC 2005-Spring, 2005.

4. K. Miyao, H. Nakayama, N. Ansari, and N. Kato, LTRT: An efficient and reliable topology control

   algorithm for ad-hoc networks, IEEE Trans. Wireless Commun., vol. 8, no. 12, pp. 60506058, Dec. 2009.

5. J.E. Wieselthier, G. D. Nguyen, et al, On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks, in Proceedings of IEEE INFOCOM 2000, March 2000, pp.585-594.

6. O. Egecioglu and T.Gonzalez, Minimum-energy broadcast in simple graphs with limited node power, in Proceedings of IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2001), pp.334-338, Anaheim, CA, August 2001.

7. D. Li, X. Jia and H. Liu, Energy Efficient Broadcast Routing in Static Ad HocWireless Networks, IEEE Transactions on Mobile Computing, Vol.3, No. 2, 2004.

8. S. Guo and O. Yang, A dynamic multicast tree reconstruction algorithm for minimum-energy multicasting in wireless ad hoc networks, in Proceedings of IEEE International Conference on Performance, Computing, and Communications, 2004, pp.634-642.

9. M. K. Awad and X. Shen, OFDMA based two-hop cooperative relay networks resource allocation, in Proc. IEEE ICC, 2008, pp. 44144418.

10. "Constructing minimum-energy broadcast trees in wireless ad hoc networks," in Proceedings of the 3rd ACM International Symposium on Mobile AdhocNetworking & Computing, 2002, pp.112-122.

11. M. R Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP- Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP9, pp.247.

12. Wen-Hsing kuo and Jeng-Farn Lee, Multicast Routing Scheme for Recipient Maximization in Wireless Relay Networks, IEEE Trans. vehicular technology on. vol. 59, no. 8, pp. 4002-4011, Oct 2010.

13. Wen-Hsing kuo and Jeng-Farn Lee, Multicast Recipient Maximization in IEEE 802.16j Wimax Relay Networks, IEEE Trans.vehicular technology on, vol. 59, no. 1, pp. 335-343, Jan 2010.

14. T. S. Rappaport, Wireless Communications: Principles and Practices. 0nglewood Cliffs, NJ: Prentice-Hall,1996.