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