Cross-layer integrated collision free path routing

US 7,339,897 B2
Filed: 10/23/2002
Issued: 03/04/2008
Est. Priority Date: 02/22/2002
Status: Expired due to Fees

First Claim

Patent Images

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

jointly determining, for the purpose of configuring a connection, values of a set of connection parameters including i) a path defined by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, for optimization of the value of a single objective function with respect to said set of connection parameters, wherein said objective function depends on said set of connection parameters;

establishing a new connection based on the jointly determined values of said set of connection parameters, using the determined path for routing, the determined channel(s) for channel allocation and the determined physical link parameter value(s) for physical link adaptation,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm;

$K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant, where i≠

Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω

in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ

is one or a multitude of physical layer parameters, κ

_i(j, m, ψ

), also denoted κ

_ij(m, ψ

), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A true cross-layer integration of functions is provided on several protocol layers within a network, thus providing a unified approach to Quality of Service (QoS) provisioning in a multihop network. In the unified approach, 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. It is thereby possible to determine connection parameters that ensure substantially non-interfering communication with respect to existing connections as well as the new connection.

328 Citations

24 Claims

1. A method for connection set-up in a wireless communication network, said method comprising the steps of:
- jointly determining, for the purpose of configuring a connection, values of a set of connection parameters including i) a path defined by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, for optimization of the value of a single objective function with respect to said set of connection parameters, wherein said objective function depends on said set of connection parameters;
  
  establishing a new connection based on the jointly determined values of said set of connection parameters, using the determined path for routing, the determined channel(s) for channel allocation and the determined physical link parameter value(s) for physical link adaptation,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm;
  
  $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant, where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
- - 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 new 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 new 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 optimization is performed by means of a heuristic algorithm.
  - 7. The method according to claim 1, wherein said optimization is performed by means of a nested algorithm having nesting levels representing path assignment, channel allocation and physical link parameter adaptation, respectively.
  - 8. The method according to claim 1, wherein said optimization includes minimization of an objective cost function with respect to all of said connection parameters.
  - 9. The method according to claim 1, wherein a local search procedure is executed in each node i to evaluate the cost κ
    - _ij(m, ψ
      
      ) from node j to node i for all nodes j in said set N(i) of neighbors, and the least cost κ
      
      _ito each node i from the source node is determined based on said evaluation together with information on K_jreceived from each node j.
  - 10. The method according to claim 1, wherein the cost κ
    - _ij(m, ψ
      
      ) includes a channel-dependent physical link parameter ψ
      
      (m).
  - 11. The method according to claim 1, wherein the cost κ
    - _ij(m, ψ
      
      ) includes link transmit power P_j(m) for node j.
  - 12. The method according to claim 11, wherein the link transmit power P_j(m) is subjected to constraints restricting the link transmit power to a predetermined interval.
  - 13. The method according to claim 12, wherein the maximum permitted and minimum required link transmit power from node j are defined as:
14. The method according to claim 12, wherein the maximum permitted and minimum required link transmit power from node j are defined as:
- ${\overset{⋒}{P}}_{\max_{j}} (m) = \min {\begin{matrix} \min_{u \in N (j) \ {i}} {\frac{C_{u} (m) - Γ_{M} \cdot (I_{u} (m) + {\hat{I}}_{u} (m) + W}{Γ_{m} \cdot G_{ju} (m)}}, \\ \min_{r \in R} {\frac{{\hat{C}}_{r} (m) - Γ_{M} \cdot (I_{r} (m) + {\hat{I}}_{r} (m) + W)}{Γ_{m} \cdot G_{jr} (m)}} \end{matrix}}$ $\begin{matrix} {\overset{⋒}{P}}_{\min j} (m) = \frac{1}{G_{ji} (m)} \cdot (γ_{W} \cdot W + γ_{R} \cdot (\sum_{v \in N (i) \ {i}} P_{v} (m) \cdot G_{vi} (m) + \\ \sum_{r \in R} {\overset{⋒}{P}}_{r} (m) \cdot G_{ri} (m))), \end{matrix}$ where {circumflex over (P)}_r(m) and Ĉ
  
  _r(m) indicates estimated (or rather preliminary) transmit and receive power, respectively, for node r within set R denoting nodes along the preliminary path connected to node j, P_v(m) and C_u(m) on the other hand indicates transmit and receive power, respectively, for nodes with established traffic, G(m) is a respective channel gain matrix, Γ
  
  _Mis a CIR (Carrier Interference Ratio) threshold, assuming that each receiver part of an existing link or preliminary path experiences the interference level I(m), Î
  
  _x(m) is the expected interference at node x from nodes along the preliminary path, γ
  
  _Ris a receive factor, and W is a noise level using a factor γ
  
  _Wensure that one is generally interference limited rather than noise limited.
15. The method according to claim 1, further comprising the step of determining a preliminary shortest path prior to said optimization, and selecting said search region of node neighbors N(i) based on knowledge of said preliminary shortest path.
16. 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 preliminary connection and having a Route REPly (RREP) confirming a selected connection.
17. 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.

18. A method for determining a new connection in a wireless communication network, said method comprising the step of jointly determining, for the purpose of configuring said connection, the values of a set of connection parameters including i) a path defined by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, for optimization of the value of a single objective function with respect to said set of connection parameters, wherein said objective function depends on said set of connection parameters,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm:
- $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant;
  
  where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.
- View Dependent Claims (19)
- - 19. The method according to claim 18, wherein said optimization is subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the new connection as well as existing connections.

20. A method for connection admission control in a wireless communication network, said method comprising the steps of:
- performing, for a pending connection, optimization of the value of a single objective function with respect to a set of connection parameters including i) a path having a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, wherein said objective function depends on said set of connection parameters, and said optimization being subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to the pending connection as well as existing connections,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm;
  
  $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant, where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node;
  
  rejecting said pending connection if no set of connection parameters can be determined without violating said constraint;
  
  accepting said pending connection if a set of connection parameters can be determined without violating said constraint.
- View Dependent Claims (21)
- - 21. The method according to claim 20, wherein said at least one constraint includes an interference-related constraint designed to ensure substantially non-interfering links, including the links of the pending connection.

22. A control system for determining a connection in a wireless communication network, said control system comprising means for jointly determining, for the purpose of configuring said connection, values of a set of connection parameters including i) a path assembled by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, for optimization of a single objective function with respect to said set of connection parameters, wherein said objective function depends on said set of connection parameters,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm:
- $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant;
  
  where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.

23. A control system for connection set-up in a wireless communication network, said control system comprising:
- means for jointly determining, for the purpose of configuring a connection, values of a set of connection parameters including i) a path assembled by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, for optimization of a single objective function with respect to said set of connection parameters, wherein said objective function depends on said set of connection parameters; and
  
  means for establishing said connection based on the determined set of connection parameters, using the determined path for routing, the determined channel(s) for channel allocation and the determined physical link parameter value(s) for physical link adaptation,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm;
  
  $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant;
  
  where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.

24. A control system for connection admission control in a wireless communication network, said control system comprising:
- means for performing, for a pending connection, optimization of the value of a single objective function with respect to a set of variable connection parameters including i) a path assembled by a set of links, ii) at least one channel for each link, and iii) at least one physical link parameter, wherein said objective function depends on said set of connection parameters, and said optimization being subjected to at least one constraint designed to ensure substantially non-colliding communication with respect to said pending connection as well as existing connections,wherein said optimization includes a search procedure for finding a least cost K_ito each node i, in a given set, from the source node according to the following optimization algorithm;
  
  $K_{i} = \min_{j \in N (i)} {\min_{m \in {1, \dots, M)}} {\min_{ψ} {κ_{i} (j, m, ψ) + K (j)}}}$ K_{Source ID}=constant;
  
  where i≠
  
  Source ID, N(i) is a set of current neighbors of node i that in turn is a set of all nodes Ω
  
  in the network, j is a neighbor node belonging to N(i), m is a set of at least one channel in a set of M orthogonal channels in total, ψ
  
  is one or a multitude of physical layer parameters, κ
  
  _i(j, m, ψ
  
  ), also denoted κ
  
  _ij(m, ψ
  
  ), is the cost from node j to node i, and the term K(j), also denoted K_j, is the accumulated cost from the source node to node j, and K_{Source ID}is the initial cost at the source node.means for rejecting the pending connection if no set of connection parameters can be determined without violating said constraint;
  
  means for accepting the pending connection if a set of connection parameters can be determined without violating said constraint.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Telefonaktiebolaget LM Ericsson
Original Assignee
Telefonaktiebolaget LM Ericsson
Inventors
Johansson, Niklas, Larsson, Peter
Primary Examiner(s)
NGUYEN, HANH N

Application Number

US10/278,014
Publication Number

US 20030161268A1
Time in Patent Office

1,959 Days
Field of Search

370/329, 370/445, 370/447, 370/449, 370/450, 370/389, 370/351, 370/468, 370/395.1, 370/395.4, 370/395.41, 370/395.21, 370/443, 370/462, 370/252
US Class Current

370/252
CPC Class Codes

H04L 45/10   Routing in connection-orien...

H04W 40/16   based on interference

H04W 40/28   for reactive routing

H04W 52/46   in multi hop networks, e.g....

Y02D 30/70   in wireless communication n...

Cross-layer integrated collision free path routing

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

328 Citations

24 Claims

Specification

Solutions

Use Cases

Quick Links

Cross-layer integrated collision free path routing

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

328 Citations

24 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links