The invention concerns routing, scheduling, and power control methods for single and multi-hop wireless networks. A multi-hop network is one in which source and destination nodes may communicate directly or through relay nodes. Nodes in single hop networks communicate without use of relay nodes. Emb
The invention concerns routing, scheduling, and power control methods for single and multi-hop wireless networks. A multi-hop network is one in which source and destination nodes may communicate directly or through relay nodes. Nodes in single hop networks communicate without use of relay nodes. Embodiments of the invention may produce an optimal schedule to provide for the best-case goal for a given parameter. In a preferred embodiment, total power is the parameter and total power is minimized for the network. In another preferred embodiment, data throughput is the parameter, and throughput is maximized for the network.
대표청구항▼
The invention claimed is: 1. A method for scheduling communication in a wireless communications network, the network having a plurality of nodes, the method comprising steps of: measuring channel parameters between arbitrary nodes in the wireless communications network; for each possible transmissi
The invention claimed is: 1. A method for scheduling communication in a wireless communications network, the network having a plurality of nodes, the method comprising steps of: measuring channel parameters between arbitrary nodes in the wireless communications network; for each possible transmission mode, identifying a signal to interference plus noise ratio based upon the measured channel parameters; mapping the signal to interference plus noise ratio into a data rate for the transmission modes; from a subset of transmission modes that result from the step of mapping, determining which of all of the transmission modes may be scheduled for one of to meet minimum data rate constraints between links and minimize total average power, or to maximize total throughput while meeting a maximum power constraint on each link in the network; and choosing path flows for routing communications through the links scheduled by said step of determining, and wherein said step of choosing paths comprises: determining an initial set of path flows between sources and destinations, and calculating a data rate carried on each link of the network to define a set of data rates; for the set data rates, minimizing total power and calculating a resulting link sensitivity of the total power to a change in the data rate on each link to define calculated link sensitivity parameters; using the calculated link sensitivity parameters to produce adjusted path flows; re-calculating the carried data rate on each link for adjusted path flows, and recalculating the link sensitivity parameters; iteratively repeating, if necessary, said steps of adjusting and re-calculating until total power used is acceptably small. 2. The method of claim 1, wherein said step of measuring measures channel parameters between all nodes in the wireless communication network. 3. The method of claim 1, wherein said step of measuring measures channel parameters between a subset of all of the nodes in the communication network, including nodes having no communication link at the time of measuring. 4. The method of claim 1, wherein said step of determining comprises: applying a linear program constrained by the minimum data rates between links and the transmitting power of nodes. 5. The method of claim 1, wherein said step of determining determines the links that define a transmission mode, and the duty cycle for each transmitting node in the transmission mode. 6. The method of claim 5, wherein a transmission mode determined in said step of determining further comprises a transmission power and data rate for each of the links. 7. The method of claim 1, applied in a hierarchal manner and carried out on a cluster of links, further comprising the steps of dividing a set of links into clusters, and carrying out said steps of measuring and determining for each cluster. 8. The method of claim 7, wherein inter-cluster interference is modeled as static ambient noise. 9. The method of claim 8, wherein interaction between clusters is modeled with a fixed-point equation that determines the level of inter-cluster interference. 10. The method of claim 1, carried out by a node in the network. 11. A method for scheduling communication in a wireless communications network, the network having a plurality of nodes, the method comprising steps of: measuring channel parameters between arbitrary nodes in the wireless communications network; for each possible transmission mode, identifying a signal to interference plus noise ratio based upon the measured channel parameters; mapping the signal to interference plus noise ratio into a data rate for the transmission modes; and from a subset of transmission modes that result from the step of mapping, determining which of all of the transmission modes may be scheduled for one of to meet minimum data rate constraints between links and minimize total average power, or to maximize total throughput while meeting a maximum power constraint on each link in the network; wherein said step of determining comprises application of a convex duality calculation; wherein the convex duality calculation comprises: defining a numerical value for each transmission mode in the subset of transmission modes, wherein the numerical value is the sum of powers for each link plus a difference term for each link, and wherein each difference term is equal to a difference between a required minimum data rate on the link and an associated data rate on the link for a given transmission mode, and wherein difference terms summed in the numerical value are weighted in proportion to corresponding dual variables defined for each link; restating a modified optimization criteria defined as the smallest numerical value from said step of defining, over the set of transmission modes in the subset of transmission modes; determining optimal values for the dual variables which maximize the modified optimization criteria; determining a set of transmission modes whose associated numerical values achieve the minimum in the modified optimization criteria, wherein the dual variables are set to optimal values as determined in said step of determining optimal values. 12. A method for scheduling communication in a wireless communications network, the network having a plurality of nodes, the method comprising steps of: measuring channel parameters between arbitrary nodes in the wireless communications network; for each possible transmission mode, identifying a signal to interference plus noise ratio based upon the measured channel parameters; mapping the signal to interference plus noise ratio into a data rate for the transmission modes; from a subset of transmission modes that result from the step of mapping, determining which of all of the transmission modes may be scheduled for one of to meet minimum data rate constraints between links and minimize total average power, or to maximize total throughput while meeting a maximum power constraint on each link in the network; specifying a traffic matrix wherein each element in the matrix comprises a rate of data traffic to be moved between a transmitting node and a receiving node; testing a candidate routing using the traffic matrix to induce a data rate on each link; scheduling according to said steps of measuring, identifying, mapping and determining to determine transmission power and link sensitivity parameters indicating sensitivity of total power to changes in data rate on each link; iteratively searching for a routing to reduce average power. 13. The method of claim 12, wherein the value of link sensitivity parameters are determined by steps comprising: defining a numerical value for each transmission mode in the subset of transmission modes, wherein the numerical value is the sum of powers for each link plus a difference term for each link, and wherein each difference term is equal to a difference between a required minimum data rate on the link and an associated data rate on the link for a given transmission mode, and wherein difference terms summed in the numerical value are weighted in proportion to a dual variable defined for each link; restating a modified optimization criteria defined as the smallest numerical value from said step of defining over the set of transmission modes in the subset of transmission modes; determining optimal values for the dual variables which maximize the modified optimization criteria; determining a set of transmission modes whose associated numerical values achieve the minimum in the modified optimization criteria, wherein the dual variables are set to optimal values as determined in said step of determining a set of transmission modes, such that the sensitivity value for each link is equal to the optimal value of respective dual variable determined by said step of determining optimal values for the dual variables. 14. A method for routing information through a wireless communication network, the network having a plurality of nodes and a plurality of potential links between the nodes, the method comprising steps of: determining a traffic matrix that specifies the rate of information transport between each pair of nodes in the network; setting an initial routing of traffic on said links of the network in order to support the traffic matrix determined in said step of determining a traffic matrix; determining required data rates on the links of the wireless communication network for the initial routing of traffic set in said step of setting; computing a sensitivity of links in response to change of data rate; iteratively adjusting the routing of traffic using the sensitivity of links so that the weighted sum of expended transmission powers across the links of the network is reduced and repeating said steps of determining and computing, wherein said step of computing computes a sensitivity parameter for all links in the network; wherein the value of link sensitivity parameters are determined by steps comprising: defining a numerical value for each transmission mode in the subset of transmission modes, wherein the numerical value is the sum of powers for each link plus a difference term for each link, and wherein each difference term is equal to a difference between a required minimum data rate on the link and an associated data rate on the link for a given transmission mode, and wherein difference terms summed in the numerical value are weighted in proportion to a dual variable defined for each link; restating a modified optimization criteria defined as the smallest numerical value from said step of defining over the set of transmission modes in the subset of transmission modes; determining optimal values for the dual variables which maximize the modified optimization criteria; determining a set of transmission modes whose associated numerical values achieve the minimum in the modified optimization criteria, wherein the dual variables are set to optimal values as determined in said step of determining optimal values; such that the sensitivity value for each link is equal to the optimal value of a respective dual variable determined by said step of determining optimal values for the dual variables. 15. The method of claim 14, wherein said step of iteratively adjusting and repeating is repeated until the weighted sum of expended transmission powers does not significantly change in response to adjusting the routing.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (9)
Hostetter George R. (Santa Clara CA) Babitch Daniel (San Jose CA), Code position modulation system and method for multiple user satellite communications.
Amadon,Gregory; Sowizral,Henry Adam; Zikan,Karel, Network traffic director system having modules that implement merit or penalty functions involving stochastic changes in network topology.
Persson Anders H.ang.kan,SEX ; Butovitsch Paul Peter,SEX ; Thornberg Carl Magnus,SEX ; Turcotte Joseph Eric,CAX ; Rahman Anisur M., Power presetting in a radio communication system.
Persson Anders H.ang.kan,SEX ; Butovitsch Paul Peter,SEX ; Thornberg Carl Magnus,SEX ; Turcotte Joseph Eric,CAX ; Rahman Anisur M., Power presetting in a radio communication system.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.