Abstract:
A method for selecting routing and cancelling overloading in multihop cellular systems is provided herein. The method includes finding a user group having several routing selections in an overloading relay station, finding a user having maximum routing selections in the user group, disconnecting the routing link between the overloading relay station and the user to reduce the use of bandwidth of the overloading relay station, and finding an optimal routing from at least one un-overloading relay station group to link the user.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    This invention generally relates to the field of communication systems, and more particularly, to a method and system for selecting routing and cancelling overloading in multihop cellular systems. 
         [0003]    2. Description of the Prior Art 
         [0004]    In traditional cellular systems, the base station (BS) executes signal processing by its own antennae for each user, but its coverage area and frequency resources are limited. 
         [0005]    In response to a demand for next generation cellular systems to support high data rates, enlarge the coverage area, and provide good quality of service (QoS) for multimedia applications, Dixit et at have put their efforts in integrating the multihop relay technique into the cellular system for investigating the routing and topology issues (S. Dixit, E. Yanmaz, and O. K. Tonguz, “On the design of self-organized cellular wireless networks,”  IEEE Commun. Mag.,  vol. 43, pp. 86-93, July 2005.) In a multihop cellular system, a user can either connect to the BS directly, or via relay stations (RSs). Consequently, it is possible to accommodate more transmission routes to increase the system capacity. However, this may be influenced by the RS overloading problem, whose congestion occurs owing to a large number of users requesting the same RS for service simultaneously. 
         [0006]    Existing overloading relief may be loosely divided into two categories. One is the dynamic balance of the load, whose mathematical theory is illustrated in O. K. Tonguz and E. Yanmaz, “The mathematical theory of dynamic load balancing in cellular networks,”  IEEE Trans. Mobile Comput.,  vol. 7, pp. 1504-1518, December 2008, and the other is the reduction of the data rate, a sub-optimal solution since its optimum throughput is proven to be NP-hard (Y. Liu, R. Hoshyar, X. Yang, and R. Tafazolli, “Integrated radio resource allocation for multihop cellular networks with fixed relay stations,”  IEEE J. Sel. Areas Commun.,  vol. 24, pp. 2137-2146, November 2006.) The former scheme is applicable when the old channel condition between the served user and the overloaded RS is similar to the new one between the served user and the unoverloaded RS, thus the served user will shift completely the volume of the transmitting data from the old RS to the new one. However, when the unoverloaded RS locates too far away or the new channel has enormous interference or deep fades, the served user may need larger capacity from the new RS for supporting the same quality transmission, and this would make the new RS to change its status from unoverloading to overloading. 
         [0007]    In view of the drawbacks mentioned with the prior art of the method for cancelling overloading, there is a continuous need to develop a new and improved method that overcomes the shortages associated with the prior art of the method for cancelling overloading. The advantages of the present invention are that it solves the problems mentioned above. 
       SUMMARY OF THE INVENTION 
       [0008]    In accordance with the present invention, a method and system for routing selection and overloading cancellation in multihop cellular systems substantially obviates one or more of the problems resulted from the limitations and disadvantages of the prior art mentioned in the background. 
         [0009]    One of the purposes of this invention is to reduce the use of bandwidth of an overloading relay station by disconnecting the transmission link between the overloading relay station and the user(s) thereof, whereby to exclude the overloading relay station from the overloading status. 
         [0010]    Another purpose of this invention is to reduce the use of bandwidth of an overloading relay station by decreasing the bandwidth of the user of the overloading relay station, whereby to solve the overloading problem for the overloading relay station. 
         [0011]    Still another purpose of this invention is to provide an optimal routing to a user to link to, wherein the user disconnects the transmission routing from an overloading relay station. 
         [0012]    The present invention provides a method for selecting routing and cancelling overloading in multihop cellular systems. The method includes (a) finding a user group having a plurality of routing selections from an overloading relay station, wherein the number of user in the user group is not zero; (b) finding a user having maximum routing selections from the user group, wherein the routing selections of the user include at least one un-overloading relay station group; (c) disconnecting the routing link between the overloading relay station and the user to reduce the use of bandwidth of the overloading relay station; and (d) finding an optimal routing from the at least one un-overloading relay station group to link the user. 
         [0013]    The present invention further discloses a system for selecting routing and cancelling overloading in multihop cellular systems. The system includes a plurality of relay stations linking with a base station to form a multihop cellular network. Wherein, when at least one relay station in the plurality of relay stations is overloaded, the system performs the steps as follows (a) finding a user group having a plurality of routing selections from the at least one relay station, wherein the number of user in the user group is not zero; (b) finding a user having maximum routing selections from the user group, wherein the routing selections of the user include at least one un-overloading relay station group; (c) disconnecting the routing link between the at least one relay station and the user to reduce the use of bandwidth of the at least one relay station; and (d) finding an optimal routing from the at least one un-overloading relay station group to link the user. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The accompanying drawings incorporated in and forming a part of the specification illustrate several aspects of the present invention, and together with the description serve to explain the principles of the disclosure. In the drawings: 
           [0015]      FIG. 1  illustrates one preferred system embodiment in accordance with the present invention; 
           [0016]      FIG. 2  illustrates one preferred flowchart in accordance with the present invention; 
           [0017]      FIG. 3A  depicts the comparisons of the system capacity in terms of users for one embodiment of this invention, IRRA, and iCAR schemes with a system bandwidth of 300 MHz; 
           [0018]      FIG. 3B  depicts the comparisons of the transmission power regarding number of users for one embodiment of this invention, IRRA, and iCAR algorithms; and 
           [0019]      FIG. 3C  shows the comparisons of the outage probability regarding number of users for one embodiment of this invention, IRRA, and iCAR designs. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0020]    Some embodiments of the present invention will now be described in greater detail. Nevertheless, it should be noted that the present invention can be practiced in a wide range of other embodiments besides those explicitly described, and the scope of the present invention is expressly not limited except as specified in the accompanying claims. 
         [0021]    Moreover, some irrelevant details are not drawn in order to make the illustrations concise and to provide a clear description for easily understanding the present invention. 
         [0022]    Referring to  FIG. 1 , a preferred system embodiment  10  in accordance with the present invention is illustrated. Two base stations BS A  and BSB have different service areas. Both of them, herein, could be the same system or different system, and are connected by a backbone  12 . Several relay stations, such as RS A1 , RS A2 , RS A3 , RS A4 , RS A5 , RS A6 , RS A7 , and RS B1 , correspondingly locate in the service areas of the base stations BS A  and BS B , and link with the base stations BS A  and BS B . Hereinafter, the inventor only uses the embodiment of  FIG. 1  as one sample explanation for the present invention. However, when the system of this invention is fulfilled in practice and has more base stations and relay stations, its operations should be the same as the embodiment described in  FIG. 1 , and this part can be obvious to those skilled in the art after they read the disclosure of this invention. Thus, the operations for the system of this invention with more base stations and relay stations will not be described. 
         [0023]    Referring to  FIG. 1  again, the relay stations RS A1 , RS A5 , and RS A6  are assumed that they are overloaded, and thus they are recorded in an overloading list by the base station BS A  to form a set of overloading relay station. First, the relay station RS A1  finds a user group with several routing selections from its users, in this embodiment, the user group has a user u A11  with 3 routing selections  101 ,  101 A, and  101 B, a user u A12  with 2 routing selections  102  and  102 A, and a user u A13  with 2 routing selections  103  and  103 A. Next, the relay station RS A1  finds a user having maximum routing selections from the user group, for example, the user u A11  in this case. Wherein, the routing selections of the user u A11  have at least one un-overloading relay station to form an un-overloading relay station group, such as the relay stations RS A2  and RS A3 . Then, the relay station RS A1  disconnects the routing link  101  between the relay station RS A1  and the user u A11  to reduce the use of bandwidth of the relay station RS A1 , whereby to solve the overloading problem. And finally, the user u A11  finds an optimal routing from the un-overloading relay station group, such as the relay stations RS A2  and RS A3 , to link to. In this embodiment, the user u A11  can select either a routing link  101 A to link to the relay station RS A2  or a routing link  101 B to link to the relay station RS A3 . The user u A11  chooses the routing link  101 A linking with the relay station RS A2  as the optimal routing since the routing link  101 A linking with the relay station RS A2  provides better communication status than the routing link  101 B linking with the relay station RS A3  does, for example, the relay station RS A2  can offers the bandwidth required by the user u A11 , but the relay station RS A3  can only provides a part of bandwidth required by the user u A11 . 
         [0024]    The inventor would like to stress that the user u A11  selects the optimal routing based on an optimal communication channel. In some cases, the optimal routing could be the shortest routing, such as linking to the base station BS A  through the routing link  101 B and the relay station RS A3 . In other cases, such as those mentioned above, the optimal routing could not be the shortest routing, for example, linking to the base station BS A  through the routing link  101 A, the relay station RS A2 , and the relay station RS A4 . Further, the optimal routing selection for the user u A11  could be determined by the steps as follows: 
         [0025]    Comparing the time (a first time) for the user u A11  passing through the routing link (a first routing) of the relay station RS A1  and the time (a second time) for the user u A11  passing through the routing link (a second routing) of the relay station RS A2 , when the difference between the first time and the second time is smaller than a predetermined threshold, the routing link of the relay station RS A2  is the optimal routing for the user u A11 . 
         [0026]    Besides, when the relay station RS A1  disconnects the routing link  101  from the user u A11 , the relay station RS A1  excludes the user u A11  from its users, and the user u A11  also removes the relay station RS A1  from its routing selections. 
         [0027]    Referring to  FIG. 1  again, if the relay station RS A1  is still in overloading status after it disconnects the routing link  101  of the user u A11 , the relay station RS A1  refinds a user group with several routing selections from its users, in this time, the user group has only the user u A12  with 2 routing selections  102  and  102 A, and the user u A13  with 2 routing selections  103  and  103 A since the user u A11  is excluded from the users of the relay station RS A1 . Next, the relay station RS A1  find a user having maximum routing selections from the user group, e.g. taking the user u A12  for a sample. Wherein, the routing selections of the user u A12  have at least one un-overloading relay station to form an un-overloading relay station group, such as the relay station RS B1 . Then, the relay station RS A1  disconnects the routing link  102  between the relay station RS A1  and the user u A12  to reduce the use of bandwidth of the relay station RS A1 , whereby to solve the overloading problem. And finally, the user u A12  finds an optimal routing from the un-overloading relay station group, such as the relay station RS B1 , to link to. In this time, the user u A12  can only select a routing link  102 A to link to the relay station RS B1 . 
         [0028]    The inventor would like to emphasize that the optimal routing selection, such as for the user u A12 , should not be limited at the relay stations within the service area of the same base station BS A , the optimal routing selection could be the relay station(s), such as the relay station RS B1 , within the different service areas of the different base stations, for example, the base station BS B . 
         [0029]    Likewise, when the relay station RS A1  disconnects the routing link  102  from the user u A12 , the relay station RS A1  excludes the user u A12  from its users, and the user u A12  excludes the relay station RS A1  from its routing selections as well. 
         [0030]    Referring to  FIG. 1  again, if the relay station RS A1  is in un-overloading status after it respectively disconnects the routing links  101  and  102  from the users u A11  and u A12 , the relay station RS A1  is removed from the overloading list mentioned above by the base station BS A . That is, the relay station RS A1  is excluded from the set of overloading relay station. The user u A13  keeps the routing link  103 A linking to the relay station RS A1  because the relay station RS A1  is not in overloading status. 
         [0031]    Referring to  FIG. 1  again, if the set of overloading relay station is not empty (for example, the relay stations RS A5  and RS A6  are still overloaded) after the base station BS A  excludes the relay station RS A1  from the overloading list, the relay station RS A5  finds a user group with several routing selections from its users, in this case, the relay station RS A5  cannot find the user group because each of its users has only one individual routing, and hence, the number of the user group is zero. Next, the relay station RS A5  finds a user using a maximum bandwidth from its users and reduce the bandwidth of the user using the maximum bandwidth to decrease the use of bandwidth of the relay station RS A5 , whereby to exclude the relay station RS A5  from overloading status. 
         [0032]    To reduce the bandwidth of the user using the maximum bandwidth, it can be implemented by the steps as follows: reducing the bandwidth of the user using the maximum bandwidth by a predetermined value to decrease the use of bandwidth of the relay station RS A5  or multiplying the bandwidth of the user using the maximum bandwidth by a predetermined percentage to reduce the use of bandwidth of the relay station RS A5 . 
         [0033]    If the overloading problem of the relay station RS A5  is completely solved (e.g. the bandwidth capacity of the relay station RS A5  is bigger than the use of bandwidth required by all its users) after the relay station RS A5  reduces the bandwidth of the user using the maximum bandwidth, the relay station RS A5  is removed from the overloading list by the base station BS A . In other words, the relay station RS A5  is excluded from the set of overloading relay station. 
         [0034]    Referring to  FIG. 1  again, if the set of overloading relay station is not empty yet (e.g. the relay station RS A6  is still in overloading status) after the base station BS A  removes the relay stations RS A1  and RS A5  from the overloading list, the relay station RS A6  finds a user group with several routing selections from its users, in this case, the user group has a user u A61  with 2 routing selections  111  and  111 A, the user u A62  with 2 routing selections  112  and  112 A, and the relay station RS A7  with 3 routing selections  113 ,  113 A, and  103 B. Next, the relay station RS A6  finds a user having maximum routing selections from the user group, for example, the relay station RS A7  in this case. Wherein, the routing selections of the relay station RS A7  have at least one un-overloading relay station to form an un-overloading relay station group, such as the relay stations RS A2  and RS A4 . Then, the relay station RS A6  disconnects the routing link  113  between the relay station RS A6  and the relay station RS A7  to reduce the use of bandwidth of the relay station RS A6 , whereby to solve the overloading problem. Finally, the relay station RS A7  finds an optimal routing from the un-overloading relay station group, such as relay stations RS A2  and RS A4 , to link with. In this case, the relay station RS A7  can select either a routing link  113 B to link to the relay station RS A2  or a routing link  113 A to link to the relay station RS A4 . The relay station RS A7  is assumed that it chooses the routing link  113 A linking with the relay station RS A4  as the optimal routing because the routing link  113 A linking with the relay station RS A4  provides better communication status than the routing link  113 B linking with the relay station RS A2  does, for example, the transmission attenuation by the relay station RS A4  is smaller than by the relay station RS A2  or the communication channel interference by the relay station RS A4  is smaller than by the relay station RS A2 , etc. 
         [0035]    The inventor would like to emphasize that the relay station RS A7  selects the optimal routing also based on an optimal communication channel. In this case, the optimal routing meets the shortest routing (e.g. linking to the base station BS A  through the routing link  113 A and the relay station RS A4 ), but not limit to. Further, the optimal routing selection for the relay station RS A7  can be fulfilled according to the optimal routing selection for the user u A11  mentioned before, and this part is obvious to those skilled in the art by reading this disclosure and would not be repeated here. The inventor also would like to clarify that the user and the user group mentioned in this invention should not be limited in end-user communication devices and they could be relay communication tools as well. In this invention, the user and the user group include communication devices and/or relay stations, such as the relay station RS A7  in this case. 
         [0036]    Similarly, when the relay station RS A6  disconnects the routing link  113  from the user (the relay station RS A7 ), the relay station RS A6  excludes the relay station RS A7  from its users, and the relay station RS A7  also excludes the relay station RS A6  from its routing selections. 
         [0037]    Referring to  FIG. 1  again, if the relay station RS A6  is still in overloading status after it disconnects the routing link  113  from the relay station RS A7 , the relay station RS A6  refinds a user group with several routing selections from its users, in this time, the user group has only user u A61  with 2 routing selections  111  and  111 A, and user u A62  with 2 routing selections  112  and  112 A since the relay station RS A7  is excluded from the users of the relay station RS A6 . Next, the relay station RS A6  finds a user having maximum routing selections from the user group, in this case, taking the user u A61  for a sample. Wherein, the routing selections of the user u A61  have at least one un-overloading relay station to form an un-overloading relay station group, such as the relay station RS A4 . Then, the relay station RS A6  disconnects the routing link  111  between the relay station RS A6  and the user u A61  to reduce the use of bandwidth of the relay station RS A6 , whereby to solve the overloading problem. And finally, the user u A61  finds an optimal routing from the un-overloading relay station group, such as the relay station RS A4 , to link to. In this time, the user u A61  can only select the routing link  111 A to link with the relay station RS A4 . 
         [0038]    In the same way, when the relay station RS A6  disconnects the routing link  111  from the user u A61 , the relay station RS A6  excludes the user u A61  from its users, and the user u A61  also excludes the relay station RS A6  from its routing selections. 
         [0039]    Referring to  FIG. 1  again, if the relay station RS A6  is still in overloading status after it disconnects the routing links  113  and  111  respectively from the relay station RS A7  and the user u A61 , the relay station RS A6  refinds a user group with several routing selections from its users, in this time, the user group has only the user u A62  with 2 routing selections  112  and  112 A since the relay station RS A7  and the user u A61  are excluded from the users of the relay station RS A6 . However, because the routing link  112 A of the user u A62  has no at least one un-overloading relay station (for example, assumed that the relay stations RS A5  is in overloading status), the relay station RS A6  finds a user using a maximum bandwidth in its users and reduces the bandwidth of the user using the maximum bandwidth to decrease the use of bandwidth of the relay station RS A6 , whereby to exclude the relay station RS A6  from overloading status. 
         [0040]    To reduce the bandwidth of the user using the maximum bandwidth, it can be realized by the steps of reducing the bandwidth of the relay station RS A5 &#39;s user using the maximum bandwidth mentioned before, and this part is obvious to those skilled in the art after reading this disclosure and would not be repeated here. 
         [0041]    If the overloading problem of the relay station RS A6  is completely solved (e.g. the bandwidth capacity of the relay station RS A6  is bigger than the use of bandwidth required by all its users) after the relay station RS A6  disconnects the routing links  113  and  111  correspondingly from the relay station RS A7  and the user u A61  and reduces the bandwidth of the user using the maximum bandwidth, the relay station RS A6  is removed from the overloading list by the base station BS A . In other words, the relay station RS A6  is excluded from the set of overloading relay station. 
         [0042]    Until now, the set of overloading relay station of the preferred embodiment illustrated in  FIG. 1  is empty after the base station BS A  removes the relay stations RS A1 , RS A5 , and RS A6  from the overloading list successively. That is, the overloading problems in the preferred embodiment of  FIG. 1  are completely solved and there is no relay station in overloading status within this multihop cellular system. 
         [0043]    Referring to  FIG. 2 , a flowchart for one preferred embodiment  20  in accordance with the present invention is illustrated. In step  22 , a base station finds an overloading relay station from a set of overloading relay station. Wherein, the set of overloading relay station is an overloading list recorded by the base station, and it means there is(are) relay station(s) in overloading status waiting to be solved in this embodiment while the set of overloading relay station is not empty. In step  24 , the overloading relay station checks whether its users have other routing selections or not? Wherein, the abovementioned other routing selections include at least one un-overloading relay station to form an un-overloading relay station group, and the un-overloading relay station group could have at least one relay station linking with the same base station or a different base station. 
         [0044]    If all the users of the overloading relay station have no additional routing selection, then step  212  is performed. In step  212 , the overloading relay station finds a user using a maximum bandwidth in the users of the overloading relay station. In step  214 , the overloading relay station decreases the bandwidth of the user using the maximum bandwidth. Wherein, the method for reducing the bandwidth of the user using the maximum bandwidth could be to reduce the bandwidth of the user using the maximum bandwidth by a predetermined value to reduce the use of bandwidth of the overloading relay station, and also could be to multiply the bandwidth of the user using the maximum bandwidth by a predetermined percentage to reduce the use of bandwidth of the overloading relay station. In step  216 , the base station updates the set of overloading relay station. Wherein, the overloading relay station is removed from the overloading list recorded by the base station when its overloading problem is solved. That is, the overloading relay station is excluded from the set of overloading relay station. 
         [0045]    In step  26 , the base station checks whether the set of overloading relay station is empty or not? When the set of overloading relay station is not empty, it means there is (are) relay station(s) in overloading status waiting to be solved in this embodiment, and then the processes repeats from step  22 . However, when the set of overloading relay station is empty, all the processes mentioned above are to be ended in step  28 . 
         [0046]    If at least one user of the overloading relay station has another routing selection, then step  222  is carried out. In step  222 , the overloading relay station finds a user having maximum routing selections from its users. In step  224 , the overloading relay station is excluded from the user&#39;s routing selections, and the user is also removed from the overloading relay station&#39;s users. That is, the overloading relay station disconnects the routing link between itself and the user to reduce the use of bandwidth thereof. In step  226 , the base station finds an optimal routing to link to the user. Wherein, the optimal routing is based on an optimal communication channel, in some cases, the optimal routing could be the shortest routing, but in other cases, the optimal routing could not be the shortest routing. Further, the optimal routing can be determined by the steps as follows: comparing the time (a first time) for the user passing through the routing link (a first routing) of the overloading relay station and the time (a second time) for the user passing through the routing link (a second routing) of an un-overloading relay station, when the difference between the first time and the second time is smaller than a predetermined threshold, the routing link of the un-overloading relay station is the optimal routing for the user. In step  228 , the user chooses the optimal routing to link to, and the base station updates the set of the overloading relay station. And then, the processes repeats from step  26 , and the details, here, will not be described again. 
         [0047]    The inventor would like to clarify that the user and the user group mentioned in this invention should not be limited in end-user communication devices only and they could be relay communication equipments as well. For example, the user and the user group could be communication devices or relay stations. 
         [0048]    The comparisons for the simulations, such as system capacity, transmission power, and outage probability, among embodiments of this invention and well-known techniques are described below. The inventor would like to emphasize that the related data set for simulations and the results obtained from simulations are used to explain the simulation processes and the results of embodiments in accordance with this invention, but not limit the implementing of this invention. Let the system (e.g. a multihop cellular system) bandwidth be 300 MHz, and the transmission data rates be 1 M, 800 k, 600 k, 400 k, and 200 k bits per second that uniformly distributed among all users. Furthermore, most of throughput gains can be obtained with the use of a two- or three-hop relaying scheme (J. Cho and Z. J. Hasa, “On the throughput enhancement of the downstream channel in cellular radio networks through multihop relaying,”  IEEE J. Sel. Areas Commun.,  vol. 22, pp. 1206-1219, September 2004.), therefore the maximum number of hops for each user can be reasonably set as three. The prescribed threshold of the overall bit error rate (BER) is set to be 10 −5 . The multihop cellular system with either 10 or 20 relay stations is considered. 
         [0049]    Referring to  FIG. 3A , the comparisons of the capacity regarding number of users for preferred embodiments of this invention and well-known schemes are illustrated. Notice that the relay stations have no overloading problem as the number of users is under 300. However, once the number of users is more than 300, the overloading event occurs. The capacities of the embodiments of this invention in 10 or 20 relay stations outperform those of other two schemes in 10 or 20 relay stations owing to the fact that the integrated radio resource allocation (IRRA) scheme reduces solely the data rates of the users, while the integrated cellular and ad hoc relaying (iCAR) only executes its primary and secondary relaying without taking the channel impact into account. Moreover, the IRRA performs better than the iCAR regarding capacity, which implies that the multihop cellular system suffers larger influence on the channel selection than the transmission data rate. 
         [0050]    Referring to  FIG. 3B , the comparisons of the transmission power regarding number of users for preferred embodiments of this invention and well-known algorithms are depicted. As the overloading problem occurs, the transmission power becomes saturated, and the embodiment of this invention displays a better performance than IRRA and iCAR regardless of whether the number of relay stations is 10 or 20. 
         [0051]    Referring to  FIG. 3C , the comparisons of the outage probability regarding number of users for preferred embodiments of this invention and well-known designs are shown. Both the embodiments of this invention and the IRRA can accommodate more users whether the number of relay stations is 10 or 20, and that is, they possess a lower outage probability than the iCAR does with 10 or 20 relay stations. In addition, the embodiments of this invention execute the “user switched” step first as the overloading problem occurs, followed by the data rate reduction. This can release more bandwidth to the other potential users and make its outage probability better than the IRRA&#39;s. 
         [0052]    Although specific embodiments have been illustrated and described, it will be obvious to those skilled in the art that various modifications may be made without departing from what is intended to be limited solely by the appended claims.