# Introduction ULTI HOP cellular networks have been proposed as an addition to the conventional single-hop cellular network by joining the fixed cellular infrastructure with the multi hop relaying technology that is frequently used in ad hoc networks. Due to the potential of the multi hop relaying to enhance coverage, ability and flexibility, the multi hop cellular networks have been drawing considerable notice. This approach of augmenting cellular communication with multi hop relaying was also used in the consistency effort to include the multi hop relaying into the thirdgeneration (3G) mobile communication systems [1]. The main advantage of the multi hop relaying arrives from the reduction in the overall path loss among a base station (BS) and a mobile station (MS) [2]. However, the penalty for using multi hop relaying is in the necessitating for extra radio channels. Another advantage of the multi hop relaying is the path diversity increase that can be achieved by picking the mainly favorable multi hop path in the shadowed environment. This diversity increase can increase with the quantity of MSs, as then the quantity of potentially transmit candidates raise and the likelihood of finding a relay with lesser path loss increases as well. In addition, the system's ability can additionally increase by permitting concurrency among the multi hop broadcast. However, such concurrency also raises the interference. So, the overall result is not instantly clear. As we saw above, the performance of the multi hop cellular networks is ruled by different tradeoffs. Thus, to get advantage from the multi hop relaying, the different tradeoffs must be comprehensively studied. However, the study of such tradeoffs in the literature is extremely limited. In scrupulous, the analysis of the transaction caused by the simultaneous transmissions among the interference and the channel reuse efficiency is of very importance. Toumpis and Goldsmith [3] showed that the simultaneous transmission can improve the system capacity of the multi hop cellular networks. However, their outcomes were obtained for a single cell system and in just two cases of complex topology, i.e., a linear topology and a single comprehension of a haphazard topology. Hence, those outcomes are inadequate to demonstrate, in common, the concurrency exchange. Moreover, numerous studies account that it is not easy to improve the capacity of code-division multiple-access (CDMA) systems by utilize of the multi hop relaying [5] - [9]. This is mostly due to the interference increase resulting from the simultaneous transmissions. Such interference may be the most significant factor limiting the network capacity. Hence, the collision of the concurrent transmission must be carefully investigated. The multi hop relaying technology can give a significant flexibility in the design and the operation of the cellular system. On the multi hop cellular system, MS preserve decide to utilize the multi hop relaying instead of the single-hop direct transmission. Such a hybrid operation can be exploited for different purposes; one of which is to mitigate the unfairness in the quality of service (QoS) between the users. In cellular networks, there is a tradeoff difficulty between system throughput and QoS fairness [4]. Since the established signal excellence depends on the user location, it is not easy to give an even QoS over the entire cell service region and to maximize the system throughput at the similar time. On the other hand, the use of multi hop relaying, instead of a direct link, can develop the QoS of the users with poor direct links who are situated near the cell boundary or in a deep shadowed district. Therefore, the equation, as well as scheme throughput in the cellular network can be better through the use of the multi hop relaying. An additional application exploiting the flexibility of the multi hop relaying technology is to mitigate the inefficiency due to the temporal changes in traffic demand in cellular scheme. To optimize the appearance of a cellular scheme, discover the optimum positions of the cell sites is a fundamental problem with interferenceimperfect systems, such as the CDMA category scheme. However, due to the ever-changing traffic demand patterns, optimal placement of cell site is a complex problem. Even if the traffic allocation could be predictable, it would still be complex to optimally plan the radio network, as the fixed cell sites cannot be relocated whenever the traffic allocation changes. Hence, there is a requirement for a self-configuring network, which would be capable of automatically coping with the alteration in traffic distribution. In the multi hop cellular system, the unusual collection of the multi hop path can allow flexible design of the cell site, which is mainly important in the case of non regular traffic allocation. Thus, the multi hop cellular system design can be utilized as a self-configuring network method that can efficiently accommodate the spatial and temporal inconsistency of traffic patterns. Although the multi hop relaying technology has been future as one of the key technologies of the selfconfiguring cellular networks [10], [11], there have been merely little numerical results clarifying how the selfconfiguring feature achieved during the multi hop relaying can develop the system's ability for non consistently distributed traffic case. Although Wu et al. [12] evaluated the capacity of the multi hop system with non consistent traffic, such that when the traffic among adjacent cells is unstable, that paper focused only on the channel borrowing among adjacent cells through multi hop relaying. Moreover, a few features of the multi hop transmit, such as path-loss diminution and path variety, were not measured in their study. Hence, their outcome may not be able to completely explain the behavior of the self-configuring capability of multi hop relaying itself. The problem studied here is to plan a scheduling algorithm for multi-hop relay wireless cellular networks, so that it can correctly position the concurrent transmission scenarios for multi-hop relay links, and the overall network throughput can be improved. # II. # Related work The study of combining relay networks with cellular networks has been going on for quite a while. In [12], an RS is equipped with together WLAN and cellular network interfaces to help with cellular traffic forwarding with WLAN links, aiming to achieve throughput development and load balancing. In [13], the MS is assumed to contain both WLAN and 3G interfaces for traffic communicates. On-demand direction-finding protocols are urbanized to discover relay paths, and incentive schemes are designed to encourage the MS to transmit traffic for other MS. In [14], a clique discovery algorithm is proposed to place the concurrent transmissions in a multi-hop relay cellular system, and relay nodes contain WLAN or WPAN edge in addition to the cellular network interface. The authors believe that the MS is presented all over in the relay path and can serve as a communicate node. Dissimilar from the over loom where a separate relay interface is required, other approaches illustrate below let the relay path share the identical physical interface of the cellular system. In [15], multiple portable stations appearance multi-hop ad hoc network inside cellular system and ad hoc steering is oppressed to extend system throughput. In [16], the MS is used to communicate traffic, while simultaneous transmissions are investigated with an easy network topology, though the source is based on account and hence is not appropriate for practical purpose. In [17], a distributed scheduling algorithm is developed to schedule concurrent transmissions in a cellular relay network aiming at maximizing throughput while avoiding data collision in the communicate links. As a consequence, each mobile knob has to pay for the signaling and bandwidth overhead for the distributed algorithm. The over approaches have one thing in general, which is the ad hoc implementation of a relay network within cellular network architecture. One benefit of the ad hoc implementation is the abundance of ad hoc routing protocols that can provide in communicates routing. Besides, the ad hoc steering protocol consequences in flexibility in the selection of relay routes. However, the ad hoc implementation has a few drawbacks. The first drawback is that ad hoc routing needs every node in the relay network to contribute in the route discovery process that involves distribution, feedback, and onward of routing communication, and this participation need significant modifications of the signaling protocols of wireless cellular system. These momentous modifications in the indication protocols of the BS and the MS make the present cellular network operator reluctant to deploy relay network. Second, the algorithm for discovery ad hoc routing occupies a definite amount of bandwidth from every mobile node, and additional bandwidth expenditure is anticipated in order to continue the routing bench up to date, since nodes are movable in the scheme. Third, the recurrent alter in the routing table decrease the consistency of the data delivery and authority the total complex throughput. Therefore, the ad hoc implementation is unattractive to the network machinist in manufacturing, since the BS, the RS, and the MS all embrace to correct for the architecture changes of the cellular network, and the additional signaling overhead and bandwidth consumption incurred for each MS is significant. Observing the disadvantage of the ad hoc implementation of a relay network, we prefer an approach that involves least network architecture changes and still can enjoy the advantages of multi-hop simultaneous transmissions. A desirable solution must be able to incorporate a relay network into the existing cellular network with unimportant architecture modification and little realization slide, and the new network construction is still handy from the point view of the network operator. When designing a relay network within the cellular network, there are several optional factors, such as whether or not the relay networks accepts the ad hoc implementation as converse over, and whether or not the RS must use the identical cellular spectrum to relay traffic, referred to as in-band relay. Other option include whether or not the MS can provide as the RS and whether or not the scheduling algorithm for simultaneous transmissions should be centralized. How to wisely select among these options to form an adaptive relay network is a difficult task. With such effort is the development of a WiMAX draft standard, 802.16j [20], which is a revision of WiMAX with the aim of incorporating relay network into WiMAX network. This 802.16j draft standard has the subsequent characteristics. The RS in 802.16j is for relay traffic simply, and the forecast algorithm is federal and run in the BS. The RS uses the identical spectrum as the BS and the MS, and no ad hoc steering is suitable in the relay paths. The approach in 802.16j permit WiMAX network to incorporate relay network without sacrificing WiMAX network architecture, and the WiMAX BS is still able to control the RS. One research work [18] study the scheduling algorithm in 802.16j, and it utilizes directional antennas to exploit the space use again of frequency resources in multi-hop relay cellular network under a Manhattan-like environment. Although scheduling algorithm is given to improve network throughput, but how to decide the simultaneous transmissions on the relay network is not addressed. What inspires our research is the work in [19], which suppose a multi-hop wireless mesh backhaul network with in-band communicate. Each RS cumulates the traffic from the close MS. A linear programming model is then developed to evaluate the minimum time to transmit a fixed data load from the BS to every RS above likely multiple hops. Since the transmission time is reduced for the fixed information load, throughput is exploiting. However, it does not in use into reflection the varying line size of each relay station; neither does it relate the frame boundary of cellular network into the transmission. Since wireless cellular networks are mainly frame-based, it is non-trivial to study the scheduling algorithm for multi-hop relay network under frame-based statements. # III. # Network architecture and challenges In a cellular network with frame-based transmissions, base Station attach to relay station and/or mobile station, and every relay station can attach further to additional relay station and/or mobile position. Relay position only ahead traffic to/from mobile station and produce no traffic on its own. Relay station is visible to a mobile station, and mobile station does not engage in routing packets for additional mobile station. Base station, relay station, and mobile station all share the similar spectrum, thus no additional hardware such as a second physical interface is required. Base station needs to meet the downlink real time queue range of its related relay station and this queue information is sent to the base station with uplink bandwidth. The resulting signaling change due to uplink queue status report is unimportant, and the matching uplink bandwidth consumption is neglect able. After gathering relay station queue. Queue information, base station runs the scheduling algorithm to get the downlink scheduling results and broadcasts the outcome to relay station and mobile station. As the input for the scheduling algorithm, simultaneous transmission scenarios need to be resolved in a capable way. When adding a link candidate into a simultaneous transmission scenario, it must be sure that adding this link will not decrease the total throughput of this scenario. However, it is not practical to cross all possible links searching for simultaneous scenarios due to the nonlinear development of links with respect to number of MS and RS. The challenge is due to information that wireless cellular networks are mainly frame-based, and the equivalent scheduling algorithm must take this factor into consideration. In each frame, different simultaneous scenarios must share this frame period. Thus arises the matter of a fair share of time resources between different MS who share one frame, while still achieving the goal of achieving max network throughput. The third challenge is to let the scheduling algorithm regulate to the real time queue size change in RS. Implementation of Scheduling Algorithm under Linear Programming: Volume XII Issue XIII Version I The number of links grows non-linearly with the number of nodes in the network; it is impractical to use a comprehensive algorithm to search for all probable scenarios. We use a linear programming model confirmed to compute the transmission schedules for all simultaneous transmission scenarios, aiming at maximizing the throughput in each frame. Here we consider the transmission schedules those subjective by the transitive relations between BS and RS. # b) Structure of Greedy effect In this Greedy Approach we apply the back force flow control mechanism. This mechanism states that in order to maximize the end to-end throughput in multi hop wireless network, the chosen simultaneous transmissions must be able to get the most out of the object function. We use a greedy algorithm to get a set of simultaneous transmission scenarios, with the back force flow control mechanism included in the greedy algorithm. Which are defined as: IV. # Implementation methodology and results The Queue aware scheduling under transitive connection considerations has been implemented using mxml and action script. The accomplishment is based on multi-hop relay based wireless cellular network routing functions that are added. In additional to building QoS routes, the protocol also establishes a best schedule plan when it learns such obligation. The best-effort scheduling is used to enhance the throughput. A distributed protocol which dynamically generates and updates broadcast schedules between the nodes has been used. Assumed transmission rate is 1 Mbps. The proposed model detects all simultaneous transmissions, and responds by invoking scheduling behavior as suitable. The relay station queues that are transitively associated with BS also be measured to end the Queue capacity of the relay station that relies on the middle between BS and transitive relay station. We apply greedy search techniques to recognize simultaneous relations of the replication. And finally end the scheduling strategy using the linear program technique proposed. These greedy searches and linear approach we implemented using action script. The linear approach considers the 6 different constraints explored above. Volume XII Issue XIII Version I Where 'i' is RS index and r is transitive RS index and tc is transitively associated relay station count. 's' and 'w' stands for node i's upstream and downstream node, correspondingly; 3. ( , ) ( , ) ( ) m ij ij k m x k t w k t T t ? × ? 4. # Conclusion and future work We have offered a Transitive relation aware scheduling algorithm for multi-hop relay wireless cellular networks. Through our analysis, we dispute that following a centralized approach for building cellular relay networks best reflects the interest of the cellular networks. This central approach implies that relay stations and mobile stations do not form ad hoc networks and they are under the control of bottom station. Another selection of building communicates cellular networks we follow include using in-band spectrum of relay stations, not permit mobile stations to provide as relay position, and relate centralized preparation algorithm. An essential scheduling algorithm is developed and base stations will run this preparation ![We there a linear programming model to implement the scheduling algorithm for wireless cellular multi hop relay network. The main advantages of this algorithm are Constraint 1: Derives the throughput for Mobile Station node in the border, informative the simultaneous broadcast nature of the multi hops cellular networks.Constraint 2: Indicates the queue consciousness of the proposed preparation algorithm by monitoring Constraint 3: The dynamic RS queue status, and this queue consciousness are not addressed by the associated work, the capacity restraint of a link in situation SK. Constraint 4: Applies Shannon's Theorem to compute the upper bound of link data rate with the thought of the interference caused by simultaneous transmissions.Constraint 5: States the time restraint of all simultaneous scenarios in a frame, suggestive of the frame-based characteristic of this approach. Constraint 6: Transitive relative among BS and RS will be careful and this restraint power the real delay calculated at RS that connected directly to the BS. Block Diagram:](image-2.png "") 1![Figure 1 : Scheduling Algorithm under Linear Programming a) Detection of Concurrent Transmission Scenarios](image-3.png "Figure 1 :") 4![arrangement in cellular relay networks under transitive relation considerations. Under transitive situation the calculation of relay stations r; 5: RS node i's queue status set of simultaneous transmission scenarios Sk, 1 ? k ? K; 8: power used from node i to j, Pij ; 9: distance between node I to j, dij ; scheduled packets transmitted from node i to j in Sk at frame t, which are destined for MS node m; 2: Tk(t), scheduled time portion for scenario Sk Constraints 1.](image-4.png "4 :,") ![MS node m's upstream node' index; 2.](image-5.png "") 12![Fig. 1 : Cellular network with Transitive relay topology for simulation](image-6.png "Fig. 1 :Fig. 2 :") © 2012 Global Journals Inc. (US)Global Journal of Computer Science and Technology ## Year algorithm. In the preparation algorithm, initial a locate of simultaneous transmission scenarios is the result and then it is used as input for a linear programming model that decide the transmission schedules for the multi-hop communicate network. The linear encoding model aims at exploiting the overall throughput of the all the mobile stations, while taking into attention the frame-based environment of cellular networks and the dynamic queue modify in the relay position The skin of frame-based and queue-awareness of the preparation algorithm are the single assistance that have not been addressed by earlier work. Simulations calculate performance metrics such as throughput and equality of the proposed scheduling algorithm. Two extra scheduling algorithms are evaluated with our approach via simulations. One is scheduled for straight transmission only, and the other is scheduled with no buffer in the communicate nodes. The effectiveness of our loom is authenticated by the replication results. * Opportunity driven multiple access ver. 1.0.0 3GPP Dec. 1999 * UMTS; UTRA; Concept evaluation (UMTS 30.06) TR 101 146 Dec. 1997 ETSI, ver. 3.0.0 * Capacity regions for wireless ad hoc networks SToumpis AGoldsmith Proc. IEEE ICC IEEE ICCNew York 2002. Apr. 2002 * QoS and fairness for CDMA packer data MAiry KRohani Proc. IEEE Vehicular Technology Conf. 2000 Spring IEEE Vehicular Technology Conf. 2000 SpringTokyo, Japan May 2000 * Area coverage and capacity enhancement by multi hop connection of CDMA cellular network AFujiwara Proc. IEEE Vehicular Technology Conf. 2002 Fall IEEE Vehicular Technology Conf. 2002 FallVancouver, BC, Canada Sept. 2002 * Performance analysis of multi hop packet CDMA cellular networks ANZadeh BJabbari Proc. IEEE GLOBECOM IEEE GLOBECOMSan Antonio, TX 2001. Nov. 2001 * Performance analysis of intelligent relaying in UTRA TDD TJHarrold ARNix Proc. IEEE Vehicular Technology Conf. 2002 Fall IEEE Vehicular Technology Conf. 2002 FallVancouver, BC, Canada Sept. 2002 * Coveragecapacity analysis of opportunity driven multiple access (ODMA) in UTRA TDD TRouse SMclaughlin HHaas Proc. IEE 3G Mobile Communication Technologies IEE 3G Mobile Communication Technologies Mar. 2001 * Capacity and power investigation of opportunity driven multiple access (ODMA) networks in TDDCDMA based systems TRouse IBand SMclaughlin Proc. IEEE ICC IEEE ICCNew York 2002. Apr. 2002 * Self-organization in future mobile communications AGSpilling ARNix MABeach TJHarrold Electron. Commun. Eng. J June 2000 * Broad-band wireless access and future communication networks RBecher MDillinger MHaardt Mohr Proc. IEEE IEEE Jan. 2001 89 * Integrated Cellular and Ad-hoc Relay Systems: iCAR HWu CQiao SDe OTonguz IEEE J. Sel. Areas Commun 19 10 Oct. 2001 * The Design and Evaluation of Unified Cellular and Ad Hoc Networks HLuo XMeng RRamjee PSinha LLi IEEE Trans. Mobile Comp 6 9 Jun. 2007 * On Downlink Capacity of Cellular Data Networks with WLAN/WPAN Relays BRadunovic AProutiere Proc. 3rd IEEE RAWNET 3rd IEEE RAWNET 2007 * Multi hop Cellular: A New Architecture for Wireless Communication YDLin YCHsu Proc. IEEE INFOCOM IEEE INFOCOM 2000 * On the Throughput Enhancement of the Downstream Channel in Cellular Radio Networks Through Multi hop Relaying JCho ZJHass IEEE J. Sel. Areas Commun 22 7 Sept. 2004 * A Novel Distributed Scheduling Alorithm for Downlink Relay Networks Y.-NLee J.-CChen Y.-CWang J.-TChen IEEE Trans. Wireless Commun 6 6 Jun. 2007 * Resource Schduling with Directional Antennas for Multi hop Relay Networks in Manhattan-linke Environment S.-JLin WHSheen I.-KFu C.-CHuang Proc. IEEE Mobile WiMAX Symp IEEE Mobile WiMAX Symp 2007 * Throughput-Range Tradeoff of Wireless Mesh Backhaul Networks HViswanathan SMukherjee IEEE J. Sel. Areas Commun 24 3 Mar. 2006 * Throughput-Range Tradeoff of Wireless Mesh Backhaul Networks HViswanathan SMukherjee IEEE J. Sel. Areas Commun 24 3 Mar. 2006