Patent information
IP India · live recordAbstract
Methodologies for scheduling transmissions in Orthogonal Frequency Division Multiple Communication (OFDMA) based relay networks and Worldwide Interoperability for Microwave Communication (WiMAX) relay networks are disclosed. The network routing topology comprises of a base station, intermediate relay nodes and wireless communication device associated to base stations/relay nodes. The transmission scheduler for OFDMA based relay networks use a GenArgMax method for scheduling transmission. The transmission scheduling for WiMAX relay networks is performed by a FastHeuristic 16j scheduling procedure and a TreeTraversal scheduling process. The methodologies eliminate multiple constraints induced by transmission scheduling in WiMAX relay networks.
Applicants
1Inventors
2Specification
Show full textCollapse
1 of 18 FORM 2 The Patent Act 1970 (39 of 1970) & The Patent Rules, 2005 COMPLETE SPECIFICATION (SEE SECTION 10 AND RULE 13) TITLE OF THE INVENTION “Transmission Scheduling in Relay Networks” Name Nationality Address Alcatel Lucent France 54 rue de la Boétie, 75008 Paris, France The following specification particularly describes and ascertains the nature of this invention and the manner in which it is to be performed:- 2 of 18 5 BACKGROUND Technical Field 1. The embodiments herein generally relate to wireless communications, and, more particularly, to scheduling in relay networks. 10 Description of the Related Art 2. Wireless communication systems generally use a network of base stations to communicate with wireless devices for providing services in the systems. OFDMA based communication systems are based on the orthogonality of frequencies of multiple subcarriers. But in wireless communication networks, the network configuration has low 15 flexibility because of the fixed base station and also suffers from shadowing arising from blockage by buildings and other obstructions between transmission/reception antennas. In an Orthogonal Frequency Division Multiple Communication (OFDMA) relay network, such as, for example, a network based on the Institute of Electrical and Electronics Engineers (IEEE) 802.16 standard, relay nodes can be employed for providing enhanced 20 transmission capabilities by acting as intermediaries between wireless communication devices operating in the network and the base station. 3. Relay networks provide an inexpensive means to overcome the potential deployment issues generally detected in non-relay based wireless communication networks such as filling coverage holes or dead-spots and extending range of a network 25 cell in the sub-urban areas. Relay network calls can be used for novel and intelligent scheduling of data transmissions. However, scheduling transmissions in relay networks is challenging as compared to traditional wireless networks. 4. A relay network needs to choose from a large count of alternatives for scheduling transmissions. The number of alternatives in a relay network is exponentially 30 more than that in non-relay based network because of multi-hop topology. A relay network has a multi-hop topology with each hop consisting of several Orthogonal Frequency Division Multiple Communication (OFDMA) sub-channels and each subchannel having different sustainable rate over each multi-hop link. Also, computing of transmission-schedules by using a brute-force technique for evaluating all the possible 35 options is impractical, since scheduling decisions have to be made every frame, the 3 of 18 duration of which is typically of the 5 order of a few milliseconds. 5. There exist various scheduling constraints in relay networks, for instance, synchronization in a multi-hop topology and use of a single transceiver at the relays. This means the schedule should ensure that a relay is not transmitting and receiving concurrently. Further, data from base-station to wireless communication device (or vice 10 versa) in a scheduling frame should reach its destination within the same frame since the relays are meant to act in a transparent mode, which give rise to flow conservation constraints. 6. Usually, in the IEEE 802.16 based wireless technology WiMAX (Worldwide Interoperability for Microwave Access) sub-channel allocation for a 15 WiMAX relay network, each wireless communication device is allocated a sub-channel which is used by all the intermediate links of the relay network during the entire scheduling-frame. However, allocating sub-channels on a per-device basis for the entire path requires the relays to be equipped with multiple-radios per relay node. This does not comply with the IEEE 802.16j standard requirement. 20 7. Wireless communication devices providing multi-hop relaying with multiuser scheduling have been implemented to overcome the scheduling constraints in relay networks. However, the method does not support OFDMA (WiMAX, LTE etc) based networks and hence cannot exploit frequency-selectivity of wireless channels. Further, the solution does not explicitly follow the requirements of IEEE 802.16j 25 standards and also may lead to different throughput for different wireless communication devices. SUMMARY 8. In view of the foregoing, one embodiment herein provides a method of scheduling transmissions for Orthogonal Frequency Division Multiple Communication 30 (OFDMA) based relay networks. The method comprises of segmenting a scheduling frame to number of network hops divisions, selecting wireless communication devices with high r(Im, C)/Rm ratio of plurality of wireless communication devices connected to a relay node for scheduling and computing highly eligible wireless communication device from selected communication devices with high r(Im,C)/Rm ratio. Rm is the 35 average data rate received by wireless communication devices till the previous 4 of 18 scheduling frame and r(Im, C) is the data rate over sub-channel C 5 of the link lm between wireless communication device m and the relay node in a scheduling frame. The objective function F(d) is defined as, summation over all mobiles m of the quantity (total bits delivered to mobile m in the current scheduling frame)/Rm The method of computing highly eligible wireless communication devices further comprises of obtaining number of 10 slots required to increase objective function F(d) by at least one unit for the eligible wireless communication device, allocating the slots to the wireless communication device requiring least number of the slots, and updating the slots available for sub-channels and segment. The slots in the scheduling frame are segmented to locate links in path from base station to the wireless communication device in different segments. The sub15 channels are assigned in different the links with priority to the wireless communication devices using less time-slots for at least unit increment in the objective function F(d). 9. Another embodiment herein discloses a method of scheduling transmission for WiMAX relay networks using a FastHeuristic16j procedure. The method comprises of calculating total transmission rate Cu of relay node u to central node, 20 calculating effective capacity Cu of a base station to corresponding wireless communication device, calculating contribution Uu, per-time slot increase in objective function F(d) by wireless communication device associated to the relay node u, computing Chu for corresponding the relay node and the base-station, computing Uu associated to the relay node and the base station, choosing the relay node and the base 25 station with Uu.Chu/Cu value maximum, allocating sub-channel C to wireless communication device with r(lm,C)/Rm value maximum and allocating slots to an intermediate relay node in the path from the relay node to the base-station. The Chu can be computed by 1/(1/Cu + {V:V in path from u to base station}1/Cv), where v is an intermediate relay node. 30 10. Yet another Embodiment herein discloses a method of scheduling transmission for WiMAX relay networks using a TreeTraversal procedure. The method comprises of computing iu and cu for relay-nodes, computing the iu and the cu for intermediate relay-nodes using the iu and cu for the relay nodes by traversing the routing topology in a bottom-up manner and computing time allocations by traversing the routing 35 topology in a top-down manner, where cu is total data per time slot to be transmitted to 5 of 18 the wireless communication device in the subtree Tu for incrementing 5 the objective function F(d) by iu per time slot.. The iu may be calculated for all time slots allocated to the subtree Tu by computing increase in an objective function F(d), wherein data transmitted to wireless communication devices in the Tu increases the objective function F(d). 10 11. One embodiment herein discloses a system for scheduling transmissions for Orthogonal Frequency Division Multiple Communication (OFDMA) based relay networks. The system comprises of at least one means adapted for segmenting a scheduling frame to number of network hops divisions, selecting wireless communication devices with high r(Im, C)/Rm ratio of plurality of wireless communication devices 15 connected to a relay node for scheduling and computing highly eligible wireless communication device from selected communication devices with high r(Im,C)/Rm ratio. Rm is the average data rate received by wireless communication devices and r(Im, C) is the data rate over the link between wireless communication device and the relay node in a scheduling frame. The method of computing highly eligible wireless communication 20 devices further comprises of obtaining number of slots required to increase objective function F(d) by at least one unit for the eligible wireless communication device, allocating the slots to the wireless communication device requiring least number of the slots, and updating the slots available for sub-channels and segment. 12. Another embodiment herein discloses a system for scheduling 25 transmission for WiMAX relay networks using a FastHeuristic16j procedure. The system comprises at least one means adapted for calculating total transmission rate Cu of relay node u to central node, calculating effective capacity Cu of a base station to corresponding wireless communication device, calculating contribution Uu per-time slot increase in objective function F(d) by wireless communication device associated to the 30 relay node u, computing Chu for corresponding the relay node and the base-station, computing Uu associated to the relay node and the base station, choosing the relay node and the base station with Uu. Chu/ Cu value maximum, allocating sub-channel C to wireless communication device with r(Im,C)/Rm value maximum and allocating slots to an intermediate relay node in the path from the relay node to the base-station. The Chu 35 can be computed by 1/(1/ Cu + {V:V in path from u to base station}1/Cv), where v is 6 of 18 5 an intermediate relay node. 13. Yet another embodiment herein discloses a system for scheduling transmission for WiMAX relay networks using a TreeTraversal procedure. The system comprises at least one means adapted for computing iu and cu for relay-nodes, computing the iu and the cu for intermediate relay-nodes using the iu and cu for the relay nodes by 10 traversing the routing topology in a bottom-up manner and computing time allocations by traversing the routing topology in a top-down manner. The iu may be calculated for all time slots allocated to the subtree Tu by computing increase in an objective function F(d), wherein data transmitted to wireless communication devices in the Tu increases the objective function F(d). cu is total data per time slot to be transmitted to the wireless 15 communication device in the subtree Tu for incrementing the objective function F(d) by iu per time slot. 14. These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings. 20 BRIEF DESCRIPTION OF THE DRAWINGS 15. The embodiments herein will be best understood from the following detailed description with reference to the drawings, in which: 16. FIG. 1 is a block diagram depicting a relay network, according to an 25 embodiment herein; 17. FIG. 2 is a block diagram illustrating the components of a base station, according to an embodiment herein; 18. FIG. 3 illustrates a flowchart depicting a method of transmission scheduling for OFDMA based relay networks, according to an embodiment herein; 30 19. FIG. 4 illustrates a flowchart depicting a method of transmission scheduling for WiMAX relay networks using FastHeuristic16j scheduler, according to an embodiment herein; and 20. FIG. 5 illustrates a flowchart depicting a method of transmission scheduling for Wi-MAX relay networks using TreeTraversal scheduler, according to an 35 embodiment herein. 7 of 18 5 DETAILED DESCRIPTION OF EMBODIMENTS 21. The embodiments herein and the various features and advantages of the embodiments are explained in more detail with reference to the non-limiting 10 embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of the ways in which the embodiments herein may be practiced and to further enable those of skill in the 15 art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein. 22. The embodiments herein achieve methodologies for scheduling transmissions in OFDMA based relay networks and WiMAX based relay networks. The scheduling methodologies exploit the frequency and time diversity of wireless channels 20 and also compute the schedule with 5ms duration of a WiMAX scheduling frame. Referring now to the drawings, and more particularly to FIGS. 1 through 5, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments. 23. The embodiments herein disclose methods for scheduling in OFDMA 25 based relay networks and WiMAX based relay networks overcoming various constraints. A relay network topology comprises of a base-station, relay nodes and wireless communication device associated with the base station or relay node. In an embodiment, a transmission scheduler for generic OFDMA based relay networks uses a process known as the GenArgMax process. The GenArgMax process comprises segmenting the 30 scheduling frame, selecting eligible wireless communication device, computing most eligible wireless communication device and further repeating the steps until a time-slot is available for all the segments. In other embodiments, transmission scheduling for WiMAX relay networks are performed using FastHeuristic16j scheduling and Tree Traversal scheduling methods. 35 24. FIG. 1 is a block diagram depicting a relay network, according to an 8 of 18 embodiment herein. The network topology includes a base station 5 101, a plurality of relay nodes 102 and a plurality of wireless communication devices m 103 associated with one of the relay nodes 102 or base station 101. The base station 101 is a wireless communication station installed at a fixed location and used to communicate to a wireless telephone/Internet access system. The base stations 101 emit radio signals that carry data 10 content to transmit information to wireless devices via downlink. The relay nodes 102 functions as an intermediate point between wireless communication device m 103 and related servicing base stations 101 for providing enhanced transmission capabilities. The relay node 102 includes a detector for receiving data from the base stations 101 or other relay nodes 102 within the network to allow the relay node 102 to identify the base 15 station 101 transmitting the radio signal. The relay nodes 102 deliver data or information to the wireless communication device m 103 in multi-hops, thereby extending the coverage and improving the communication capability and quality of the base station 101. The amount of data a wireless communication device m 103 receives in a transmission schedule, referred as decision variable dm can be computed using a 20 transmission scheduler. The notation Rm refers the average data rate received by wireless communication device m till the previous scheduling frame. The rate of data r (Im,C) can be achieved over the link Im between the wireless communication device m 103 and the relay node 102 to which the wireless communication device m 103 is related, over subchannel C in the current scheduling frame. The scheduling algorithm attempts to 25 maximize a utility function F(d) that takes into account the utility of serving dm amount of data to mobile m. The information on the rate of data is available at the base-station 101 and WiMAX relay standards provide mechanisms for obtaining the rate of data. 25. FIG. 2 is a block diagram illustrating the components of a base station, according to an embodiment herein. The base station 101 comprises of a transmitting 30 antenna 201, a transmitter 202, a receiving antenna 203, a receiver 204, a base station controller 205, which further comprises a scheduler 206 and an interface to the network infrastructure 207. The transmitter 202 performs transmission of signals to the wireless communication devices 103 using the transmitting antenna 201. The receiving antenna 203 receives the signals from the wireless communication devices 103 and the signals are 35 passed onto the receiver 204 before being sent over the network infrastructure through 9 of 18 the interface 207. The base station controller 205 controls the functionalities 5 of the base station 101 including the transmission and reception of wireless signals to and from the wireless communication devices 103. The scheduler 206, present in the controller 205 performs scheduling of the frames to be transmitted so that the schedules of the frames exploit the frequency and time diversity of wireless channels and the schedule 10 computation is done within 5 ms duration of a scheduling frame. The scheduler 206 has to consider that a relay network has a multi-hop technology, with each hop comprising of several OFDMA sub channels, with each sub channel having a different sustainable rate over each multi-hop link. Also, the scheduler has to perform synchronization in a multihop technology and ensure that any relay node 102 in contact with the base station 101 is 15 not transmitting and receiving concurrently. The scheduler 206 must ensure that data from base station 101 to the wireless communication device 103 and vice versa reaches its destination within the same frame. 26. FIG. 3 illustrates a flowchart depicting a method of transmission scheduling for OFDMA based relay networks, according to an embodiment herein. The 20 scheduling frame is segmented (301) to divisions equal to the number of network hops. The time-slots belonging to segment h are only assigned to links which are h hops or more from the base station 101. The scheduling frame is segmented in a manner that the segmenting slots in a scheduling frame for the links in the path from the base station 101 to the wireless communication device m 103 to be located in separate segments and 25 assigning sub-channels in different links by paying higher priority to wireless communication device m using less time slots along the path for unit increment in objective function F(d). The segmentation of the scheduling frame solves the ordering constraint (i.e., the relay nodes receive more data than they send till time-slot t in the scheduling-frame for all t) if all sub-channels for first hop links are assigned to the first 30 segment, all the sub-channels for the second hope links to the second segment, and so the like. The eligible wireless communication devices m are selected (302) after segmenting the frame. A wireless communication device m is eligible for scheduling, if for a subchannel C the wireless communication device m has a higher ratio of r(Im,C)/Rm among all the wireless communication device m connected to a relay node 102 or base station 35 101. Further, create (303) a list of eligible wireless communication device m for 10 of 18 scheduling. Obtain (304) the time-slot required by eligible 5 wireless communication device m to increase the objective function F(d) by transmitting data to wireless communication device m only. Incrementing F(d) by single unit by only increasing decision variable dm requires Rm (average data rate received by wireless communication device) units of data to be transferred to wireless communication device m, which 10 requires Rm/r(Im,C) time slots of the link that is present in the path to wireless communication device m. Further, allocate (305) maximum slots to wireless communication device m requiring least number of time slots. When an optimal subchannel is used, wireless communication device m needs at least a predetermined number of slots on link l such number calculated using the equation am(l) = min {c: Rm/r(l,C)}. 15 Thus, the maximum number of slots required on any of the segments is bm = max{l is in path from m to BS: am(l)} as the links in the path are present on distinct segments. In every iteration, the wireless communication device m with minimum bm is chosen for unit increase in F(d). Thereafter, update (306) slots for each sub-channel and segments by incrementing F(d). The various actions in method 300 may be performed in the order 20 presented, in a different order, or simultaneously. Further, in some embodiments, some actions listed in FIG. 3 may be omitted 27. FIG. 4 illustrates a flowchart depicting a method of transmission scheduling for Wi-MAX relay networks using FastHeuristic16j scheduler, according to an embodiment herein. The method comprises of solving a LP (Linear Program) to 25 determine subchannel and time allocation to different links, and then rounding the LPbased solution without violating the flow and synchronization constraints. The solving of LP are based on the assumptions that for any relay node u, transmissions over subchannel C to wireless communication device m associated with u occurs only to the wireless communication device m for which r(Im,C) /Rm maximum and the relay link 30 holds a time duration during which all sub-channels are used for transmission over the link. The time allocated to each relay node/base station associated to u is partitioned into multiple segments as Tm(u), the number of time-slots for transmitting data to the wireless communication device m related to relay node u, and Tr(l), and the number of time-slots for transmitting data on the relay-child link l 2 L0u. The two simplifying assumptions 35 lead to an LP which can be solved without using any LP-solver tool. The simplification is 11 of 18 proved for the wireless communication device m connected to 5 the base-station, and thus is an extension of base-station’s property to the relay nodes. Thus each wireless communication device m receives data exclusively over specific sub-channels. The relay links have clear line of sight and smaller path loss exponent as compared to the relay to wireless communication device m or base station to wireless communication device m 10 links. Transmissions from a central relay node to an associated relay node in the routing pattern use all the sub-channels simultaneously and hence the delay spread of the channels is low. The low delay spread results in high signal to noise ratio for all the subchannels, and also causes little or no frequency diversity. The method of scheduling comprises of calculating (401) total transmission rate Cu of a relay node to the parent 15 node of the routing tree topology, calculating (402) the effective capacity Cu of a relay node or base station to the wireless communication device m, and calculating (403) the contribution Uu per time slot to unit increment of objective function F(d) by the wireless communication device m linked to relay node u. Thus, Cu, Cu, Uu can be defined as Cu := c r(lu,C), Cu := c r( Imc(u) , C), Uu := c r( Imc(u) , C)/Rmc(u). Further, compute (404) Chu 20 for all relay nodes and base stations, where Chu = 1/(1/ Cu + {v: v is in the path from u to BS}1/Cv) and compute (405) Uu associated to relay node or base station. The relay node or base station with Uu. Chu/ Cu value maximum is selected (406) and then allocate (407) sub-channel C to wireless communication device m for which r(Im,C)/Rm value is maximum. Further, allocate (408) slots to an intermediate relay node v in the path from 25 the relay node with Uu. Chu/ Cu value maximum to the base station. The various actions in method 400 may be performed in the order presented, in a different order, or simultaneously. Further, in some embodiments, some actions listed in FIG. 4 may be omitted 28. FIG. 5 illustrates a flowchart depicting a method of transmission 30 scheduling for Wi-MAX relay networks using TreeTraversal scheduler, according to an embodiment herein. The scheduler is applicable when the relay links have frequency selectivity and solves the relay scheduling problem based on the idea that a sub-channel at a relay node, instanced as u, is dedicated to transmission to only one of the associated nodes which may be a wireless communication device m or another relay node associated 35 to u. The method traverses the routing topology in a bottom up manner and the fraction of 12 of 18 time-slots to be assigned to RS’s in Tv (for all relays v that 5 is an associated node of u) out of every unit time-slot allocated to Tu is computed for all relay nodes or base stations associated to u, where Tu is the subtree of the tree formed by the relay nodes and the base station under relay node u. The method includes calculating (501) the increment iu in objective function F(d) due to data transmitted to all wireless communication devices m 10 in the subtree Tu in the routing topology for unit time-slot allocated to the subtree Tu, calculating (502) total data per time-slot cu to be transmitted to all the wireless communication devicess m in subtree Tu for incrementing F(d) by iu per time-slot and computing (503) fraction of transmission time tu allocated to relays in Tu for every unit time allocated to Tpu where pu is the parent relay node of relay node u .Further, iu and cu 15 for relay nodes is computed (504) and then compute (505) iu and cu for the intermediate relay-nodes using the iu and cu for the associated relays by traversing the routing topology in a bottom-up manner. Thereafter, employ the values of iu and cu obtained for computing (506) the time allocations to relays by traversing the routing topology in a top-down manner. The various actions in method 500 may be performed in the order presented, in a 20 different order, or simultaneously. Further, in some embodiments, some actions listed in FIG. 5 may be omitted 29. Embodiments disclosed herein require the base stations to be aware of channel quality for all sub-channels at each relay node to relay node and relay node to wireless communication device m links at the beginning of the scheduling frame. The 25 channel quality is evaluated based on supportable modulation-coding combination. The FastHeuristic 16j scheduler is used to compute both downlink and uplink schedules for WiMAX relay networks. An uplink and downlink map can be constructed based on the computed schedule and then disseminated at the beginning of the scheduling frame. Further, the average data rates for wireless communication device m are updated on 30 completion of the scheduling frame and then compute the downlink and uplink schedules for performing the operation for the succeeding scheduling frame. 30. Embodiments disclosed herein achieve the option of using single radio at relay node for OFDMA based relay networks. Further, the embodiments provide improvement in mean throughput depending on the routing topology and exploits 35 frequency-dependent attenuation of wireless relay links in OFDMA networks. 13 of 18 31. Embodiments disclosed herein optimize a 5 throughput dependent utility function in WiMAX relay networks and provides proportional equity of the individual user throughputs. The resource-allocation decision in less than 0.1ms and hence suitable for WiMAX relay networks where computation of transmission schedules need to be performed in ms. The scheduling requires only single radio per relay node and achieves 10 improvement in mean and median throughputs. 14 of 18 5 CLAIMS What is claimed is: 1. A method of scheduling transmissions for Orthogonal Frequency Division Multiple Communication (OFDMA) based relay networks, said method comprising steps of: 10 segmenting (301) a scheduling frame to number of network hops divisions; selecting (302) wireless communication devices (103) with high r(Im, C)/Rm ratio from plurality of wireless communication devices (103) connected to a relay node (102) for scheduling, wherein Rm is average data rate received by wireless communication devices (103) and r(Im, C) is data rate over the link between wireless 15 communication device (103) and said relay node (102) in a scheduling frame; and computing (303) highly eligible wireless communication device (103) from selected communication devices with high r(Im,C)/Rm, said computing further comprising steps of: obtaining (304) number of slots required to increase objective function 20 F(d) by at least one unit for said eligible wireless communication device (103); allocating (305) said slots to said wireless communication device (103) requiring least number of said slots; and updating (306) said slots available for sub-channels and segment. 25 2. The method, as claimed in claim 1, wherein said slots in said scheduling frame are segmented (301) to locate links in path from base station (101) to said wireless communication device (103) in different segments. 3. The method, as claimed in claim 1, wherein sub-channels are assigned in different 30 said links with priority to said wireless communication device (103) using minimum time-slots for at least one unit increment in said objective function F(d). 4. A method of scheduling transmission for WiMAX relay networks, said method comprising steps of: 15 of 18 calculating (401) total transmission rate Cu of relay 5 node (102) u to a central node; calculating (402) effective capacity Cu of a base station (101) to corresponding wireless communication devices (103); calculating (403) contribution Uu per-time slot increase in objective function F(d) 10 by said wireless communication devices (103) associated to said relay node (102) u; computing (404) Chu for corresponding said relay node (102) and said basestation (101); computing (405) Uu associated to said relay node (102) and said base station (101); 15 choosing (406) said relay node and said base station with maximum Uu.Chu/ Cu value; allocating (407) sub-channel C to a wireless communication device with maximum r(Im,C)/Rm value; and allocating (408) slots to an intermediate relay node in path from said relay node 20 (102) to said base-station (101). 5. The method, as claimed in claim 4, wherein said Chu is computed (404) by 1/(1/ Cu + {V:V in path from u to base station}1/Cv), where v is an intermediate relay node. 25 6. A method of scheduling transmission for WiMAX relay networks, said method comprising steps of: computing (504) iu and cu for relay-nodes; computing (505) iu and cu for intermediate relay-nodes using said iu and said cu for relay nodes (102) by traversing routing topology in a bottom-up manner; and 30 computing (506) time allocations by traversing said routing topology in a topdown manner. 7. The method, as claimed in claim 6, wherein iu is calculated (501) for all time slots allocated to a subtree Tu by computing increase in an objective function F(d), wherein 16 of 18 data transmitted to wireless communication devices in said Tu increases 5 said objective function F(d). 8. The method as claimed in claim 6, wherein said cu is calculated as total data per time slot to be transmitted to said wireless communication device (103) in a subtree Tu 10 for incrementing said objective function F(d) by iu per time slot. 9. A system for scheduling transmission for generic Orthogonal Frequency Division Multiple Communication (OFDMA) based relay networks, said system comprising at least one means adapted for: 15 segmenting (301) a scheduling frame to number of network hops divisions; selecting (302) wireless communication devices (103) with high r(Im, C)/Rm ratio of plurality of wireless communication devices (103) connected to a relay node (102) for scheduling, where Rm is average data rate received by wireless communication devices (103) and r(Im, C) is data rate over the link between wireless communication 20 device (103) and said relay node (102) in a scheduling frame; and computing (303) highly eligible wireless communication device (103) from selected communication devices with high r(Im,C)/Rm, said computing further comprising of : obtaining (304) number of slots required to increase objective function 25 F(d) by at least one unit for said eligible wireless communication device (103); allocating (305) said slots to said wireless communication device (103) requiring least number of said slots; and updating (306) said slots available for sub-channels and segment. 30 10. A system for scheduling transmission for WiMAX relay networks, said system comprising at least one means adapted for: calculating (401) total transmission rate Cu of relay node (102) u to a central node; calculating (402) effective capacity Cu of a base station (101) to a corresponding 35 wireless communication device (103); 17 of 18 calculating (403) contribution Uu per-time slot increase in 5 objective function F(d) by said wireless communication device (103) associated to said relay node (102) u; computing (404) Chu for corresponding said relay node (102) and said basestation (101); computing (405) Uu associated to said relay node (102) and said base station 10 (103); choosing (406) said relay node (102) and said base station (103) with Uu.Chu/ Cu value maximum; allocating (407) sub-channel C to wireless communication device (103) with maximum r(Im,C)/Rm value; and 15 allocating (408) slots to an intermediate relay node in path from said relay node (102) to said base-station (103). 11. A system of scheduling transmission for WiMAX relay networks, said system comprising at least one means adapted for: 20 computing (504) iu and cu for relay-nodes; computing (505) iu and cu for intermediate relay-nodes using said iu and said cu for relay nodes by traversing routing pattern in a bottom-up manner; and computing (506) time allocations by traversing said routing pattern in a top-down manner. 18 of 18 5 ABSTRACT Methodologies for scheduling transmissions in Orthogonal Frequency Division Multiple Communication (OFDMA) based relay networks and Worldwide Interoperability for Microwave Communication (WiMAX) relay networks are disclosed. 10 The network routing topology comprises of a base station, intermediate relay nodes and wireless communication device associated to base stations/relay nodes. The transmission scheduler for OFDMA based relay networks use a GenArgMax method for scheduling transmission. The transmission scheduling for WiMAX relay networks is performed by a FastHeuristic 16j scheduling procedure and a TreeTraversal scheduling process. The 15 methodologies eliminate multiple constraints induced by transmission scheduling in WiMAX relay networks. FIG. 1 20