Method and apparatus of fully distributed packet scheduling for a wireless network

The present invention relates to a method and apparatus of fully distributed packet scheduling for a wireless network.

The packet scheduling algorithm in a wireless multihop network is usually central-unit processing-based. This type of algorithm, although effective, is costly in terms of computing complexity and not scalable with the network size and the traffic demand. This type of algorithm requires sending every possible combination of transmission and receiving and the corresponding signal-to-noise-ratio (SNR) to the base station (BS), and uses a brutal force method to find the optimal combination. In an actual system, it is difficult to estimate the SNR, not to mention the SNR for all the combinations. Besides, the SNR estimation is only the beginning. The real computation is in the central-unit processing-based packet scheduling.

In a multi-hop wireless network, a relay is for storing and forwarding the packets received at BS to the network node of the mobile station (MS), and vice versa. In other words, the MS in a multi-hop wireless network can also transmit packets from a BS to a relay, and packets from a relay to an MS.

A relay network is a network that has relays between the BS and the MS. There are several advantages of a relay network. The distance of the transmit-receive pair is shorter, and the required transmission power can be reduced in order to expand the service coverage area. The network throughput is therefore increased because the BS, MS, and relay are allowed to transmit packets simultaneously. The channel reuse is also possible by spatial multiplexing technique.

FIG. 1A shows a schematic view of a conventional single cell multihop wireless network. The wireless network includes a base station BS, two relays R 1 , R 2 , and four users (mobile station) M 1 -M 4 . FIG. 1B shows a schematic view of a conventional multiple-cells multi-hop wireless network. The wireless network includes three base stations BS 1 -BS 3 , four relays R 1 -R 4 , and eight users M 1 -M 8 . In FIGS. 1A & 1B , the variable v j on each network link indicates whether the network link is currently transmitting.

However, if the packets for transmission are not appropriately scheduled, each advantage of using a relay is also accompanied by side effects. For example, when the service coverage area is expanded, the packets from MS are moving among several relays before they reach their destination. Therefore, if the relays do not schedule the packet transmission carefully, the wireless network resources may be wasted. On the other hand, as the simultaneous packet transmission is allowed in a multihop wireless network, the frequent data packet collision may occur. In this case, the performance will greatly decrease.

A good packet scheduling technique not only requires the avoidance of packet collision, but also exploits the spatial reuse characteristics of the multihop wireless network in order to maximize the system throughput. As shown in FIG. 1A , if the outcome of the packet scheduling algorithm is {v 1 , v 2 , v 3 , . . . , v 10 }={0,1,0,0,1,0,0,0,0,1}, instead of {0,1,0,0,0,0,0,0,0,0}, where v j =1 indicates the network link is currently transmitting, and v j =0 indicates that the network link is not transmitting, the network overall performance is better. This is because the first schedule includes three network links transmitting, while the second schedule only has one link transmitting. It is also worth noticing that the schedule {0,1,0,0,0,0,0,1,1,0} is not an effective schedule as the three packets transmitting to the user M 3 will collide.

The present invention provides a method and apparatus of fully-distributed packet scheduling for a wireless network to effectively solve the side effects associated with conventional packet scheduling algorithms in a multi-hop wireless network.

The present invention is based on the factor graph and a sum-product algorithm to apply a low-density parity-check (LDPC) code decoding algorithm to a multihop wireless network to achieve the packet scheduling. The factor graph is a schematic view of the multi-hop wireless network, and the neighboring base stations and mobile users use the sum-product algorithm for communication.

Accordingly, the packet scheduling method of the present invention includes the following three steps: (a) constructing a factor graph to model a multi-hop wireless network; (b) based on the factor graph, transforming the packet scheduling problem into a LDPC code decoding problem and using a standard process to solve the decoding problem; and (c) weighting the packet schedule in accordance with the network condition.

The fully-distributed packet scheduling apparatus of the present invention includes a network modeling unit, a packet scheduling unit and a weighting scheme to realize the fully distributed packet scheduling method.

The foregoing and other features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings.

FIG. 1A shows a schematic view of a conventional single cell multihop wireless network.

FIG. 1B shows a schematic view of a conventional multi-cell multihop wireless network.

FIG. 2 shows a flowchart of the full-distributed packet scheduling method of the present invention in a relay network.

FIG. 3A shows a factor graph of FIG. 1A .

FIG. 3B shows a factor graph of FIG. 1B .

FIG. 4A shows the factor graph of FIG. 3A with information on the packet queue length of each network link, using downlink for communication.

FIG. 4B shows the factor graph of FIG. 3A with information on the packet queue length of each network link, using uplink for communication.

FIG. 5 shows a schematic view of an apparatus realizing FIG. 3 .

FIG. 6 shows the comparison between the present and the RR and IP in terms of average transmission rate in each packet slot with uplinks for communication in a single cell multihop wireless network.

FIG. 7 shows the average transmission rates of mobile stations in each packet slot with uplinks for communication in a multicell multihop wireless network.

In FIG. 1A , it can be observed that the packet scheduling problem can be transformed into a decoding problem for low-density parity-check (LDPC) code as long as the packet scheduling problem can be described by a factor graph model, and the constrain rules are defined for the variable vj on each network link. A standard process commonly known as sum-product algorithm can solve the decoding problem for LDPC code. To fully explore the network resources, the present invention designs a weighting scheme so that the user with more packets has a higher priority for transmission.

FIG. 2 shows a flowchart of the fully-distributed packet scheduling method of the present invention. First, step 201 is to construct a factor graph to model a multi-hop wireless network. The factor graph includes a plurality of agent nodes, a plurality of variable nodes and a plurality of edges. The factor graph is a mutually-interactive graph. Step 202 is to transform the packet scheduling problem into a decoding problem for LDPC code based on the factor graph, and use a standard process to solve the decoding problem. In other words, the sum-product algorithm is used as a tool for an access point (AP) to communicate with the neighboring APs. Step 203 is to apply a weighting scheme on the packet schedule according to the network condition at that time.

The construction of factor graph in step 201 can be implemented with the following three steps.

(a) An agent node is used to represent each network node. Each agent node is marked with the corresponding constrain function f i , which defines an interference-avoiding local constrain rule.

(b) A variable node is used to represent a network link. Each variable node is marked with a variable v j .

(c) Each variable node is linked to two agent nodes, where the network nodes corresponding to the two agent nodes can communicate through the network link corresponding to the variable node.

To improve the utilization of the network resource, the present invention uses the link communication to repeatedly exchange the soft-information of the probability mass function (pmf) of each variable node between the neighboring network nodes and variable nodes.

Taking FIG. 1A as an example, FIG. 3A shows a factor graph of a single cell network constructed by using the above three steps. Taking FIG. 1B as an example, FIG. 3B shows a factor graph of a multi-cell network constructed by using the above three steps.

To meet the basic multi-hop wireless network and the interference-avoiding local constrain rules, each network node must obey the following rules during each packet slot.

(a) A network node can only transmit to one network node during transmission.

(b) A relay cannot transmit and receive packets simultaneously.

(c) A network node cannot receive packets from multiple sources simultaneously.

In other words, when executing the interference-avoiding local constrain rule and sum-product convergence, each agent node in the example in FIG. 3A must obey the following constrain rules:

ƒ 1 : v 1 +v 2 +v 3 +v 4 ≦1; and

ƒ 2 : v 1 +v 5 +v 6 +v 8 ≦1; ƒ 3 : v 3 +v 7 +v 9 +v 10 ≦1; and

ƒ 4 : v 5 ≦1; ƒ 5 : v 6 +v 7 =1; and

ƒ 6 : v 2 +v 8 +v 9 ≦1; ƒ 7 : v 4 +v 10 ≦1.

That is, the variables surrounding each agent node form a valid local transmission pattern. In the example in FIG. 3A , the valid local transmission pattern is: for BS, {v 1 , v 2 , v 3 , v 4 }={(0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}; and for M 3 , {v 2 , v 8 , v 9 }={(0,0,0), (1,0,0), (0,1,0), (0,0,1)}, and so on. The collection of all the valid local transmission patterns forms a valid global collision-free schedule.

It is worth noticing that the interference-avoiding local constrain rules can be applied to both single cell and multi-cell multihop wireless network.

The following describes how to compute and transport the soft-information that can improve the network resource utilization. The soft-information shows the probability that each network link will be utilized in each packet slot.

First, the probability P b (v j ) of each variable node v j (v j =b, b is 0 or 1) is initialized. Then, the soft-information SI st (x, y, b) of each agent node (marked by the corresponding constrain function ƒ i ) linking to each variable node v j , where P 1 (v j ) is uniformly distributed between (0,1), and P 0 (v j )+P 1 (v j )=1. SI st (x, y, b) represents the soft-information transported from node x to node y, and indicates the probability when the corresponding variable node v j is b. The subscript s is the packet slot index, t is the iteration index. The initialized probability P b (v j ) is the probability randomly assigned to each variable node v j .

It is worth noticing that the initialized P b (v j ) can be added through the network link corresponding to the variable node v j to one of the two agent nodes linking the variable node.

Then, according to the standard sum-product algorithm, the soft-information SI st (x, y, b) transported from variable node v j to agent node (mark by the corresponding constrain function ƒ i ) can be computed. Taking variable node v 1 and agent node f 2 as an example, the soft-information is computed as SI st (v 1 , ƒ 2 , b)=c 1,2 P b (v 1 )·SI (s−1)t (ƒ 1 , v 1 , b), where c 1, 2 is a normalizing factor to make SI st (v 1 , ƒ 2 , 0)+SI st (v 1 , ƒ 2 , 1)=1.

Furthermore, in addition to weighting each valid local transmission pattern, the same sum-product algorithm is used to compute the soft-information transported from agent node (mark by the corresponding constrain function ƒ i ) to variable node v j . The agent node (mark by the corresponding constrain function ƒ i ) collects all the incoming soft-information from its neighboring variable nodes {V h }, and computes the soft-information SI st (ƒ i , v j , b) to be transported to variable node v j . Taking BS as an example, the soft-information is computed as SI st (ƒ 1 , v 1 , 1)=d 1,1 {ω t (ƒ 1 , 1000))·SI st (v 2 , ƒ 1 , 0) SI st (v 3 , ƒ 1 , 0) SI st (v 4 , ƒ 1 , 0)}, where d 1,1 is a normalizing factor.

The total soft-information SI st (v j , b) of variable node v j can be computed as the product of all the soft-information SI st (ƒ i , v j , b), where ƒ i belongs to the set of all the agent nodes linking to variable node v j .

It is worth noticing that the above soft-information computation of variable node v j can be applied to both single cell and multi-cell multihop wireless network. After the second iteration, if SI st (v j , 1)≧SI st (v j , 0), variable node v j is determined to be active; that is v j =1; otherwise, v j =0. When all the variable nodes v j follow the interference-avoiding local constrain rule, the standard sum-product algorithm terminates and outputs a valid global schedule. Otherwise, the agent nodes not following the interference-avoiding local constrain rule must repeat the above sum-product computation.

A multihop wireless network may prefer a certain interference-avoiding or collision-free packet scheduling method to others because the former can maximize the reuse of the network resources. For example, in a single cell multihop wireless network, the service provider can prefer the global schedule {v j }={0,1,0,0,1,0,0,0,0,1}, instead of the global schedule {v j }={0,1,0,0,0,0,0,0,0,0} because the former can reuse the network resource more effectively, even though both are valid interference-avoiding or collision-free scheduling techniques.

Therefore, to improve the network resource utilization, the present invention based on the network condition at the time, such as urgency and transmission rate of each network link, weights each valid local transmission pattern. Without the loss of generality, the present invention uses a single cell multihop wireless network as an embodiment for explanation. However, the weighting scheme is also applicable to a multi-cell multi-hop wireless network.

For agent node ƒ i , the information on the packet queue length of the neighboring agent nodes are collected, and the weight of local transmission pattern of the k-th local link of each agent node ƒ i is computed as follows:

ω ⁢ ⁢ t ⁡ ( f i , { 0 , … ⁢ , 0 , 1 , 0 , … ⁢ , 0 } ) = sum ⁢ ⁢ of ⁢ ⁢ { max ⁡ ( x T , t ⁡ ( k ) - x R , t ⁡ ( k ) , 0 ) / max ⁡ ( x T , t ⁡ ( h ) - x R , t ⁡ ( h ) , ɛ ) } ,

where max is the maximum function, ε is a positive number, h is not equal to k, ƒ h belongs to the set of all the variable nodes linking to the agent node ƒ i , and x T,t (k) and x R,t (k) are the total number of packets that can reach the destination queue through the k-th local link of agent node ƒ i , where subscripts T and R are the transmitting end and the receiving end of the local link, and t is the concerned packet slot index.

FIG. 4A is the factor graph of FIG. 3A with information on the packet queue length of each network link, using downlink for communication. The weight of local transmission pattern {v 1 , v 2 , v 3 , v 4 } of BS (agent node ƒ 1 ) is computed as follows:

;

;

;

=

The weighting of relay is the same as the weighting of BS, except that the weight of the link that is in use and is the only link to the BS is set to be 1. Therefore, the weight of local transmission pattern {v 1 , v 5 , v 6 , v 8 } corresponding to agent node ƒ 2 is computed as follows: ω t (ƒ 2 , {1,0,0,0})=1; ω t (ƒ 2 , {0,1,0,0})=⅚+ 5/3=2.5; ω t (ƒ 2 , {0,0,1,0}) = 6/5+ 6/3=3.2; and ω 2 (ƒ 2 , {0,0,0,1})=⅗+ 3/6=1.1.

The weighting of the uplinks is the same as the weighting of the downlinks, except that the transmission direction is reverse, and the packet destination is BS. FIG. 4B is the factor graph of FIG. 3A with information on the packet queue length of each network link, using uplink for communication. The weight of local transmission pattern {v 1 , v 2 , v 3 , v 4 } of BS (agent node f i ) is computed as follows:

The weight of non-zero local transmission pattern {v 1 , v 5 , v 6 , v 8 } of agent node ƒ 2 is computed as follows: ω t (ƒ 2 , {1,0,0,0})=1; ω t (ƒ 2 , {0,1,0,0})=(9−7)/ε+(9−7)/(8−7)=2(ε+1); ω t (ƒ 2 , {0,0,1,0})=0/(9−7)=0; and ω t (ƒ 2 , {0,0,0,1})=(8−7)/(9−7)+(8−7)/ε=ε+0.5.

The weight of non-zero local transmission pattern {v 2 , v 8 , v 9 } of agent node f 2 is computed as follows: ω t (ƒ 6 , {1,0,0})=ω t (ƒ 6 , {1,0,0})=ω t (ƒ 6 , {1,0,0})=1.

As shown in the above description, the present invention does not need to estimate the SNR. It is only necessary for the neighboring wireless APs to reach a consensus. The weighting scheme of the present invention is natural-competition-based. When the packet queue length of the transmitting end is longer than the packet queue length of the receiving end, the corresponding network link is more likely to be activated for use because the weight of transmission pattern activating the network link is increased. This characteristic allows the urgent packets having a higher priority, and prevents the packet queue from overflowing on any network node. On the other hand, when the packet queue length of the receiving end is longer than the packet queue length of the transmitting end, the corresponding network link is more likely to be deactivated because the weight of transmission pattern activating the network link is set to 0. Stopping the network link prevents the packet queue from overflowing on any network node, and gives more time for the relay to consume the packets.

It is worth noticing that weighting scheme of the present invention is also applicable to a multi-cell multihop wireless network.

In accordance with the above fully-distributed packet scheduling method for a wireless network, FIG. 5 shows a block diagram of the apparatus realizing the fully-distributed packet scheduling method. As shown in FIG. 5 , the apparatus includes a network modeling unit 501 , a packet scheduling unit 503 and a weighting mechanism 505 . Network modeling unit 501 is to model a multi-hop wireless network with a factor graph. As aforementioned, the factor graph includes a plurality of agent nodes, a plurality of variable nodes and a plurality of edges. The factor graph is bounded by a group of mutually-interactive constrain rules. Based on the factor graph, packet scheduling unit 503 transforms the packet scheduling problem into a decoding problem of LDPC code, and uses a standard process to solve the decoding problem. Weighting mechanism 505 weights the packet schedule solved by the decoding problem according to the network condition at the time.

The correspondence between the factor graph and the wireless network is described earlier in the construction of factor graph, and therefore, is omitted here.

The present invention is also compared with two conventional packet scheduling techniques, namely, round-robin (RR) and individual-polling (IP). RR and IP are both central-unit-processing-based packet scheduling methods. In RR, all the links of the network are activated in turn with a pre-determined order, while the local link between BS and relay is activated in an order that is determined individually in IP.

FIG. 6 shows the comparison between the present and the RR and IP in terms of average transmission rate in each packet slot, and the uplinks are used for communication in a single cell multihop wireless network. The x-axis is the mean of packet arrival rates λ, and the y-axis is the average of transmission rates in each packet slot.

As shown in FIG. 6 , when the traffic load in the network is less than the capacity of the system (i.e., λ≦0.5), the weighting scheme of the present invention helps to maintain the fairness of packet transmission rate among all the mobile stations, regardless of the network resources used by each mobile station. Because of the fairness of transmission pattern, the priority of the urgent packets is raised. The fairness of packet scheduling can be seen in the standard deviation (STD) at upper left corner of the table.

When the traffic load in the network is gradually greater than the capacity of the system (i.e., λ≧0.5), the present invention releases the network resource of M 1 to help other mobile stations to survive under the heavier traffic load.

Therefore, the average transmission rate in each packet slot and the difference among the users are far better than the two conventional packet scheduling methods.

FIG. 7 shows the average transmission rates of M 1 -M 8 in each packet slot with uplinks for communication in a multi-cell multi-hop wireless network. The x-axis is the mean of packet arrival rates λ, and the y-axis is the average of transmission rates in each packet slot. Similarly, the weighting scheme helps to maintain the fairness of packet transmission rate among all the mobile stations, as well as helps other mobile stations to survive under the heavier traffic load.

As shown in FIG. 7 , the network resources available to each user is not only related to the number of links available, but also related to the traffic consumption service surrounding the user. Although in a multi-cell multihop wireless network, the traffic information among neighboring nodes is complicated, the fully-distributed packet scheduling of the present invention is natural-competition-based. Therefore, regardless of the average packet arrival rate λ, the natural-competition-based method provides the optimal balanced solution.

Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.