Cross-layer integrated collision free path routing

• US 20030161268A1
• Filed: 10/23/2002
• Published: 08/28/2003
• Est. Priority Date: 02/22/2002
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Larsson, Peter, Johansson, Niklas
• Granted Patent: US 7,339,897 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The invention generally represents a true cross-layer integration of functions on several protocol layers within the network, thus providing a unified approach to QoS provisioning in a multihop network. In the unified approach according to the invention, connections are preferably determined by integrated optimization of a given objective function with respect to connection parameters on at least three protocol layers within the network. Preferably, the optimization involves routing (path selection), channel access as well as adaptation of physical link parameters. By incorporating physical connection parameters together with properly designed constraints, the issue of interference can be carefully considered. This means that it is possible to determine connection parameters that ensure substantially non-interfering communication with respect to existing connections as well as the new connection.

Claims

1. A method for connection set-up in a communication network, said method comprising the steps of:

determining, for a requested connection, a set of connection parameters including path, channel and at least one physical link parameter by means of integrated optimization of a single objective function with respect to all of said connection parameters; and

establishing the requested connection based on the determined set of connection parameters.

2. The method according to claim 1, wherein said communication network is a wireless multihop network.

3. The method according to claim 1, wherein said optimization is subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the requested connection as well as existing connections.

4. The method according to claim 3, wherein said connection parameters are jointly determined under at least one interference-related constraint designed to ensure substantially non-interfering links, including the links of the requested connection.

5. The method according to claim 1, wherein said at least one physical link parameter is selected from the group of:

transmit power;

adaptive antenna (AA) parameters;

multiple-input-multiple-output (MIMO) parameters;

modulation parameters;

bandwidth;

data rate; and

error correction parameters.

6. The method according to claim 1, wherein said integrated optimization is performed by means of a heuristic algorithm.

7. The method according to claim 6, wherein the horizon over which the algorithm acts is selectable to provide optimum performance for a given acceptable level of computational complexity.

8. The method according to claim 1, wherein said integrated optimization is performed by means of a nested algorithm having nesting levels representing path assignment, channel allocation and physical link parameter adaptation, respectively.

9. The method according to claim 1, wherein said optimization includes minimization of an objective cost function with respect to all of said connection parameters.

10. The method according to claim 1, wherein said optimization includes a search procedure for finding a least cost K_i to each node i, in a given set, from the source node according to the following optimization algorithm:

11. The method according to claim 10, wherein a local search procedure is executed in each node i to evaluate the cost K_ij (m, ψ

) from node j to node i for all nodes j in said set N(i) of neighbors, and the least cost K_i to each node i from the source node is determined based on said evaluation together with information on K_j received from each node j.

12. The method according to claim 10, wherein the cost K_ij (m, ψ

) includes a channel-dependent physical link parameter ψ

(m).

13. The method according to claim 10, wherein the cost K_ij (m, ψ

) includes link transmit power P_j(m) for node j.

14. The method according to claim 13, wherein the link transmit power P_j(m) is subjected to constraints restricting the link transmit power to a predetermined interval.

15. The method according to claim 14, wherein the maximum permitted and minimum required link transmit power from node j are defined as:

16. The method according to claim 14, wherein the maximum permitted and minimum required link transmit power from node j are defined as:

17. The method according to claim 10, further comprising the step of determining a preliminary shortest path prior to said integrated optimization, and selecting said search region of node neighbors N(i) based on knowledge of said preliminary shortest path.

18. The method according to claim 1, wherein on-demand routing is deployed, having a Resource REQuest (RREQ) conveying path, channel and physical link parameters for a requested preliminary connection and having a Route REPly (RREP) confirming a selected connection along a corresponding path.

19. The method according to claim 1, wherein on-demand routing is deployed, having a Resource REQuest (RREQ) collating information on existing connections when said RREQ is forwarded through the network, and determining, at a destination node, a new connection fulfilling a Quality of Service (QoS) requirement as contained in said RREQ based on said collated information.

20. A method for determining a connection in a communication network, said method comprising the step of determining, for said connection, a set of connection parameters including path, channel and at least one physical link parameter by means of integrated optimization of a single objective function with respect to all of said connection parameters.

21. The method according to claim 20, wherein said optimization is subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the requested connection as well as existing connections.

22. A method for connection admission control in a communication network, said method comprising the steps of:

performing, for a requested connection, integrated optimization of a single objective function with respect to a set of connection parameters including path, channel and at least one physical link parameter, said optimization being subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the requested connection as well as existing connections;

rejecting the requested connection if no set of connection parameters can be determined without violating said constraint;

accepting the requested connection if a set of connection parameters can be determined without violating said constraint.

23. The method according to claim 22, wherein said at least one constraint includes an interference-related constraint designed to ensure substantially non-interfering links, including the links of the requested connection.

24. A method for determining a connection in a communication network, said method comprising the step of determining said connection by means of optimization of a single objective function with respect to connection parameters on at least three protocol layers within the network.

25. The method according to claim 24, wherein said communication network includes a wireless multihop network, and said connection parameters include parameters on at least three protocol layers within said wireless multihop network.

26. The method according to claim 24, wherein said at least three protocol layers include the network layer, the link layer and the physical layer.

27. The method according to claim 26, wherein said at least three protocol layers further include the application layer.

28. The method according to claim 24, wherein said optimization is subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the requested connection as well as existing connections.

29. The method according to claim 24, wherein said connection is defined by at least a triplet comprising a selected path, a selected orthogonal resource such as a channel, and one or more selected physical link parameters.

30. The method according to claim 24, wherein said algorithm is a nested algorithm, where each nesting level represents a network protocol layer.

31. A control system for determining a connection in a communication network, said control system comprising means for determining, for said connection, a set of connection parameters including path, channel and at least one physical link parameter by means of integrated optimization of a single objective function with respect to all of said connection parameters.

32. A control system for connection set-up in a communication network, said control system comprising:

means for determining, for a requested connection, a set of connection parameters including path, channel and at least one physical link parameter by means of integrated optimization of a single objective function with respect to all of said connection parameters; and

means for establishing the requested connection based on the determined set of connection parameters.

33. A control system for connection admission control in a communication network, said control system comprising:

means for performing, for a requested connection, integrated optimization of a single objective function with respect to a set of connection parameters including path, channel and at least one physical link parameter, said optimization being subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the requested connection as well as existing connections;

means for rejecting the requested connection if no set of connection parameters can be determined without violating said constraint;

means for accepting the requested connection if a set of connection parameters can be determined without violating said constraint.

34. A control system for determining a connection in a communication network, said control system comprising means for determining said connection by means of optimization of a single objective function with respect to connection parameters on at least three protocol layers within the network.