Routing apparatus and method for multi-hop cellular systems

• US 20080085702A1
• Filed: 09/14/2007
• Published: 04/10/2008
• Est. Priority Date: 11/10/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Yongsuk, Jung, Eun Sun, Bang, Jong Ho
• Granted Patent: US 8,755,786 B2
• Time in Patent Office: Days
• US Class Current: 455/422.1
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A routing method in a multi-hop cellular system, the method including: maintaining a signal strength in each node included in the multi-hop cellular system; receiving, in at least one neighbor node, a route-request message broadcasted by a source node; dropping or re-broadcasting, by the at least one neighbor node, the route-request message based on a hop count and the signal strength; and storing, in a base station, the route-request message which is received via the at least one neighbor node, based on an elapsed time, or transmitting a route-reply message to the source node via an optimal path which is selected via the stored route-request message.

Claims

1. A routing method in a multi-hop cellular system, the method comprising:

maintaining a signal strength in each node included in the multi-hop cellular system;

receiving, in at least one neighbor node, a route-request message broadcasted by a source node;

dropping or re-broadcasting, by the at least one neighbor node, the route-request message based on a hop count and the signal strength; and

storing, in a base station, the route-request message which is received via the at least one neighbor node, based on an elapsed time, or transmitting a route-reply message to the source node via an optimal path which is selected via the stored route-request message.

2. The method of claim 1, wherein the signal strength corresponds to a signal strength level from the each node to the base station.

3. The method of claim 1, wherein the route-request message comprises a source address of the source node, an address of a previous node, the hop count, and the signal strength corresponding to a signal strength level from the node to the base station.

4. The method of claim 1, wherein the dropping or re-broadcasting comprises:

setting the hop count and the signal strength included in the route-request message as a first hop count and a first signal strength, respectively;

confirming whether the route-request message is a first route-request message transmitted from the source node;

setting a hop count of the previously received route-request message and a signal strength of the neighbor node as a second hop count and a second signal strength, respectively, when the route-request message is different from the first route-request message, and setting the second hop count to infinity when the route-request message is the first route-request message;

confirming whether the first hop count is less than the second hop count and the first signal strength is less than the second signal strength included in the neighbor node; and

updating the second hop count and the first signal strength and re-broadcasting the route-request message after increasing and updating the first hop count, when the first hop count is less than the second hop count and the first signal strength is less than the second signal strength included in the neighbor node, and dropping the route-request message when the first hop count is greater than or equal to the second hop count and the first signal strength is greater than or equal to the second signal strength included in the neighbor node.

5. The method of claim 4, wherein the updating and re-broadcasting comprises:

updating the second hop count of the neighbor node with the first hop count;

updating the first signal strength of the route-request message with the second signal strength;

increasing and updating the first hop count of the route-request message; and

re-broadcasting the route-request message in which the signal strength and the hop count are updated.

6. The method of claim 1, wherein the storing or transmitting comprises:

measuring and maintaining the elapsed time with respect to the route-request message which is first transmitted, from among the route-request message including a source address of the source node;

storing the first transmitted route-request message until the elapsed time exceeds a predetermined waiting time; and

selecting the optimal path based on the stored route-request message, and transmitting the route-reply message via the optimal path, when the elapsed time exceeds the predetermined waiting time.

7. The method of claim 6, wherein the selecting of the optimal path and the transmitting of the route-reply message comprises:

comparing the hop count included in the route-request message and selecting the optimal path;

updating a routing table included in the base station via the optimal path; and

transmitting the route-response message via the optimal path.

8. The method of claim 7, wherein the routing table comprises a destination address, a subsequent hop, and a most recent usage time, and the base station stores other paths in the routing table and removes a path which is least recently used, based on the most recent usage time, when storage space with respect to the optimal path is insufficient.

9. A computer-readable recording medium of instructions for controlling a base station and nodes included in a multi-hop cellular system to implement a routing method, the instructions comprising:

a first set of instructions for controlling each node included in the multi-hop cellular system to maintain a signal strength;

a second set of instructions for controlling at least one neighbor node to receive a route-request message broadcasted by a source node;

a third set of instructions for controlling the at least one neighbor node to drop or re-broadcast the route-request message based on a hop count and the signal strength; and

a fourth set of instructions for controlling the base station to store the route-request message which is received via the at least one neighbor node, based on an elapsed time, or to transmit a route-reply message to the source node via an optimal path which is selected via the stored route-request message.

10. A multi-hop cellular system comprising:

a source node for broadcasting a route-request message to at least one neighbor node;

the at least one neighbor node for dropping or re-broadcasting the route-request message based on a hop count and a signal strength included in the route-request message; and

a base station for storing the route-request message, which is received via the at least one neighbor node, based on an elapsed time, or for transmitting a route-reply message to the source node via an optimal path which is selected via the stored route-request message.

11. The system of claim 10, wherein the signal strength corresponds to a signal strength level from any one of the source node and the neighbor node to the base station.

12. The system of claim 10, wherein the route-request message comprises a source address of the source node, an address of a previous node, the hop count, and the signal strength corresponding to a signal strength level from the node to the base station.

13. The system of claim 10, wherein the neighbor node comprises:

a setting unit for setting the hop count and the signal strength included in the route-request message as a first hop count and a first signal strength, respectively;

a second hop count setting unit for setting a hop count of the previously received route-request message and a signal strength of the neighbor node as a second hop count and a second signal strength, respectively, when the route-request message is different from the first route-request message, and for setting the second hop count to infinity when the route-request message is the first route-request message;

a comparison unit for confirming that the first hop count is less than the second hop count and the first signal strength is less than the second signal strength included in the neighbor node; and

a route-request message processing unit for updating the second hop count and the first signal strength and re-broadcasting the route-request message after increasing and updating the first hop count, when the first hop count is less than the second hop count and the first signal strength is less than the second signal strength included in the neighbor node, and for dropping the route-request message when the first hop count is greater than or equal to the second hop count and the first signal strength is greater than or equal to the second signal strength included in the neighbor node.

14. The system of claim 10, wherein the base station comprises:

an elapsed time measurement and maintenance unit for measuring and maintaining the elapsed time with respect to the route-request message which is first transmitted, from among the route-request message including a source address of the source node;

a route-request message storage unit for storing the first transmitted route-request message until the elapsed time exceeds a predetermined waiting time;

a path selection unit for selecting the optimal path based on the stored route-request message, when the elapsed time exceeds the predetermined waiting time; and

a route-reply message transmission unit for transmitting the route-reply message to the source node via the optimal path.