CN100401831C - Frequency Allocation Method Combined with Point-Edge Coloring in Fixed-Relay Cellular Networks - Google Patents

Abstract

The invention relates to a frequency allocation method combining point-edge coloring of a fixed relay cellular network, which belongs to the technical field of wireless communication. The specific steps of the present invention are as follows: the first step: calculate the point coloring algorithm of the graph according to the point coloring constraints, and obtain the frequency allocation result of the base station; the second step: obtain the situation of all 3 adjacent fixed relays, and use the middle coloring node Instead, record the location and frequency consumption information; the third step: according to the edge coloring frequency constraints and the relay frequency allocation constraints, the edge coloring algorithm is used to color the edge coloring graph, and the frequency resource allocation results of each fixed relay are obtained . On the basis of the prior art, the present invention can effectively take factors such as complex topography into consideration, and at the same time, ensure relatively high calculation efficiency. This is something that traditional coloring schemes cannot achieve in fixed relay networks.

Description

Frequency Allocation Method Combined with Point-Edge Coloring in Fixed-Relay Cellular Networks

technical field

The invention relates to a method in the technical field of wireless communication, in particular to a method for allocating frequencies in conjunction with point-edge coloring of a fixed relay cellular network.

Background technique

Frequency is a precious resource in wireless communication. In network planning, how to deal with frequency allocation to improve the efficiency of spectrum resources is of great significance. In this field, a major breakthrough of many researchers is to introduce the coloring problem in graph theory. Once the entire planned wireless network is abstracted into a graph model, many conclusions and algorithms in graph theory coloring problems can be successfully applied to this network, which greatly reduces the complexity of the frequency allocation process. Fixed relay network is a wireless network architecture that has been researched quite recently. It is an improvement to the traditional cellular network. By adding a fixed-position relay node in a cellular network, it can improve the coverage of the cell, reduce the power consumption of the cell, and reduce the call drop rate.

After searching the prior art documents, it was found that the researchers of Carleton University (Huining Hu. Performance Analysis of Cellular Networks with Digital Fixed Relays[D]. Ottawa, Ontario: Carleton University, 2003. (introducing digital fixed relays in cellular network Performance analysis, Canada, Montreal, University of Kelton master's thesis 2003) proposed a network layout with 6 fixed relays regularly distributed in a cell, this relay scheme has been researched and analyzed to save power and improve spectrum efficiency, Compared with the traditional network, it has been greatly improved. In terms of frequency spectrum planning, the document Huining Hu.Performance Analysis of Cellular Networks with Digital Fixed Relays[D].Ottawa, Ontario: Carleton University, 2003 (the introduction of digital fixed relays in the cellular network Performance Analysis, Canada, Montreal, Kelton University Master Thesis 2003) gives the simplest frequency allocation scheme under Carleton fixed relay, however, this frequency scheme only considers the principle of multiplexing the farthest frequency under regular distribution, Any actual terrain factors and radio wave propagation characteristics are not considered.

Contents of the invention

Aiming at the deficiencies of the prior art, the present invention provides a frequency allocation method for fixed-relay cellular network joint point edge coloring, so that it can effectively take factors such as complex terrain into consideration on the basis of the prior art, and at the same time , which also guarantees a fairly high computational efficiency. This is something that traditional coloring schemes cannot achieve in fixed relay networks.

The present invention is realized through the following technical solutions. The present invention uses a 3-step allocation process, and for the first time tries to use an improved frequency allocation algorithm combining a point coloring frequency allocation method and an edge coloring frequency allocation method. The specific steps of the method are as follows:

The first step: calculate the point coloring algorithm of the graph according to the point coloring constraint conditions, and obtain the frequency allocation result of the base station;

Step 2: Obtain the situation of all three adjacent fixed relays, replace them with intermediate coloring nodes, and record the location and frequency consumption information;

Step 3: According to the edge-coloring frequency constraints and the relay frequency allocation constraints, the edge-coloring algorithm is used to color the edge-coloring graph, and the frequency resource allocation results of each fixed relay are obtained.

The calculation of the point coloring algorithm of the graph according to the point coloring constraints to obtain the frequency allocation result of the base station refers to: when the map information of the cellular network, the location of the base station and the path loss are known, according to the point coloring constraints, apply The point coloring algorithm obtains the colorable set of each base station, that is, the allocated frequency set.

The described application of the point coloring algorithm to obtain the colorable set of each base station refers to: using a typical point coloring algorithm to solve the frequency allocation problem of the base station, modeling the wireless network into a simple graph G (V, E), the set The vertex v in V represents a launch station in a network, and the edge e=(v1, v2) in the set E represents the connection of two adjacent launch stations. When performing the point coloring allocation algorithm, analyze the frequency of the entire network Constraint problem, the constraints are: co-channel frequency distance constraint, adjacent channel frequency distance constraint, frequency distance constraint and frequency constraint problem, graph vertex coloring algorithm model of co-channel frequency distance constraint, solved by DL algorithm, coloring in descending order of degrees Sequential DL algorithm solution.

In the case of obtaining all three adjacent fixed relays, replaced by intermediate colored nodes, it means: searching the entire fixed relay network, belonging to three adjacent fixed relays under three different base stations, and the distance is less than the coverage of the base station When the radius is 1/2, mark the 3 fixed relays as a group, and use the center point of the triangle formed by the 3 fixed relays as the vertices to replace the 3 fixed relays, and this point is used as the middle coloring point.

Said to replace the three fixed relays with the center point of the triangle formed by these three fixed relays as vertices, it means: record the information of the three fixed relays formed on this intermediate coloring point, it The antenna and emission conditions of the fixed relay are equivalent to the antenna and emission conditions of the fixed relay, and the path loss between it and each base station and each other intermediate coloring point needs to be recalculated and recorded.

The situation of obtaining all 3 adjacent fixed relays, replaced by intermediate coloring nodes, means: in terms of position, the distance between the 3 fixed relays between 3 adjacent cells is quite close, so this The three fixed relays are regarded as one point to participate in the frequency allocation of fixed relays. After obtaining the frequency allocation results of the base station, the information in the original scene is scanned to obtain the information of all three adjacent fixed relays, and the middle color is used The node replaces, records the location and frequency consumption information, constructs an edge coloring graph for all known base stations and intermediate points, and then uses the edge coloring algorithm to complete the frequency allocation of the entire cellular system.

According to the edge coloring frequency constraints and relay frequency allocation constraints, coloring the edge coloring graph with the edge coloring algorithm refers to: after the intermediate coloring points are obtained and the information is completed, the entire scene The base station and the middle coloring point construct an edge coloring allocation graph. The edge coloring frequency constraint condition is: when edge coloring, the adjacent edges must be colored with different colors, and the relay frequency allocation constraint condition is: when the relay frequency allocation, the middle The edge connecting the colored point to the base station must be colored differently from the base station.

The described edge coloring algorithm coloring of the graph on the edge coloring graph refers to: using a heuristic algorithm, starting with the vertex with the largest degree, first coloring each edge connected to it, and then using the adjacent edge of this point The vertex with the largest degree is the second order, and the uncolored edges connected to it are colored.

Compared with the prior art, the present invention adopts the technology of distinguishing base station cells from fixed relays and assigning them sequentially when planning the frequency of the cellular network with fixed relays, which simplifies the implementation of the entire allocation process . The present invention also adopts an improved edge coloring algorithm when performing frequency allocation on fixed relays, and replaces the adjacent three fixed relays with intermediate coloring points within the allowable error range, which greatly simplifies coloring The complexity of the algorithm. Moreover, the present invention fully considers the different terrain factors of the base station and the fixed relay transmitting station, and makes up for the blank of a comprehensive and effective frequency allocation algorithm in the fixed relay cellular network.

Detailed ways

The present invention mainly utilizes the characteristics of fixed relay position and relatively small relay transmission power during frequency multiplexing, combines edge coloring and point coloring, and divides the frequency of fixed transmitting stations and divides fixed transmission chains with these two algorithms The advantage of the frequency of the road is integrated into the new algorithm, which is completed after some changes.

The graph point coloring algorithm involved in the present invention refers to modeling the wireless network as a simple graph G(V, E). The vertex v in the set V represents a launch station in a network, and the edge e=(v1, v2) in the set E represents the connection of two adjacent launch stations. When carrying out the distribution algorithm of point coloring, the frequency constraint problem of the whole network is analyzed. Constraints in allocation mainly include co-channel frequency distance constraints, adjacent channel frequency distance constraints, frequency distance constraints, and frequency constraints. The mathematical outline of the point coloring algorithm is: find a distribution A: V->F; satisfy v∈V, u≠v, D(u, v)<d ₀ , d0=1 then |A(u)-A(v)|≠0, max4(V)=max{A(v)|v∈ V}. Let F be an optional set of frequency colors, and max means that the solution assignment color span is the smallest. The graph vertex coloring algorithm model of FD-CCAP can be solved by the DL algorithm, and the present invention adopts the DL algorithm whose coloring order is in descending order of degrees.

If the constraints are more complex, such as d0 > 1, we can still find a suitable simple heuristic algorithm to approximate (FD-ACAP) for the allocation of this graph. Although the conclusion is not optimal, the process is still very efficient. , especially with a small number of vertices.

In the present invention, when the map information of the cellular network, the location of the base station and the path loss are known, the interference graph is drawn, and the DL algorithm is used to solve the problem according to the same-channel frequency distance constraint condition of point coloring, and the coloring order is in descending order of degree The DL algorithm solves it.

e_j∈E，i≠j，D*(i，j)＜d₁则|A(e_i)-A(e_j)|≠0，maxA(E)＝max{A(e)|e∈E}模型建立之后，频率分配问题就转化为如何使用有限的颜色集合对图G中的每条边进行着色。最简单的约束条件为合理边着色，它指的是图G(V，E)中任意一个顶点的所有关联边的颜色互不相同，即d1＝1的情况。The graph edge coloring algorithm involved in the present invention refers to modeling the wireless network as a simple graph G(V, E), which is mainly used in the frequency allocation scheme with directional emission and "space division multiple access". The vertex v in the set V represents a launch pad in a network. When there is a directional launch relationship between two launch pads, the corresponding vertices v1 and v2 of the launch pad are connected by a straight line, which is called an associated edge. The set of all associated edges is denoted by E. The mathematical outline of edge coloring is: find a distribution A: E->F; satisfy

e _j ∈ E, i≠j, D*(i, j)<d ₁ then |A(e _i )-A(e _j )|≠0, maxA(E)=max{A(e)|e∈ After the E} model is established, the frequency assignment problem is transformed into how to use a limited set of colors to color each edge in graph G. The simplest constraint condition is reasonable edge coloring, which means that the colors of all associated edges of any vertex in the graph G(V, E) are different from each other, that is, the case of d1=1.

Reasonable edge coloring is constrained by the 1964 Vizing theorem, the minimum colorable number x'=Δ, Δ+1 of a simple graph. And there are also many well-accepted heuristics that yield suboptimal results. The heuristic algorithm adopted in the present invention is specifically: start with the vertex with the largest degree, first color the edges connected to it, and then take the vertex with the largest degree adjacent to this point as the second order, and color the edges it connects. Individual unshaded edges.

The present invention can adopt the coloring method in which the order of degree coloring is transferred, but the constraints of edge coloring are slightly different from those of the classical ones: adjacent sides must be colored with different colors, and the constraint conditions for relay frequency allocation are: when the relay frequency is allocated, intermediate coloring The edge connecting the point to the base station must be colored differently from the base station.

The designed frequency allocation scheme of the present invention, main innovation point is:

1) Frequency allocation is carried out in 2 steps:

The frequency resource allocation between cell base stations is performed first, and then the frequency resource allocation of each relay node is performed. The main reason for adopting such a dispensing step is the simplicity of the operation process. The base station frequency resource allocation involved in the first step is a typical case that can be solved using the point coloring algorithm, and the number of points involved is small, so the suboptimal algorithm runs quickly and stably.

When the spectrum of the base station has been allocated, the frequency limit of the fixed relay is also fixed. In fact, when planning and designing the entire cellular network with 2-hop fixed relays, the frequency limitation of the fixed relays is also subject to the frequency planning of the superior base station. In this way, the lower-level allocation algorithm is also very clear.

2) Use intermediate location points to represent 3 adjacent fixed relays:

Since the transmission power of fixed relays is small, the range of influence is also small. In terms of location, the distance between the three fixed relays between the three adjacent cells is quite close, so the present invention attempts to regard these three fixed relays as a point to participate in the second step of fixed relay frequency allocation. The present invention analyzes numerically the error caused by replacing three adjacent fixed relays with the middle position point. Theoretically, the error calculation is very simple. If the reuse factor of the cell is 4 and the attenuation factor of wireless propagation is 4, the error is less than 1.17%. If the error caused by the different environment may be included in the actual different positions, the maximum error of the interference coefficient is within 5%.

In the Carleton fixed relay solution, the interference error within 5% caused by using the intermediate position point has a very low probability of affecting the subsequent fixed relay frequency allocation results. The three nodes are simplified into one representative point, and the benefits brought are very obvious. The complexity of the system is greatly reduced, and the number of points participating in edge coloring distribution is the original (1/3). This is an important guarantee for the efficiency of subsequent heuristic algorithms.

For this reason, the present invention designs the following process of obtaining the intermediate coloring point: search the entire fixed relay network, belong to 3 adjacent fixed relays under 3 different base stations, when the distance is less than 1/2 of the coverage radius of the base station, mark the Three fixed relays are used as a group, and these three fixed relays are replaced by the center point of the triangle formed by the vertices of these three fixed relays, and this point is used as the middle coloring point.

3) In the frequency allocation of the relay, introduce the edge coloring algorithm:

The present invention innovatively proposes the idea of introducing an edge coloring algorithm in the second step, the frequency allocation process between fixed relays. The reason for using this algorithm is that the position of the fixed relay node is fixed, and the rules are located in three different directions of the middle point. In addition, the fixed relay has the characteristics that the transmission power is very small and only affects an area around it.

Since the introduction of edge coloring, the traditional point coloring algorithm has been solved in the face of the newly generated frequency constraints of fixed relay networks. According to the constraints of edge coloring, two associated edges with common nodes cannot be colored with the same color. This condition directly solves the problem that different fixed relays cannot occupy the same channel resource in the same cell. In addition, although the relay nodes are not in the same cell, but the geographical location is close, they are also constrained by edge coloring and cannot be colored in the same color.

Another feature of the edge coloring algorithm is that the frequency planning of the entire scene can be changed very conveniently through the dynamic adjustment of the permissible conditions of the color of the vertices. That is to say, there is a simple processing method for the dynamic frequency resource allocation of the relay node. This makes the frequency allocation of the fixed relay network very flexible and facilitates the development of more complex frequency allocation schemes.

The concrete realization of the present invention is divided into following 7 operations:

1) Obtain scene information, map information, available frequency resource information, and resource consumption quantity information of specific fixed relays.

2) Extract information related to the base station, and establish a point-colored graph A that only exists in the base station. Calculate the path loss information of each cell, write it into the weight of the edge, and complete the point coloring map A.

3) Carry out algorithm calculation on this graph according to the general point coloring constraint conditions, and obtain the frequency allocation result of the base station.

4) After obtaining the frequency allocation result of the base station, scan the information in the original scene to obtain the information of all three adjacent fixed relays, and replace them with intermediate colored nodes. Record location and frequency usage information.

5) Construct edge-colored graph B for all known base stations and intermediate points.

6) Perform algorithmic coloring on the edge-coloring graph B according to the edge-coloring frequency constraint conditions and the relay frequency allocation constraint conditions. The frequency resource allocation result of each fixed relay is obtained.

7) Check the entire process and complete the entire frequency allocation process.

The following examples are provided in conjunction with the content of the method of the present invention:

This embodiment is adopted in a scene imitating Manhattan. This simulated Manhattan scene consists of 440*410 map grids, with 19 distributed base station nodes and 114 (19*6) distributed fixed relay nodes. In this embodiment, a total of 42 optional frequencies are allocated, and each frequency is replaced by a different color. Each base station can be assigned to 6 different frequencies, and each fixed relay can only be assigned to 3 different frequencies. In this embodiment, the known geographical location and antenna height are used to calculate the path loss value with the OKUMURA_HATA+dual slope propagation model. Before point coloring and edge coloring, according to the path loss value between all points, the path with less influence is ignored, and then Construct a vertex-colored graph and an edge-colored graph. This embodiment adopts the DL algorithm of descending degree order to perform algorithmic coloring on the point-colored graph, and this embodiment adopts the heuristic algorithm of descending-degree order to perform algorithmic coloring on the edge-colored graph. The final results were sent to the COBWeb Network Simulator with 2-hop Fixed Relaying Nodes Scheme wireless 2-hop relay system simulation platform for performance testing. The platform is a simulation platform for large-scale fixed relay scenarios. The entire system is configured in the FDD working mode, and the Mobility model of Random Walk+Markov. When the power control and adaptive functions of the system are not turned on, the test results show that there are SINR on the first hop (the link from the mobile station to the fixed relay) and the second hop (the link from the fixed relay to the base station). Significant quality improvement.

Claims (7)

1. a kind of frequency assignment method that fixed relay cellular network combines point edge coloring, it is characterized in that, concrete steps are as follows: The first step: calculate the point coloring algorithm of the graph according to the point coloring constraint conditions, and obtain the frequency allocation result of the base station; Step 2: Obtain the situation of all 3 adjacent fixed relays, replace them with intermediate coloring nodes, record the location and frequency consumption information, In the case of obtaining all three adjacent fixed relays, replaced by intermediate colored nodes, it means: searching the entire fixed relay network, belonging to three adjacent fixed relays under three different base stations, and the distance is less than the coverage of the base station When the radius is 1/2, mark the 3 fixed relays as a group, and use the center point of the triangle formed by the 3 fixed relays as vertices to replace the 3 fixed relays, and this point is used as the middle coloring point; Step 3: According to the edge-coloring frequency constraints and the relay frequency allocation constraints, the edge-coloring algorithm is used to color the edge-coloring graph, and the frequency resource allocation results of each fixed relay are obtained. 2. the fixed relay cellular network according to claim 1 combines the frequency allocation method of point edge coloring, it is characterized in that, the point coloring algorithm calculation of graph is carried out according to point coloring constraint condition, obtains the frequency allocation result of base station, It refers to: when the map information of the cellular network, the base station location and the path loss are known, according to the point coloring constraints, the point coloring algorithm is applied to obtain the colorable set of each base station, that is, the allocated frequency set. 3. the fixed relay cellular network according to claim 2 combines the frequency allocation method of point edge coloring, it is characterized in that, described application point coloring algorithm obtains the colorable set of each base station, refers to: use typical point The coloring algorithm is used to solve the frequency allocation problem of the base station, and the wireless network is modeled as a simple graph G(V, E), the vertex v in the set V represents a transmitting station in the network, and the edge e in the set E=(v1, v2) represents the connection of two adjacent transmitting stations. When performing the point coloring allocation algorithm, the frequency constraint problem of the entire network is analyzed. The constraint conditions are: same-channel frequency distance constraint, adjacent channel frequency distance constraint, frequency distance constraint and The frequency constraint problem, the graph vertex coloring algorithm model with the frequency distance constraint of the same channel, is solved by the DL algorithm, and the DL algorithm with the coloring order in descending order is solved. 4. The frequency allocation method of fixed relay cellular network combined point edge coloring according to claim 1, characterized in that, the center point of the triangle formed with these 3 fixed relays as vertices replaces these 3 A fixed relay refers to: record the information of the three fixed relays to this intermediate coloring point, its antenna and emission conditions are equivalent to the antenna and emission conditions of the fixed relay, it and each base station, and In addition, the path loss of each intermediate shading point needs to be recalculated and recorded. 5. the frequency allocation method of fixed relay cellular network joint point edge coloring according to claim 1, is characterized in that: the described situation of obtaining all 3 adjacent fixed relays is replaced by an intermediate coloring node, which means : In terms of location, the distance between the three fixed relays between the three adjacent cells is quite close, so these three fixed relays are regarded as a point to participate in the fixed relay frequency allocation, and the frequency allocation of the base station is obtained After the result, scan the information in the original scene to obtain the information of all three adjacent fixed relays, replace them with intermediate coloring nodes, record the location and frequency consumption information, and construct edges for all known base stations and intermediate points Coloring the graph, and then using the edge-coloring algorithm, completes the frequency allocation for the entire cellular system. 6. The frequency allocation method of fixed relay cellular network junction edge coloring according to claim 1, characterized in that, according to the edge coloring frequency constraints and relay frequency allocation constraints, the edge coloring graph is graphed Edge shading algorithm coloring refers to: after completing the acquisition of intermediate shading points and information completion, the base station and intermediate shading points of the entire scene are constructed into an edge shading allocation graph, and the edge shading frequency constraint condition is: edge shading When , the adjacent sides must be colored with different colors. The constraint condition for relay frequency allocation is: when the relay frequency is allocated, the edge connecting the middle colored point with the base station must be colored with a different color from the base station. 7. according to claim 1 or 6 described fixed relay cellular network combined point edge coloring frequency allocation method, it is characterized in that, described edge coloring algorithm coloring of graph is carried out to edge coloring graph, refers to: adopt heuristic The algorithm starts with the vertex with the largest degree, and first colors the edges it connects, and then takes the vertex with the largest degree adjacent to this point as the second order, and colors the uncolored edges it connects.