CN103747530A - Wireless Mesh network channel allocation system and wireless Mesh network channel allocation method under partially overlapped channels - Google Patents

Abstract

The invention relates to a wireless Mesh network channel allocation system and a wireless Mesh network channel allocation method under partially overlapped channels. The system comprises a neighbor-interface binding module, a channel allocation order determination module and a greedy channel allocation module; the neighbor-interface binding module determines neighbor-interface binding relations according to the adjacent relations between nodes of a physical topology, and links which share the same interface serve as a whole and share the same channel when channels are allocated; the Rank descending order is used by the channel allocation order determination module, and the channel allocation order of each link is determined according to the principle that the link with the greatest Rank value is given priority in channel allocation; in order to minimize total interference in a network, the greedy channel allocation module uses the greedy algorithm to allocate channels to all the links in the network. The invention can effectively decrease the probability of network jamming, reduce interference in the network, increase the parallel transmission count in the network and increase the network capacity.

Description

The wireless Mesh netword channel assigning system and the method that partly overlap under channel

Technical field

The invention belongs to wireless communication technology field, relate in particular to a kind of multi-signal-channel and multi-interface wireless Mesh netword channel assigning system and method partly overlapping under channel based on IEEE802.11b/g.

Background technology

Wireless Mesh netword (Wireless Mesh Networks, WMN) there is high bandwidth, rapid deployment, be easy to install, safeguard the advantages such as simple, up-front investment cost is low, coverage that can extended wireless network, is therefore expected to become the ideal solution of solution " last kilometer " access problem.

By cochannel, disturbing the network capacity causing to decline is the main challenge that WMN faces.Due to the finiteness of orthogonal channel number, especially in all available channels of the WMN based on IEEE802.11b/g, only have 3 orthogonal channels, make network be difficult to avoid distribute same channel into adjacent link, therefore only utilize orthogonal channel to be difficult to solve interference problem.The WMN interference mitigation that is introduced as of channel of partly overlapping is even eliminated and has been brought new thinking, by the partly overlap use of channel of careful planning, can effectively reduce the interference in network, increases the parallel transmission number in network, significantly promotes network capacity.From current research situation both domestic and external, the planning of the channel that partly overlaps in WMN is used problem not yet effectively to be solved.In the channel assignment scheme hypothesis network that the overwhelming majority partly overlaps under channel, have business statistics device, therefore network can be known the load on each link in advance; Or suppose that network topology is given, the routed path of each stream given (conventionally using shortest path first to determine).In fact above-mentioned hypothesis has determined the link set that need to be assigned with channel, the more important thing is for the method for channel allocation that uses business load as channel allocation order foundation, has been equivalent to determine that link is assigned with the order of channel.The task of channel allocation is exactly under these given conditions, along the path computing of stream, show that a kind of channel allocation and link scheduling result are to complete the transmission of load.But the load of real network link is difficult to know in advance, and when link traffic load variations, channel assignment scheme may be inapplicable, need to re-start channel allocation.Therefore the dynamic that should consider business in network, connection request has dynamic source, destination and the time of advent, is all link assignment channels in network, the total interference in the simultaneous minimization network that guarantees network connectivty.

Summary of the invention

The technical problem to be solved in the present invention is to provide a kind of possibility that can reduce congested generation, reduces the total interference in network, the wireless Mesh netword channel assigning system and the method that partly overlap under channel based on IEEE802.11b/g of lifting WMN capacity.

In order to solve the problems of the technologies described above, the wireless Mesh netword channel assigning system under the channel that partly overlaps of the present invention comprises:

Neighbours-interface binding module: calculate the number of degrees of each node according to the syntople between the each node of physical topology, the number of degrees of node are defined as the neighbor node number of node; When carrying out neighbours-interface binding, according to avoid the node that the number of degrees are high to determine neighbours-interface binding relationship with the principle of other neighbours' link sharing interfaces as far as possible, when carrying out channel allocation, the link of shared same interface is as an integral dispensing same channel;

Channel allocation order determination module: use Rank descending, determine according to the principle of the large link priority allocation channel of Rank value the order that each link channel distributes;

Greedy channel assignment module: utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_i}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant; K is the path loss factor in two footpath propagation models (Two-ray Ground propagation model), and value is 2～4;

From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j; Be followed successively by all link assignment channels.

The present invention uses neighbours-interface binding relationship when neighbours' number of node is greater than number of ports, to make some neighbour share interface, because the high node of the number of degrees may have many stream processes, easily become the bottleneck node in network, therefore should make such node obtain more resource, avoid sharing interface with other neighbours, to reduce it, congested possibility occurs; Adopt the distance between link for greedy channel allocation algorithm, corresponding to the interference range under certain particular channel interval, quantize the interference between link, and the interference range that uses theoretical calculation method to obtain to partly overlap under channel, interference between link is portrayed more accurately and can be overcome the existing measurement method that is directed to particular network parameter configuration and obtain the portable poor deficiency of interference range, make this method can be applicable to the Mesh network of any configuration; To minimize, network is total to be disturbed as target use greedy algorithm all link assignment channels in network; Use all 11 available channels that partly overlap in IEEE802.11b/g frequency spectrum, can reduce the interference in network, increase the parallel transmission number in network, promote network capacity.

Described Rank value adopts following formula to calculate:

Wherein Rank _lfor the Rank value of link l; Neighbours' number of link l is defined as the also concentrated element number of neighbours' collection of two end nodes of link l, and link l is defined as the mean value of the minimum hop count of two end-point distances gateways of link l apart from the minimum hop count of gateway; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.

The present invention, on neighbours-interface binding basis, uses Rank descending to determine that the method for channel allocation order is the large link priority allocation channel of Rank value.In network, neighbours' number is more, the link fewer apart from the minimum hop count of gateway, more easily become the capacity bottleneck of network, the present invention has considered link neighbours number and apart from two factors of gateway minimum hop count, according to neighbours' number of the minimum hop count of link range gateway and link, all links in network are carried out to descending, use Rank descending to determine the order that each link channel distributes, be preferably the link assignment channel that Rank value is large; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward, can reduce to greatest extent the bottleneck link number in network, promotes overall performance of network.

The Itr(τ of corresponding different channels interval τ) be worth as shown in table 1;

Table 1

Once after greedy algorithm is a link assignment channel, the channel that link is used will no longer change, therefore greedy algorithm convergence is very fast.Once but after having distributed channel, just no longer change, conventionally use greedy algorithm to be difficult to reach optimal channel assignment.

The present invention also comprises population channel allocation optimization module; The input of this module using the channel allocation result of greedy channel assignment module as particle cluster algorithm, is used particle cluster algorithm to optimize channel allocation.

Described population channel allocation optimization module comprises following submodule:

Initial parameter arranges module: a kind of channel assignment scheme of all links in network is mapped as to a particle; Population is comprised of the particle of multiple expression different channels allocative decisions; The initial parameter of particle cluster algorithm is set, comprises the scale of population, the maximum iterations M allowing, total number of available channels N, control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 that learns and learn to historical optimum individual to contemporary optimum individual; Wherein inertia weight factors A lpha3 is obtained by formula (5);

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission;

Particle position and speed initialization module: flying speed and the position of using the channel allocation initializes particle that greedy channel assignment module obtains; Be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0); Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study; v _idand x (1) _id(0) value adopts the method for rounding up to round;

Particle position and speed iteration update module: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) （7）+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration, x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round;

Each iteration is calculated each particle position fitness function Objf after upgrading, selects the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle, using this, upgrade contemporary optimum individual and historical optimum individual: when reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish;

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Obif}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent the channel c that link i and j are used _iwith c _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

Population channel allocation optimization module of the present invention is using greedy channel allocation algorithm result as initial input, according to the fitness function guiding population iteration of definition, upgrade, consider the significance level of each link in network, for the suitable channel of all link assignment of Mesh network, optimize greedy channel allocation algorithm result, the total interference of network is further reduced, and network performance further promotes.

Wireless Mesh netword method for channel allocation of the present invention comprises the steps:

1) neighbours-interface binding: calculate the number of degrees of each node according to the syntople between the each node of physical topology, the number of degrees of node are defined as the neighbor node number of node; When carrying out neighbours-interface binding, according to avoid the node that the number of degrees are high to determine neighbours-interface binding relationship with the principle of other neighbours' link sharing interfaces as far as possible, when carrying out channel allocation, the link of shared same interface is as an integral dispensing same channel;

2) determining of channel allocation order: use Rank descending, determine according to the principle of the large link priority allocation channel of Rank value the order that each link channel distributes;

3) greedy channel allocation: utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_j}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant; K is the path loss factor in two footpath propagation models (Two-ray Ground propagation model), and value is 2～4;

From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j; Be followed successively by all link assignment channels.

Described step 2) in, Rank value adopts following formula to calculate:

Wherein Rank _lfor the Rank value of link l; Neighbours' number of link l is defined as the also concentrated element number of neighbours' collection of two end nodes of link l, and link l is defined as the mean value of the minimum hop count of two end-point distances gateways of link l apart from the minimum hop count of gateway; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.

In described step 3), the Itr(τ of corresponding different channels interval τ) be worth as shown in table 1;

Table 1

The present invention also comprises the steps:

Step 4) population channel allocation optimization: the input using greedy channel allocation result as particle cluster algorithm, use particle cluster algorithm to optimize channel allocation.

Described population channel allocation optimization comprises the steps:

1) initial parameter setting: a kind of channel assignment scheme of all links in network is mapped as to a particle; Population is comprised of the particle of multiple expression different channels allocative decisions; The initial parameter of particle cluster algorithm is set, comprises the scale of population, the maximum iterations M allowing, total number of available channels N, control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 that learns and learn to historical optimum individual to contemporary optimum individual; Wherein inertia weight factors A lpha3 is obtained by formula (5);

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission;

2) particle position and speed initialization: flying speed and the position of using the channel allocation initializes particle that greedy channel assignment module obtains; Be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0); Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study; v _idand x (1) _id(0) value adopts the method for rounding up to round;

3) particle position and speed iteration are upgraded: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) （7）+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration, x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round;

Each iteration is calculated each particle position fitness function Objf after upgrading, selects the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle, using this, upgrade contemporary optimum individual and historical optimum individual: when reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish;

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Objf}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent the channel c that link i and j are used _iwith c _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

Accompanying drawing explanation

Below in conjunction with the drawings and specific embodiments, the present invention is described in further detail.

Fig. 1 is wireless Mesh netword channel assigning system block diagram of the present invention.

Fig. 2 is wireless Mesh netword method for channel allocation flow chart of the present invention.

Fig. 3 is neighbours-interface binding method key diagram.

Fig. 4 is the flow chart of the greedy method for channel allocation of the present invention.

Fig. 5 is the flow chart of particle group optimizing method for channel allocation of the present invention.

Embodiment

As shown in Figure 1, wireless Mesh netword channel assigning system of the present invention comprises neighbours-interface binding module, channel allocation order determination module, greedy channel assignment module and population channel allocation optimization module.

Described neighbours-interface binding module adopts following method to determine neighbours-interface binding relationship:

Considering the dynamic of business in wireless Mesh netword, need to be all link assignment channels in network.According to the syntople between the each node of physical topology, determine neighbours-interface binding relationship, need to be for sharing the link assignment same channel of same interface when carrying out channel allocation.Due to the restriction of hardware condition, actual wireless Mesh nodes number of ports is limited, and neighbours' number is greater than number of ports conventionally, and some neighbour need to share node interface.Before carrying out channel allocation, need to determine the binding relationship of neighbours-interface.The present invention uses node adjacency relation to calculate the number of degrees of each node (being neighbours' number of node) to determine neighbours-interface binding relationship.As shown in Figure 3, A～K is 11 nodes on wireless Mesh network backbone.Node A has 3 interfaces, forms 4 link AB, AC, AD and AE with 4 neighbours.The number of degrees of Node B, C, D, E are respectively 4,3,2,2, from the highest node of the number of degrees, start to determine the binding of neighbours-interface, are link AB distribution interface 1, link AC distribution interface 2, link AD distribution interface 3.According to avoid the neighbours large with the node number of degrees to share the principle of interface as far as possible, for the link AE distribution interface identical with the link AD of the node number of degrees minimum comprising in AB, AC, AD, be link AE distribution interface 3.So just complete neighbours-interface binding of node A.Neighbours-interface binding procedure of all the other nodes is similar.

Described channel allocation order determination module is used Rank descending, according to the principle of the large link priority allocation channel of Rank value, determines the order that each link channel distributes, and concrete grammar is as follows:

On neighbours-interface binding basis, according to neighbours' number of the minimum hop count of link range gateway and link, all links in network are carried out to descending, use Rank descending to determine the order that each link channel distributes.Neighbours' number is more, and the link fewer apart from the minimum hop count of gateway more easily becomes the capacity bottleneck of network, should be preferably described link assignment channel, and when Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.Neighbours' number of described link is defined as the also concentrated element number of neighbours' collection of two end nodes of link, and the minimum hop count of described link range gateway is defined as the mean value of the minimum hop count of two end-point distances gateways of link.

Still, take node A 4 link AB, AC, AD and AE around as example, determining of channel allocation order is described.Neighbours' number of link AB is 8, and link AB is 2 apart from the minimum hop count of gateway, and therefore the Rank value of link AB is 4; In like manner, neighbours' number of link AC, AD and AE is respectively 7,6,6, and link AC, AD and AE are respectively 2.5,2.5,1.5 apart from the minimum hop count of gateway, and therefore the Rank value of link AC, AD and AE is respectively 2.8,2.4,4.The larger expression channel allocation of Rank value order is more forward; When Rank value is identical, the node channel allocation order that neighbours' number is more is more forward, and therefore the channel allocation order of 4 links is followed successively by: link AB → AE → AC → AD.

While determining channel allocation order, also can use the more more forward principle of multichannel assignment order or apart from the more forward principle of the fewer channel allocation order of gateway minimum hop count of link neighbours number.Be that Rank value also can adopt two formula below to calculate:

Rank _lneighbours' number of=link l

Or

Rank _l=link l is apart from the minimum hop count of gateway

To minimize, network is total to be disturbed as target use greedy algorithm all link assignment channels in network described greedy channel assignment module, specific as follows:

Utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_j}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ, only relevant with channel number interval,, therefore Itr(τ irrelevant with specific environment) value can be used theoretical calculation method acquisition before carrying out channel allocation; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when therefore Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant, is used for quantizing the annoyance level of the interchannel that partly overlaps on same node distinct interface, conventionally gets higher value, for example 10, to avoid same node distinct interface to use the channel that partly overlaps as far as possible; K is the path loss factor in Two-ray Ground propagation model, and value is 2～4.

The present invention uses interference range reduction gear ratio Itr(τ) interference relationships of the overlapping interchannel of quantized segment, and use theoretical calculation method to obtain Itr(τ) value.When the path loss factor k value in hypothesis Two-ray Ground propagation model is 4, when transceiver uses the raised cosine roll off filter that roll-off factor is 1, the Itr(τ of corresponding different channels interval τ) be worth as shown in table 1.

It is that 1 raised cosine roll off filter and the path loss factor are the Itr(τ of 4 o'clock that table 1 is used roll-off factor) value

When transceiver uses dissimilar filter, network can obtain Itr(τ by theoretical calculation method before carrying out channel allocation) value.When interference range R ' under given cochannel, the channel reduction interference range that partly overlaps when channel number is spaced apart τ is Itr (τ) × R '.This method of obtaining interference range has good transplantability, is applicable to the network of any configuration.When being link j allocated channel, be assumed to be link j allocated channel c _j, calculate the total interference between the link of all allocated channels in link j and network under this channel allocation, the rest may be inferred, the total interference when calculating link j and distributing other channels.From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j.Use all links in above-mentioned greedy algorithm traverses network, for every link selection makes network, always disturb minimum channel.Once after greedy algorithm is a link assignment channel, the channel that link is used will no longer change, therefore greedy algorithm convergence is very fast.Once but after having distributed channel, just no longer change, conventionally use greedy algorithm to be difficult to reach optimal channel assignment.

Described population channel allocation optimization module comprises following submodule:

Initial parameter arranges module: a kind of channel assignment scheme of all links in network is mapped as to a particle (particle matrix is a vector, and the each element representation in vector is distributed to the channel of respective links).Population is comprised of the particle of multiple expression different channels allocative decisions.By physical topology, build the distance matrix between each node, by sharing the link bundling of same interface, when channel allocation, must distribute same channel.The initial parameter of particle cluster algorithm is set, comprises the scale (being the number of per generation particle) of population, the maximum iterations M allowing, total number of available channels N, to contemporary optimum individual study with to control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 of historical optimum individual study.Wherein control coefrficient Alpha1 and Alpha2 are the constants that particle cluster algorithm itself is given, and inertia weight factors A lpha3 is obtained by formula (5).

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission.

Particle position and speed initialization module: use flying speed and the position of the channel allocation initializes particle that greedy channel assignment module obtains, be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0).Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study.Because channel number is all integer, to v _idand x (1) _id(0) value adopts the method for rounding up to round.

Particle position and speed iteration update module: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) （7）+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration; x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; Because channel number is all integer, to v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round.

Each iteration is calculated the fitness function Objf of each particle position after upgrading, the less expression particle position of fitness function value is more excellent.Upgrade contemporary optimum individual and historical optimum individual: select the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle.When reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish.

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Objf}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent channel ci and c that link i and j are used _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

As shown in Figure 2, wireless Mesh netword method for channel allocation of the present invention comprises the following steps:

1) neighbours-interface binding: considering the dynamic of business in wireless Mesh netword, need to be all link assignment channels in network.According to the syntople between the each node of physical topology, determine neighbours-interface binding relationship, need to be for sharing the link assignment same channel of same interface when carrying out channel allocation.Due to the restriction of hardware condition, actual wireless Mesh nodes number of ports is limited, and neighbours' number is greater than number of ports conventionally, and some neighbour need to share node interface.Before carrying out channel allocation, need to determine the binding relationship of neighbours-interface.The present invention uses node adjacency relation to calculate the number of degrees of each node (being neighbours' number of node) to determine neighbours-interface binding relationship.As shown in Figure 3, A～K is 11 nodes on wireless Mesh network backbone.Node A has 3 interfaces, forms 4 link AB, AC, AD and AE with 4 neighbours.The number of degrees of Node B, C, D, E are respectively 4,3,2,2, from the highest node of the number of degrees, start to determine the binding of neighbours-interface, are link AB distribution interface 1, link AC distribution interface 2, link AD distribution interface 3.According to avoid the neighbours large with the node number of degrees to share the principle of interface as far as possible, for the link AE distribution interface identical with the link AD of the node number of degrees minimum comprising in AB, AC, AD, be link AE distribution interface 3.So just complete neighbours-interface binding of node A.Neighbours-interface binding procedure of all the other nodes is similar.

2) determining of channel allocation order: use Rank descending, determine according to the principle of the large link priority allocation channel of Rank value the order that each link channel distributes, concrete grammar is as follows:

On neighbours-interface binding basis, according to neighbours' number of the minimum hop count of link range gateway and link, all links in network are carried out to descending, use Rank descending to determine the order that each link channel distributes.Neighbours' number is more, and the link fewer apart from the minimum hop count of gateway more easily becomes the capacity bottleneck of network, should be preferably described link assignment channel, and when Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.Neighbours' number of described link is defined as the also concentrated element number of neighbours' collection of two end nodes of link, and the minimum hop count of described link range gateway is defined as two end nodes of link apart from the mean value of the minimum hop count of gateway.

Still, take node A 4 link AB, AC, AD and AE around as example, determining of channel allocation order is described.Neighbours' number of link AB is 8, and link AB is 2 apart from the minimum hop count of gateway, and therefore the Rank value of link AB is 4; In like manner, neighbours' number of link AC, AD and AE is respectively 7,6,6, and link AC, AD and AE are respectively 2.5,2.5,1.5 apart from the minimum hop count of gateway, and therefore the Rank value of link AC, AD and AE is respectively 2.8,2.4,4.The larger expression channel allocation of Rank value order is more forward; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward, and therefore the channel allocation order of 4 links is followed successively by: link AB → AE → AC → AD.

While determining channel allocation order, also can use the more more forward principle of multichannel assignment order or apart from the more forward principle of the fewer channel allocation order of gateway minimum hop count of link neighbours number.Be that Rank value also can adopt two formula below to calculate:

Rank _lneighbours' number of=link l

Or

Rank _l=link l is apart from the minimum hop count of gateway

3) greedy channel allocation: network is total to be disturbed as target use greedy algorithm all link assignment channels in network to minimize.As shown in Figure 4, concrete grammar is as follows:

Be assumed to be link j allocated channel c _j, utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_i}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ, only relevant with channel number interval,, therefore Itr(τ irrelevant with specific environment) value can be used theoretical calculation method acquisition before carrying out channel allocation; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when therefore Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant, is used for quantizing the annoyance level of the interchannel that partly overlaps on same node distinct interface, conventionally gets higher value, for example 10, to avoid same node distinct interface to use the channel that partly overlaps as far as possible; K is the path loss factor in Two-ray Ground propagation model, and value is 2～4.

The present invention uses interference range reduction gear ratio Itr(τ) interference relationships of the overlapping interchannel of quantized segment, and use theoretical calculation method to obtain Itr(τ) value.When the path loss factor k value in hypothesis Two-ray Ground propagation model is 4, when transceiver uses the raised cosine roll off filter that roll-off factor is 1, the Itr(τ of corresponding different channels interval τ) be worth as shown in table 1.

It is that 1 raised cosine roll off filter and the path loss factor are the Itr(τ of 4 o'clock that table 1 is used roll-off factor) value

When transceiver uses dissimilar filter, network can obtain Itr(τ by theoretical calculation method before carrying out channel allocation) value.When interference range R ' under given cochannel, the channel reduction interference range that partly overlaps when channel number is spaced apart τ is Itr (τ) × R '.This method of obtaining interference range has good transplantability, is applicable to the network of any configuration.When being link j allocated channel, be assumed to be link j allocated channel c _j, calculate the total interference between the link of all allocated channels in link j and network under this channel allocation, the rest may be inferred, the total interference when calculating link j and distributing other channels.

From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j.

Use all links in above-mentioned greedy algorithm traverses network, for every link selection makes network, always disturb minimum channel.

Once after greedy algorithm is a link assignment channel, the channel that link is used will no longer change, therefore greedy algorithm convergence is very fast.Once but after having distributed channel, just no longer change, conventionally use greedy algorithm to be difficult to reach optimal channel assignment.

4) population channel allocation optimization: use particle cluster algorithm to optimize channel allocation, the input using greedy algorithm channel allocation result as particle cluster algorithm.As shown in Figure 5, specifically comprise the steps:

(1) the initial parameter setting of particle cluster algorithm: a kind of channel assignment scheme of all links in network is mapped as to a particle.Population is comprised of the particle of multiple expression different channels allocative decisions.By physical topology, build the distance matrix between each node, by sharing the link bundling of same interface, when channel allocation, must distribute same channel.The initial parameter of particle cluster algorithm is set, comprises the scale (being the number of per generation particle) of population, the maximum iterations M allowing, total number of available channels N, to contemporary optimum individual study with to control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 of historical optimum individual study.Wherein control coefrficient Alpha1 and Alpha2 are the constants that particle cluster algorithm itself is given, and inertia weight factors A lpha3 is obtained by formula (5).

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission.

(2) particle position and speed initialization: use flying speed and the position of the channel allocation initializes particle that greedy channel assignment module obtains, be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0).Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study.Because channel number is all integer, to v _idand x (1) _id(0) value adopts the method for rounding up to round.

(3) particle position and speed iteration are upgraded: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) （7）+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration; x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; Because channel number is all integer, to v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round.

Each iteration is calculated the fitness function Objf of each particle position after upgrading, the less expression particle position of fitness function value is more excellent.Upgrade contemporary optimum individual and historical optimum individual: select the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle.When reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish.

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Objf}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent the channel c that link i and j are used _iwith c _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

Claims (10)

1. the wireless Mesh netword channel assigning system partly overlapping under channel, is characterized in that comprising:

Neighbours-interface binding module: calculate the number of degrees of each node according to the syntople between the each node of physical topology, the number of degrees of node are defined as the neighbor node number of node; When carrying out neighbours-interface binding, according to avoid the node that the number of degrees are high to determine neighbours-interface binding relationship with the principle of other neighbours' link sharing interfaces as far as possible, when carrying out channel allocation, the link of shared same interface is as an integral dispensing same channel;

Channel allocation order determination module: use Rank descending, determine according to the principle of the large link priority allocation channel of Rank value the order that each link channel distributes;

Greedy channel assignment module: utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_j}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant; K is the path loss factor in the propagation model of two footpaths, and value is 2～4;

From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j; Be followed successively by all link assignment channels.

2. the wireless Mesh netword channel assigning system under the channel that partly overlaps according to claim 1, is characterized in that described Rank value adopts following formula to calculate:

Wherein Rank _lfor the Rank value of link l; Neighbours' number of link l is defined as the also concentrated element number of neighbours' collection of two end nodes of link l, and link l is defined as the mean value of the minimum hop count of two end-point distances gateways of link l apart from the minimum hop count of gateway; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.

3. the wireless Mesh netword channel assigning system under the channel that partly overlaps according to claim 1, is characterized in that the Itr(τ of corresponding different channels interval τ) be worth as shown in table 1;

Table 1

4. according to the wireless Mesh netword channel assigning system under the channel that partly overlaps described in claim 1,2 or 3, characterized by further comprising population channel allocation optimization module; The input of this module using the channel allocation result of greedy channel assignment module as particle cluster algorithm, is used particle cluster algorithm to optimize channel allocation.

5. the wireless Mesh netword channel assigning system under the channel that partly overlaps according to claim 4, is characterized in that described population channel allocation optimization module comprises following submodule:

Initial parameter arranges module: a kind of channel assignment scheme of all links in network is mapped as to a particle; Population is comprised of the particle of multiple expression different channels allocative decisions; The initial parameter of particle cluster algorithm is set, comprises the scale of population, the maximum iterations M allowing, total number of available channels N, control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 that learns and learn to historical optimum individual to contemporary optimum individual; Wherein inertia weight factors A lpha3 is obtained by formula (5);

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission;

Particle position and speed initialization module: flying speed and the position of using the channel allocation initializes particle that greedy channel assignment module obtains; Be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0); Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study; v _idand x (1) _id(0) value adopts the method for rounding up to round;

Particle position and speed iteration update module: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) （7）+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration, x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round;

Each iteration is calculated each particle position fitness function Objf after upgrading, selects the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle, using this, upgrade contemporary optimum individual and historical optimum individual: when reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish;

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Objf}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent the channel c that link i and j are used _iwith c _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

6. the wireless Mesh netword method for channel allocation partly overlapping under channel, is characterized in that comprising the steps:

1) neighbours-interface binding: calculate the number of degrees of each node according to the syntople between the each node of physical topology, the number of degrees of node are defined as the neighbor node number of node; When carrying out neighbours-interface binding, according to avoid the node that the number of degrees are high to determine neighbours-interface binding relationship with the principle of other neighbours' link sharing interfaces as far as possible, when carrying out channel allocation, the link of shared same interface is as an integral dispensing same channel;

2) determining of channel allocation order: use Rank descending, determine according to the principle of the large link priority allocation channel of Rank value the order that each link channel distributes;

3) greedy channel allocation: utilize formula (1), (2), (3), (4) to be calculated as link j allocated channel c _jtime the network that has been assigned with in link j and network between the link of channel always disturb

$I_{c_j}=\underset{i\∈I}{\mathrm{\Σ}}\mathrm{ir}(i,j,c_i,c_j)---\left(1\right)$

$\mathrm{Itr}\left(\mathrm{\τ}\right)=\sqrt[k]{\frac{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}\left(f\right)\×\mathrm{PSD}(f-5\·\mathrm{\τ})\mathrm{df}}{{\∫}_{-\∞}^{+\∞}\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(3\right)$

τ＝|c _i-c _j| (4)

Wherein: ir(i, j, c _i, c _j) represent that j is allocated channel ci respectively, the interference ratio of two links during cj, c when being link i _j=1,2 ... N, N is the quantity that link j can be used channel; I represents to be assigned with in network the link set of channel; Itr(τ) channel number that represents the interchannel using as link i and the j interference range reduction gear ratio while being spaced apart τ; D(i, j) represent the distance between link i and j, refer to the minimum value of distance between any end points of link i and any end points of link j; R ' represents the interference range under cochannel, the channel reduction interference range that partly overlaps when Itr (τ) × R ' is spaced apart τ for the channel number between i and j; F represents the frequency of channel; PSD(f) represent power spectral density function; α is constant; K is the path loss factor in the propagation model of two footpaths, and value is 2～4;

From using channel 1,2 ... in N, select to make network always disturb minimum channel c _j ^*distribute to link j; Be followed successively by all link assignment channels.

7. the wireless Mesh netword method for channel allocation under the channel that partly overlaps according to claim 6, is characterized in that described step 2) in, Rank value adopts following formula to calculate:

Wherein Rank _lfor the Rank value of link l; Neighbours' number of link l is defined as the also concentrated element number of neighbours' collection of two end nodes of link l, and link l is defined as the mean value of the minimum hop count of two end-point distances gateways of link l apart from the minimum hop count of gateway; When Rank value is identical, the link channel assignment order that neighbours' number is more is more forward.

8. the wireless Mesh netword method for channel allocation under the channel that partly overlaps according to claim 6, is characterized in that in described step 3), the Itr(τ of corresponding different channels interval τ) be worth as shown in table 1;

Table 1

9. according to the wireless Mesh netword method for channel allocation under the channel that partly overlaps described in claim 6,7 or 8, characterized by further comprising following step:

Step 4) population channel allocation optimization: the input using greedy channel allocation result as particle cluster algorithm, use particle cluster algorithm to optimize channel allocation.

10. the wireless Mesh netword method for channel allocation under the channel that partly overlaps according to claim 9, is characterized in that described population channel allocation optimization comprises the steps:

1) initial parameter setting: a kind of channel assignment scheme of all links in network is mapped as to a particle; Population is comprised of the particle of multiple expression different channels allocative decisions; The initial parameter of particle cluster algorithm is set, comprises the scale of population, the maximum iterations M allowing, total number of available channels N, control coefrficient Alpha2 and Alpha1, the inertia weight factors A lpha3 that learns and learn to historical optimum individual to contemporary optimum individual; Wherein inertia weight factors A lpha3 is obtained by formula (5);

$\mathrm{Alpha}3=w_{\max }-\frac{w_{\max }-w_{\min }}{M}\×m---\left(5\right)$

The number of times that wherein m is current iteration; M is the maximum iterations allowing; w _maxand w _minrepresent respectively the flying speed of partcles of minimum and maximum permission;

2) particle position and speed initialization: flying speed and the position of using the channel allocation initializes particle that greedy channel assignment module obtains; Be about to each channel assignment scheme and be mapped as a particle, wherein the initial position of arbitrary particle i is x _id(0); Using the particle position of optimal channel assignment scheme mapping in channel assignment scheme as contemporary optimum individual g _dand the historical optimum individual of this particle (0); The initial position x of arbitrary particle i in all the other particles _id(0) as himself historical optimum individual p _id(0); Utilize formula (6) to calculate the flying speed of the iteration for the first time v of each particle _id(1);

v _id(1)＝Alpha2×rand()×(g _d(0)-x _id(0)) （6）

Wherein: rand() represent the interior stochastic variable changing of (0,1) scope; Alpha2 represents to the control coefrficient of contemporary optimum individual study; v _idand x (1) _id(0) value adopts the method for rounding up to round;

3) particle position and speed iteration are upgraded: utilize more speed and the position of new particle of formula (7), (8);

v _id(t+1)＝Alpha3×v _id(t)+Alpha1×rand()×(p _id(t)-x _id(t)) (7)+Alpha2×rand()×(g _d(t)-x _id(t))

x _id(t+1)＝x _id(t)+v _id(t+1) （8）

Wherein: v _idand v (t) _id(t+1) represent respectively the flying speed of the particle i of the t time and the t+1 time iteration, x _idand x (t) _id(t+1) represent respectively the position of the particle i of the t time and the t+1 time iteration, t=1,2..., m ... M; p _id(t) represent particle i by first generation till the current optimal location searching, i.e. historical optimum individual; g _d(t) represent the optimal location that population current search arrives, i.e. contemporary optimum individual; Rand() represent the interior stochastic variable changing of (0,1) scope; v _idand x (t+1) _id(t+1) value adopts the method for rounding up to round;

Each iteration is calculated each particle position fitness function Objf after upgrading, selects the particle position of fitness function value minimum in current population as contemporary optimum individual; Selection by first generation till current certain particle search to the position of fitness function minimum as the historical optimum individual of this particle, using this, upgrade contemporary optimum individual and historical optimum individual: when reaching the maximum iteration time of permission, select contemporary optimum individual as last channel assignment scheme, IEEE 802.11 many interfaces of the b/g multi-Channel Wireless Mesh Network channel allocation under the channel that partly overlaps finish;

Total interference when the fitness function Objf of particle group optimizing is defined as corresponding to certain channel allocation in network, that is:

$\mathrm{Objf}=\underset{i,j\∈L}{\mathrm{\Σ}}{\mathrm{Rank}}_{\mathrm{ij}}\×\mathrm{ir}(i,j,c_i,c_j)---\left(9\right)$

Rank _ij＝max(Rank _i,Rank _j) （10）

Wherein: L represents all link set in network; Ir(i, j, c _i, c _j) represent the channel c that link i and j are used _iwith c _jbetween interference ratio; Rank _ijrepresent the weighted value that certain interference ratio is corresponding, value is the greater during the Rank of two links sorts.

Images