CN103561471A - Method for allocating bandwidths in multi-user single relay communication system - Google Patents

Abstract

The present invention provides a bandwidth allocation method in a multi-user single-relay communication system. When there are multiple users in an area, some of them can be directly connected to APs to become relays, and some of them need to connect to relay users to obtain data services. When a user enters the public LAN area, the user revenue function is discretized according to the user revenue function and the relay consumption function, and the bandwidth allocation algorithm is used to select the optimal bandwidth allocation strategy for bandwidth allocation, and the maximum service bandwidth of the relay is also considered And the user's minimum demand bandwidth limit, remove the user with low benefit to the network under appropriate circumstances, insert new user with higher benefit, and update the bandwidth allocation of the entire cluster. When the user leaves, the bandwidth is released and the bandwidth allocation is updated.

Description

A bandwidth allocation method in a multi-user single-relay communication system

technical field

The invention relates to the field of wireless communication, in particular to a bandwidth allocation method in a multi-user single-relay communication system.

Background technique

With the development of wireless local area network (WLAN), mobile users can access the Internet to obtain information, browse webpages and read emails anytime and anywhere by connecting to the access point AP. However, some users cannot access the Internet due to reasons such as limited AP connection range and poor signal strength. At this time, multi-hop access can solve this problem very well, that is, users within the signal coverage of the AP directly access the AP to become a relay, and those users who cannot directly connect to the AP can connect to the surrounding Relay to obtain Internet service indirectly.

The cooperation modes of each node in WLAN are generally divided into two types: cooperative type and selfish type. In a cooperative scenario, all nodes are willing to serve others to solve resource allocation problems. We define a wireless LAN with relatively fixed users (such as classrooms, etc.) as a Relay-Union Network (RUN), in which each user is willing to serve others to obtain the maximum benefit of the entire network. Under the condition of a single monopoly operator, Jiongkuan Hou et al. priced the service bandwidth according to the maximization of the interests of the Internet service provider and the congestion management scheme, and provided users with appropriate access services. However, the main purpose of this pricing strategy is to maximize the interests of service providers, without considering the end user's affordability and service requirements, and at the same time ignoring the characteristics of the RUN network, such as the role changes of ordinary users or relays.

Contents of the invention

Aiming at the above problems, the present invention proposes a bandwidth allocation method in a multi-user single-relay communication system, designs a relay connection strategy from the perspective of users, and maximizes the revenue of the entire network.

The bandwidth allocation method in the multi-user single-relay communication system provided by the present invention mainly includes the following steps:

Step 1. Acquiring the parameters required for allocating bandwidth to users, the parameters required for allocating bandwidth for users include user minimum bandwidth requirement B _min , user benefit function f _i (B _i ), relay maximum service bandwidth B _max and relay consumption function g(B);

Step 2: Initialize the relay bandwidth limit B _r , the total network revenue R _rc and the bandwidth value k allocated to users;

Step 3: Set the segmentation granularity ΔB, discretize the user benefit function f _i (B _i ) according to the segmentation granularity ΔB, and establish candidate bandwidths according to the segmentation granularity ΔB and the relay bandwidth limit B _r gather;

Step 4, select bandwidth from the candidate bandwidth set as the bandwidth value k allocated to the user, calculate the function dp (i, j) value between the user income of i users and the relay remaining bandwidth j, and get dp (i -1, jk)+f _i (k) and dp(i-1, j) are larger, increase the value of k in turn, and calculate the value of function dp(i, j) in a loop until the value of k is greater than the remaining bandwidth of the relay j ends the loop, and records the bandwidth allocation value k allocated to the user when the dp(i, j) value is the largest;

Step 5, loop step 4 until the bandwidth allocation of all users is completed, and record the k value selected for each user;

Step 6. Calculate the total network revenue R _rc under the relay bandwidth limit B _r , B _r =B _r +ΔB, repeat steps 4 and 5 in sequence until the relay bandwidth limit reaches the maximum service bandwidth of the relay, and record the maximum total network revenue R _rc , the bandwidth value k allocated to each user under the total revenue, and the relay bandwidth limit B _r for obtaining the maximum total network revenue.

The candidate bandwidth set is a set with segment granularity ΔB increasing sequentially from 0 to relay bandwidth limit B _r , that is, {0, B _min , B _min +ΔB, . . . , B _r }.

The segmentation granularity ΔB is set according to the accuracy actually required, and the segmentation granularity is inversely proportional to the accuracy.

The value of k increases sequentially and the value of the loop calculation function dp(i, j) increases the segmentation granularity ΔB each time the value of k increases.

The variation range of the relay bandwidth limit B _r is {B _min , B _min +ΔB, . . . , B _max }.

The method further includes: when the user in the relay leaves the relay, the relay re-performs step 6 to allocate bandwidth to other users in the relay.

The method further includes: when the relay leaves the local area network, judging whether the user in the local area network can directly connect to the access point AP, and if so, serving the user as a relay to other users; otherwise, The surrounding relays are randomly accessed, and the accessed relays perform steps 1 to 6.

The present invention focuses on the allocation strategy of relays under the condition of single relay and multiple users, and proposes a centralized bandwidth allocation cooperation method in a wireless local area network with relatively fixed users, so as to maximize the service benefits of all users in the network and reduce service costs. Provider overhead. Compared with the existing general algorithm, the technical solution of the invention can improve the calculation accuracy or reduce the calculation complexity according to the needs of users.

Description of drawings

Specific embodiments of the present invention will be described below with reference to the accompanying drawings, wherein:

FIG. 1 shows a schematic diagram of a user accessing a network;

Fig. 2 shows the curve diagram of the change of bandwidth revenue in the case of a single relay for a single user;

Fig. 3 shows the flowchart of the bandwidth allocation method of the embodiment of the present invention;

FIG. 4 shows a schematic diagram of bandwidth allocation in the case of a single user and a single relay;

Fig. 5 shows a schematic block diagram of bandwidth reallocation according to an embodiment of the present invention.

Detailed ways

In order to make the technical solutions and advantages of the present invention clearer, the exemplary embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings. Obviously, the described embodiments are only part of the embodiments of the present invention, not all implementations. Exhaustive list of examples.

In order to achieve resource allocation and maximize the benefits of the entire network, the present invention proposes a method for centralized bandwidth allocation in a wireless LAN with relatively fixed users. The designed scenario is a cooperative scenario, that is, all users will be other users Serve.

The embodiment of the present invention provides a bandwidth allocation method in a multi-user single-relay communication system, and the main technical solutions are as follows:

As shown in Figure 1, the identity of each user is determined through the perception and identification of the surrounding environment, and whether the user is a relay or an ordinary user is judged according to the coordinate position and the position of the access point AP:

If the user can be directly connected to the access point AP of the LAN, use it as a relay to provide services for other users;

If the user needs Internet service but cannot be directly connected to the access point AP, then randomly find suitable relays around to connect.

Usually, the collection of a relay and all users served by it is called a cluster.

All clients need to add the pricing parameter set after the Independent Basic Service Set Integrated Service Support System (IBSS, Independent Basic Service Set) parameter set of the standard beacon frame defined by the 802.11 protocol. The pricing parameter set will include user revenue function f _i (B _i ), user minimum bandwidth requirement B _min , relay consumption function g(B), relay service bandwidth upper limit B _max and other parameters.

The user benefit function f _i (B _i ) describes the relationship between the user access bandwidth and its satisfaction, and represents the satisfaction degree of the corresponding user node c _i after receiving the service, where the user access bandwidth B _i refers to the user The number of data transmitted per unit time represents the access bandwidth obtained by the user node from its relay node, and f _i (B _i ) is the credit limit that the user is willing to pay for this bandwidth.

The relay consumption function g(B) represents the cost function of the relay, where B is the service bandwidth of the relay, and g(B) is the cost of providing the bandwidth B. The relay service bandwidth B refers to the sum of the access bandwidth of all users served by the relay node. When the relay provides services to N users, the service bandwidth obtained by user i from the relay is B _i , then the relay service Bandwidth is

The larger the service bandwidth B of the relay node is, the more credits it gets. Among them, credit refers to the virtual currency that relays and users trade with each other in the relay alliance network RUN. Credit is a virtual real value (credit can be negative), stored in each user client, when the user just enters RUN, it is assumed that its credit is 0. However, when a user acts as a relay to provide services for other users, it will also affect the transmission of the user itself. In addition, energy consumption and CPU utilization will also increase with the increase of the bandwidth of the relay service. There will also be a price to pay for it.

In the embodiment of the present invention, the access bandwidth obtained by the user (acquired from the access point AP or from the relay) is used as the standard for measuring the service, and the goal pursued is to allocate the optimal access bandwidth (not lower than the minimum bandwidth requirement of the user) for the user so that The total revenue of the network is the largest.

When the selected relay connects to a new user, the appropriate bandwidth is allocated to the user according to the bandwidth allocation algorithm, and the bandwidth to other users is adjusted to maximize the utility of the entire network (that is, maximize the revenue).

Assuming that R _rc is the total revenue of the entire network, the total network revenue is the sum of relay revenue R _r and user revenue R _c . Among them, the relay revenue R _r is the difference between the total revenue brought by the service bandwidth of relay r and its consumption cost, and the user revenue R _c is the difference between the network revenue of user c and the consumption cost (such as payment credit).

另外，h_i(B_i)要低于用户收益函数f_i(B_i)，这样用户才能通过连接中继获益，此时总的用户收益为 $R_c={\mathrm{\Σ}}_{i-1}^N[f_i\left(B_i\right)-h_i\left(B_i\right)].$ 此时该中继用户组总收益为 $R_{\mathrm{rc}}={\mathrm{\Σ}}_{i-1}^N{f}_i\left(B_i\right)-g\left(B\right).$ 从而总收益仅靠用户收益函数和中继消耗函数决定。For a relay r and user _ci , h _i (B _i ) represents their charging function, where B _i is the access bandwidth of _ci , then h _i (B _i ) is the fee charged by r for _ci Fee, that is, the credit that _ci should pay to r for accessing the bandwidth B _i . The charging function h _i (B _i ) must be higher than the g(B) of the relay r, so as to ensure that the relay can benefit from providing services. At this time, the total income of the relay is

In addition, h _i (B _i ) must be lower than the user benefit function f _i (B _i ), so that users can benefit from connection relays. At this time, the total user benefit is $R_c={\mathrm{\Σ}}_{i-1}^N[f_i\left(B_i\right)-h_i\left(B_i\right)].$ At this time, the total income of the relay user group is $R_{\mathrm{rc}}={\mathrm{\Σ}}_{i-1}^N{f}_i\left(B_i\right)-g\left(B\right).$ Therefore, the total revenue is only determined by the user revenue function and the relay consumption function.

Fig. 2 shows the variation of user benefit function f _i (B _i ) and relay consumption function g(B) with access bandwidth B _i in the case of a single user and single relay. Among them, the user income function f _i (B _i ) is a convex function, and the relay consumption function g(B) is a concave function. R _c (B) in the figure represents user income, and R _r (B) represents relay income. B _c represents the bandwidth allocation value at which the user obtains the maximum benefit, and the bandwidth allocation in the embodiment of the present invention seeks the bandwidth value at this point. B _n means that when the bandwidth exceeds B _n , the increase in the bandwidth obtained by the user will not lead to an increase in the overall benefit, but will reduce the overall benefit of the network due to the consumption of relays.

The bandwidth allocation process in which a single relay allocates appropriate bandwidth for multiple users is shown in Figure 3, and the details are as follows:

First, the relay acquires the parameters required to allocate bandwidth to the user, including: the minimum bandwidth requirement of the user, the bandwidth of the relay service, the user consumption function, and the user revenue function.

Because in practical applications, when obtaining the optimal bandwidth in the relay alliance network, it is not necessary to use up the bandwidth that all relays can provide. Sometimes, providing a larger service bandwidth may reduce the revenue of the relay. In the embodiment of the present invention, a piecewise linear function is used to approximate the user revenue function and the relay consumption function, but in practical applications, the user bandwidth is limited by the minimum bandwidth, and the relay service bandwidth is also limited. Therefore, to ensure that all bandwidth utilization possibilities are considered, we will repeat our decision process for different relay service bandwidth limits. Assume that the upper limit of the relay service bandwidth is B _max , the minimum bandwidth requirement of each user is B _min , and the variation range of the relay service bandwidth limit B _r is specified as {B _min , B _min +ΔB,..., B _max }. Therefore, the user benefit function can only be discretized between B _min and B _max . Assuming that the segmentation granularity is ΔB, the bandwidth relayed to the user can only be selected from the candidate bandwidth set {0, B _min , B _min +ΔB, ..., B _max }. When ΔB→0, the piecewise linear approximation is a continuous curve. When the segmentation granularity ΔB is smaller, the obtained bandwidth allocation is closer to the optimal bandwidth allocation, and at the same time, its computational complexity increases. Then, according to the conditions of different service bandwidth constraints, the optimal network total revenue is selected for bandwidth allocation.

The relay discretizes the user revenue function according to the user's minimum bandwidth requirement and the relay's bandwidth margin, and obtains an allocatable bandwidth array set {0, B _min , B _min +ΔB,..., B _max }, It can also be called a candidate bandwidth set. Among them, ΔB is the segmentation granularity, which is set according to the degree of accuracy. The higher the accuracy, the smaller the ΔB setting; when the accuracy requirement is not high, the ΔB setting is larger.

Obtain the relationship function between the user revenue brought by i users and the remaining bandwidth according to the user revenue function $(i.j),\mathrm{dp}(i,j)={\mathrm{\Σ}}_{\mathrm{the\; s}-1}^i{f}_{\mathrm{the\; s}}\left(B_{\mathrm{the\; s}}\right).$ where j represents the remaining bandwidth of the relay, $j=B_{\max }-{\mathrm{\Σ}}_{\mathrm{the\; s}-1}^i{B}_{\mathrm{the\; s}}.$

The discretization process is initialized. For any j, j, let dp(ij)=0, the total network revenue R _rc tends to negative infinity, and the bandwidth allocation initialization B _j →0. Figure 4 shows the piecewise linear approximation process in the case of a single user and a single relay. The abscissa represents the bandwidth value, gradually adding ΔB from B _min to B _max , and the ordinate represents the credit value, k ₁ , k ₂ , . ..indicates the different bandwidths allocated to the user, where f(B) and g(B) vary with the value of the bandwidth k allocated to the user.

In the embodiment of the present invention, when allocating the i-th user's bandwidth, when the remaining bandwidth j>B _min , that is, the remaining bandwidth is sufficient for allocation, it can be within {0, B _min , B _min +ΔB,..., B _max } Select the appropriate bandwidth, assuming that the bandwidth allocated to user i is k, and the initial setting k=B _min , respectively calculate: dp(i-1, jk)+f _i (k), that is, when the allocated bandwidth is k, the user group at this time and calculating dp(i-1, j), that is, the income of the user group when the allocated bandwidth is 0. Comparing the two, when the former is larger, the bandwidth k is allocated to the user, _ki =k; when the latter is larger, no bandwidth is allocated to the user, _ki =0. When k is less than or equal to the remaining bandwidth j, k=k+ΔB, j= _jki , the value of k keeps increasing, correspondingly, the remaining bandwidth j of the relay gradually decreases, and the above operations are repeated until the maximum value of k for the user is found , and record it. Until the k value is greater than the remaining bandwidth, end the current loop, i++, and find the maximum k value for the next user. Until all users have cycled, that is, after i is greater than the N value, the output selects the maximum k value for each user, which is the bandwidth value allocated to the user by the relay For a WLAN with N users and one relay, select a set of bandwidth allocation arrays {k ₁ , k ₂ ,...k _N } from the candidate bandwidth set.

更新网络总收益R_rc和网络的带宽分配

B_r＝B_r+ΔB，增大当前中继带宽限制；否则，直接增大当前中继带宽限制B_r。According to the above operations, the user's maximum bandwidth allocation can be obtained when the relay bandwidth limit B _r = B _min $\left\{B_c^{i^{,}}\right\},$ Calculate the total network revenue at this time $R_{\mathrm{rc}}^{,}={\mathrm{\&Sigma;}}_{i=1}^N{f}_i\left(B_c^{i^{,}}\right)-g\left({\mathrm{\&Sigma;}}_{i=1}^N{B}_c^{i^{,}}\right),$ if $R_{\mathrm{rc}}<R_{\mathrm{rc}}^{,}$ (the initial network total income is set to 0), then let

Update the total network revenue R _rc and the bandwidth allocation of the network

B _r =B _r +ΔB, increase the current relay bandwidth limit; otherwise, directly increase the current relay bandwidth limit B _r .

The loop bandwidth allocation step ends until the relay bandwidth limit is greater than the maximum service bandwidth of the relay. Ultimately, finding the optimal relay bandwidth limit and the bandwidth value allocated to each user under the bandwidth limit maximizes the total revenue of the entire network, and achieves the goal of optimal bandwidth allocation in this embodiment of the invention.

The algorithm complexity and accuracy of the bandwidth allocation algorithm provided by the embodiments of the present invention are related to the segmentation granularity. From the above algorithm, it can be seen that the algorithm time complexity is O(NB ² _{m burden} ), which is a pseudopolynomial, and the discrete granularity related. Through the bandwidth allocation step, the relay calculates the bandwidth that needs to be allocated to the newly accessed user, and adjusts the bandwidth for other users to maximize the utility of the entire network (that is, maximize the revenue).

If a user in the relay leaves the relay, the relay needs to re-perform the above bandwidth allocation step at the next moment to re-allocate the bandwidth of the remaining users under the relay, as shown in FIG. 5 .

When the relay leaves the local area network, other users remaining in the local area network need to search for other relay connections again.

The present invention uses the bandwidth allocation algorithm to select the optimal bandwidth allocation strategy for bandwidth allocation, and at the same time, it also considers the restrictions on the maximum service bandwidth of the relay and the minimum required bandwidth of the user, and can not only effectively solve the bandwidth allocation problem of single relay and multiple users , and the accuracy and complexity of the algorithm can be adjusted appropriately according to the engineering needs. When appropriate, remove users with low benefit to the network, insert new users with higher benefit, and update the bandwidth allocation of the entire cluster. Moreover, all calculations in the present invention are performed on the client side, ensuring user mobility and safety. When the user leaves, the bandwidth is released and the bandwidth allocation is updated.

The above embodiments are only used to illustrate the technical solution of the present invention, not to limit it. Therefore, those skilled in the art can make various changes, substitutions and alterations without departing from the spirit and essence of the present invention. Obviously, these changes, substitutions and modifications should all fall within the protection scope of the claims of the present invention.

Claims (7)

1. a bandwidth allocation method in a multi-user single relay communication system, is characterized in that, comprises the following steps: Step 1. Acquiring the parameters required for allocating bandwidth to users, the parameters required for allocating bandwidth for users include user minimum bandwidth requirement B _min , user benefit function f _i (B _i ), relay maximum service bandwidth B _max and relay consumption function g(B); Step 2: Initialize the relay bandwidth limit B _r , the total network revenue R _rc and the bandwidth value k allocated to users; Step 3: Set the segmentation granularity ΔB, discretize the user benefit function f _i (B _i ) according to the segmentation granularity ΔB, and establish candidate bandwidths according to the segmentation granularity ΔB and the relay bandwidth limit B _r gather; Step 4, select bandwidth from the candidate bandwidth set as the bandwidth value k allocated to the user, calculate the function dp (i, j) value between the user income of i users and the relay remaining bandwidth j, and get dp (i -1, jk)+f _i (k) and dp(i-1, j) are larger, increase the value of k in turn, and calculate the value of function dp(i, j) in a loop until the value of k is greater than the remaining bandwidth of the relay j ends the loop, and records the bandwidth allocation value k allocated to the user when the dp(i, j) value is the largest; Step 5, loop step 4 until the bandwidth allocation of all users is completed, and record the k value selected for each user; Step 6. Calculate the total network revenue R _rc under the relay bandwidth limit B _r , B _r =B _r +ΔB, repeat steps 4 and 5 in sequence until the relay bandwidth limit reaches the maximum service bandwidth of the relay, and record the maximum total network revenue R _rc , the bandwidth value k allocated to each user under the total revenue, and the relay bandwidth limit B _r for obtaining the maximum total network revenue. 2. The bandwidth allocation method according to claim 1, wherein the set of candidate bandwidths is a set of sequentially increasing segmentation granularity ΔB from 0 until the relay bandwidth limit B _r , i.e. {0, B _min , B _min +ΔB,..., _Br }. 3. The bandwidth allocation method according to claim 1, wherein the segmentation granularity ΔB is set according to the accuracy actually required, and the segmentation granularity is inversely proportional to the accuracy. 4. The bandwidth allocation method according to claim 1, wherein the value of k increases successively, and the value of the loop calculation function dp(i, j) increases the segmentation granularity ΔB each time the value of k increases. 5. The bandwidth allocation method according to claim 1, wherein the variation range of the relay bandwidth limit B _r is {B _min , B _min +ΔB, . . . , B _max }. 6. The bandwidth allocation method according to claim 1, further comprising: when a user in the relay leaves the relay, the relay re-executes step 6 to allocate bandwidth to other users in the relay. 7. The bandwidth allocation method according to claim 1, further comprising: when the relay leaves the local area network, judging whether the users in the local area network can directly connect with the access point AP, if If yes, the user is used as a relay to provide services for other users; otherwise, the surrounding relays are randomly accessed, and the accessed relays perform steps 1 to 6.

Images