A novel and effective multi-constrained QoS routing scheme in WMNs

Abstract

Multi-constrained quality of service (QoS) routing aims at finding an optimal path that satisfies a set of QoS parameters, as an NP complete problem, which is also a big challenge for wireless mesh networks (WMNs). Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions, most of which suffered either from excessive computational complexities or from low performance, were proposed only for wired networks and cannot be used directly in wireless mesh networks. In this paper, we propose a novel routing scheme based on mean field annealing (MFA-RS) to solve this problem. MFA-RS first uses a function of two QoS parameters, wireless link’s delay and transmission success rate as the cost function, and then seeks to find a feasible path by MFA. Because MFA-RS uses a set of deterministic equations to replace the stochastic process in simulated annealing (SA) and uses saddle point approximation in the calculation of the stationary probability distribution at equilibrium, the convergence time is much less than the routing scheme based on SA (SA-RS). Simulation results demonstrate that MFA-RS is an effective algorithm and is very fit for WMNs.

Keywords

energy function / multi-constrained routing / mean field annealing (MFA) / simulated annealing (SA)

Introduction

In the last few years, many research works have focused on multi-hop ad hoc networks, in which relaying nodes are in general mobile, and communication needs are primarily between nodes within the same network. However, this type of network does not yet have an impact on our way of using wireless networks. Indeed, wireless mesh network (WMN) [1,2], a new broadband Internet access technology, which is an alias of wireless ad hoc network in the industry, is drawing significant attention these days and has been focused on by an increasing number of multi-hop wireless deployments and proprietary commercial solutions. Different from ad hoc network, WMN introduces a hierarchy in the network architecture with the implementation of dedicated nodes communicating among each other and providing wireless transport services to data traveling from users to either other users or access points (access points are special wireless routers with a high-bandwidth wired connection to the Internet backbone). In this class of networks, rather than involving pairs of terminal nodes, it mostly involves communication to and from wired gateways. Numerous challenges must be overcome to realize the practical benefits of wireless mesh networking. These include high network capacity, service of differentiation support, and secure and reliable communication, and, of principal interest here, quality of service (QoS) routing issues are critical topics for WMNs. Cost-effective resolution of these issues at appropriate levels is essential for widespread general use of wireless mesh networking.

Now, most QoS-sensitive applications that attract interest for use in current wired networks would attract interest for WMNs as well, therefore providing QoS guarantees is a critical issue for WMNs and needs to be overcome to realize the practical benefits of wireless mesh networking.

More than one QoS constraints (with or without optimization) often make the QoS routing (QoSR) problem non-deterministic polynomial (NP) complete [3,4]. However, an efficient polynomial algorithm rarely exists, and we propose a novel routing scheme based on mean field annealing (MFA) for multi-constrained routing in WMNs.

Related works

The main function of multi-constrained QoSR is to find an optimal path that satisfies multiple constraints for QoS applications. In wired networks, there are many multi-constrained QoSR (with or without optimization) methods that have been proposed [3,5-11]. However, they cannot be directly applied to WMNs because unlike the wired network, the network topology may change constantly, the available state information for routing is inherently imprecise, and the network itself is noncentralization. Furthermore, these algorithms, most of which are heuristic methods, may be suffering high complexity and cannot find feasible path in some worst cases; thus, they cannot be used directly in WMNs. In WMNs, if the just computed feasible route ceases to exist during the corresponding topology update, the QoS guarantee will become meaningless. Therefore, fast convergence is crucial while performing multi-constrained QoS routing to find (approximate) optimal configuration. On the other hand, QoSR for wireless ad hoc networks has been previously explored by Refs [12-16]. However, path computation algorithms in these literatures care about only a single metric, such as delay or hop-count, and most of them only deal with the best effort data traffic.

In ad hoc networks, only few QoS routing algorithms tend to solve the problem mentioned above.

In Ref. [17], a genetic algorithm (GA)-based routing method named as a GA-based QoS routing method for mobile ad hoc network (GAMAN) was proposed to address the multiconstrained QoSR in mobile ad hoc networks (MANETs). Rather than seeking for the optimal routes, GAMAN pays more attention to the response time and the robustness of the algorithm itself. By using small population size, few nodes are involved in route computation. By taking a subpopulation, the nodes in this subpopulation care only about the routes in this subpopulation. The broadcast is avoided because the information is transmitted only for the nodes in a population. GA searches for different routes, and they are sorted by ranking them. Therefore, the first one is the best route, but other ranked routes can be used as backup routes. By using a tree-based GA method, the loops can be avoided. GAMAN considers two QoS parameters and has a good gene coding sheme and simple genetic operation. However, it may suffer an untimely convergence problem for which the last configuration obtained may not be the optimal configuration, and with the scale of network increasing, the convergence time of GAMAN will increase severely. Moreover, for the intrinsic character of GA, GAMAN may be not able to find the optimal configuration in polynomial time in some worst case.

An efficient SA-based routing method named SA_RA was proposed in Ref [18]. to cope with the multi-constrained QoSR with optimization in ad hoc networks. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by SA. It is proved therein that SA_RA is a powerful stochastic optimization method in searching for global optimal solutions, but it is a little time-consuming due to the stochastic process in SA.

Reference [19] utilizes multiple paths between source and sink pairs for QoS provisioning. By estimation and approximation of path quality based on local link state information, they transform traditional NP-complete QoS problem to a modest problem, formulate the optimization problem as a probabilistic programming, and then convert it into a deterministic linear programming based on some approximation technique. Their goal is to provide soft-QoS to different packets.

Reference [20] proposes an enhanced simulated annealing-based multi-constrained QoS routing scheme for wireless multimedia sensor networks. Moreover, a more refined cooling schedule is constructed, while two key factors, attenuation function of control parameter T, and termination value of T were concerned. Furthermore, the influence of some classical random generators on the algorithms performance is investigated. Theoretical analysis and experiment results demonstrate that the proposed method is an effective multi-constrained QoS routing scheme, showing better performance than the other pertinent algorithms.

Proposed scheme

Pertinent information

Definition A graph, G=(V,\mathrm{\Gamma }), is used to describe a WMN with a finite non-empty node set V and a link set \mathrm{\Gamma }, and the member of which has two endpoints that can communicate with each other directly. In QoSR with optimization, each link (i,j)\in \mathrm{\Gamma } is associated with a primary cost parameter c(i,j) and an m-dimension additive QoS parameters vector \mathit{w}(i,j)=(w_{\mathrm{1}}(i,j),w_{\mathrm{2}}(i,j),\cdots ,w_l(i,j),\cdots ,w_m(i,j)), which is also called QoS metric w(e). Here, all parameters are nonnegative. Given m-dimension constraint vectors \mathit{c}=(c_{\mathrm{1}},c_{\mathrm{2}},\cdots ,c_l,\cdots ,c_m), the problem is to find a path p from a source node s to a destination node d such that:

1) w_l(p)={\displaystyle \sum _{(i,j)\in p}{w}_l(i,j)\le c_l} for l = 1, 2,…,m, and

2) c(p)={\displaystyle \sum _{(i,j)\in p}c(i,j)} is minimized over all feasible paths satisfying condition 1).

SA

In statistical mechanics, a physical process called annealing is often performed in order to relax the system to the state with the minimum energy. The probability of the system being in state is represented by the Gibbs canonical distribution [21]:

(1)P_T(i)={\displaystyle \frac{\mathrm{1}}{Z_T}}{\mathrm{e}}^{\frac{-E_i}{\kappa T}}

where Z_T is the system partition function, which is defined as

(2)Z_T={\displaystyle \sum _{i\in S}{\mathrm{e}}^{\frac{-E_i}{\kappa T}}}

While the temperature is being lowered down, it is easy to find that [22]

(3)$$\begin{gathered} \underset{T\to \mathrm{0}}{\lim }{P}_T(i)=\underset{T\to \mathrm{0}}{\lim }{\displaystyle \frac{{\mathrm{e}}^{-\frac{E_i-E_{\min }}{\kappa T}}}{{\displaystyle \sum _{j\in S}{\mathrm{e}}^{-\frac{E_j-E_{\min }}{\kappa T}}}}} \\ =\underset{T\to \mathrm{0}}{\lim }{\displaystyle \frac{{\mathrm{e}}^{-\frac{E_i-E_{\min }}{\kappa T}}}{{\displaystyle \sum _{j\in S_{\min }}{\mathrm{e}}^{-\frac{E_j-E_{\min }}{\kappa T}}}+{\displaystyle \sum _{j\notin S_{\min }}{\mathrm{e}}^{-\frac{E_j-E_{\min }}{\kappa T}}}}} \\ =\{\begin{array}{ll}{\displaystyle \frac{\mathrm{1}}{\left|S_{\min }\right|}}\hfill & \mathrm{i}\mathrm{f}i\in S_{\min }\hfill \\ \mathrm{0}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\hfill \end{array} \end{gathered}$$

where S_{\min }=\{i:E_i=E_{\min }\}, and E_{\min }={\min }_{j\in S}E(j).

In the basic form of SA, it first generates an initial solution as the current feasible solution using Metropolis algorithms [21]. Then, another solution is selected in the neighborhood of the current solution and replaces the current solution with the new one with the following transition probability given by the Metropolis criterion:

(4)P(i\Rightarrow j)=\{\begin{array}{ll}\mathrm{1}\hfill & \mathrm{i}\mathrm{f}f(j)\le f(i)\hfill \\ {\mathrm{e}}^{\frac{f(i)-f(j)}{t}}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\hfill \end{array}

MFA

Even though SA is proved to be able to reach the global optima asymptotically, it is time consuming to reach thermal equilibrium at each temperature. Finite number of transitions at each temperature cannot guarantee convergence to the global optima. In statistical physics, mean field approximation is often used. MFA uses a set of deterministic equations to replace the stochastic process in SA. It uses saddle point approximation in the calculation of the stationary probability distribution at equilibrium and reaches equilibrium at each temperature much faster than SA. Even though this approximation method may not guarantee convergence to global minima, it does provide a good approximation in finding near-optimal solutions with much less computing effort.

It is difficult to calculate the system partition function Z_T, which is defined in Eq. (2) in a large-scale optimization problem, thus an approximation method, such as the saddle point approximation [23], is used. Note that the Dirac delta function \delta (\cdot ) can be expressed as

(5)\delta (x)={\displaystyle \frac{\mathrm{1}}{\mathrm{2}\mathrm{\pi }i}}{\displaystyle {\int }_I{\mathrm{e}}^{xy}\mathrm{d}y}

where the integral is taken along the imaginary axis. Hence,

(6)$$\begin{gathered} Z_T={\displaystyle \sum _{\mathit{S}\in S}{\mathrm{e}}^{-\frac{E(S)}{T}}} \\ =C{\displaystyle \sum _{\mathit{S}\in S}{\displaystyle {\int }_{\mathit{R}}{\displaystyle {\int }_{\mathit{I}}{\mathrm{e}}^{-\frac{E(\mathit{v})}{T}}{\mathrm{e}}^{\mathit{u}(\mathit{S}-\mathit{v})}}}}\mathrm{d}\mathit{u}\mathrm{d}\mathit{v} \\ =C{\displaystyle {\int }_{\mathit{R}}{\displaystyle {\int }_{\mathit{I}}{\mathrm{e}}^{-E_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{u},\mathit{v})}\mathrm{d}\mathit{u}\mathrm{d}\mathit{v}}}, \end{gathered}$$

where

(7)E_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{u},\mathit{v})={\displaystyle \frac{E(\mathit{v})}{T}}+\mathit{u}\mathit{v}-\ln {\displaystyle \sum _{\mathit{S}\in S}{\mathrm{e}}^{\mathit{u}\mathit{S}}}

is called effective energy in statistical mechanics, C is a complex constant, BoldItalic is the network state, and S is the state space of the network. At saddle points, we have

(8){\displaystyle \frac{\partial E_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{u},\mathit{v})}{\partial \mathit{u}}}=\mathit{v}-{\displaystyle \frac{{\displaystyle \sum _{\mathit{S}\in S}\mathit{S}{\mathrm{e}}^{\mathit{u}\mathit{S}}}}{{\displaystyle \sum _{\mathit{S}\in S}{\mathrm{e}}^{\mathit{u}\mathit{S}}}}}=\mathrm{0}

and

(9){\displaystyle \frac{\partial E_{\mathrm{eff}}(\mathit{u},\mathit{v})}{\partial \mathit{v}}}={\displaystyle \frac{\mathrm{1}}{T}}{\displaystyle \frac{\partial E(\mathit{v})}{\partial \mathit{v}}}+\mathit{u}=\mathrm{0.}

Therefore,

(10)

where is the thermal average of BoldItalic at temperature T. In statistical physics, BoldItalic and BoldItalic are called the mean field vectors, and \mathit{h}=-\partial E(\mathit{v})/\partial \mathit{v} is called the mean field. For a binary system, if we represent a configuration \mathit{S}={[s_{\mathrm{1}},s_{\mathrm{2}},\cdots ,s_n]}^{\mathrm{T}} as a sequence of binary values, that is, s_i\in {\{\mathrm{0},\mathrm{1}\}}^n, then we have \mathit{v}={[v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_n]}^{\mathrm{T}} and

(11)v_i={\displaystyle \frac{{\displaystyle \sum _{s_i=\mathrm{0}}^{\mathrm{1}}{s}_i{\mathrm{e}}^{u_i{s}_i}}}{{\displaystyle \sum _{s_i=\mathrm{0}}^{\mathrm{1}}{\mathrm{e}}^{u_i{s}_i}}}}={\displaystyle \frac{{\mathrm{e}}^{u_i}}{\mathrm{1}+{\mathrm{e}}^{u_i}}}={\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}\left[\mathrm{1}+\tanh \left({\displaystyle \frac{u_i}{\mathrm{2}}}\right)\right],

where \mathit{u}={[u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_n]}^{\mathrm{T}}, and u_i=-{\displaystyle \frac{\mathrm{1}}{T}}{\displaystyle \frac{\partial E(\mathit{v})}{\partial v_i}}.

For the binary system, we have the following MFA equations:

(12)v_i={\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}\left(\mathrm{1}+\tanh {\displaystyle \frac{h_i}{\mathrm{2}T}}\right),

(13)h_i=-{\displaystyle \frac{\partial E(\mathit{v})}{\partial v_i}}.

Hopfield [24] defined the following energy function of the Hopfield net for optimization:

(14)E_h(\mathit{S})=-{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{\displaystyle \sum _i{\displaystyle \sum _{j\ne i}{s}_i{s}_j{w}_{ij}-}}{\displaystyle \sum _i{s}_i{I}_i}=-{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{\mathit{S}}^{\mathrm{T}}\mathit{W}\mathit{S}-{\mathit{I}}^{\mathrm{T}}\mathit{S},

where s_i\in \{\mathrm{0},\mathrm{1}\}. In the Hopfield model, the system is represented by a network composed of n neurons. Each neuron i can be represented by an operational amplifier, s_i is the output of neuron i, and w_{ij}, which is symmetric (w_{ij}=w_{ji}, and w_{ii}=\mathrm{0}), represents the synaptic connection between neuron i and j. I_i is the input current to amplifier i. The stable states of the network correspond to the {\mathrm{2}}^n corners of the hypercube {\{\mathrm{0},\mathrm{1}\}}^n, the local minima of the energy function defined in Eq. (14). For the MFA approximation, if the energy function is formulated as Eq. (14), the mean field h_i and the thermal average v_i becomes

(15)h_i=-{\displaystyle \frac{\partial E_h(\mathit{v})}{\partial v_i}}={\displaystyle \sum _j{w}_{ij}}{v}_j+I_i,

(16)

In MFA, the iterative procedure to reach thermal equilibrium at each temperature is called relaxation, in which the mean field is updated by

(17)h_i(t+\mathrm{\Delta }t)=h_i(t)+\mathrm{\Delta }t\left(-{\displaystyle \frac{\partial E_h(\mathit{v})}{\partial v_i}}-h_i(t)\right).

When \mathrm{\Delta }t\to \mathrm{0}, we have

(18)$$\begin{gathered} {\displaystyle \frac{\mathrm{d}{h}_i}{\mathrm{d}t}}=\underset{\mathrm{\Delta }t\to \mathrm{0}}{\lim }{\displaystyle \frac{h_i(t+\mathrm{\Delta }t)-h_i(t)}{\mathrm{\Delta }t}} \\ =-{\displaystyle \frac{\partial E_h(\mathit{v})}{\partial v_i}}-h_i(t) \\ ={\displaystyle \sum _j{w}_{ij}}{v}_j+I_i-h_i. \end{gathered}$$

The MFA relaxation operation at each temperature should lead the system to stable equilibrium. The mean field network (MFN) procedure can be summarized in the flow chart shown in Fig. 1, where Eqs. (19) and (20) are listed as follows:

(19)h_i(k)=h_i(k-\mathrm{1})+\mathrm{\Delta }t\left[{\displaystyle \sum _j{v}_j(k-\mathrm{1})w_{ij}}+I_i-h_i(k-\mathrm{1})\right],

(20)v_i(k)={\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}\left(\mathrm{1}+\tanh {\displaystyle \frac{h_i}{T}}\right),(i=\mathrm{1},\mathrm{2},\cdots ,N)

and l and l_k are the lth sweep at temperature T_k and the number of sweeps performed at temperature T_k, respectively.

Scheme description

To solve the multi-constrained QoS routing problem with optimization in WMNs using MFA, we first need to set the net parameters, that is, to map the problem onto the MFN.

Problem representation

For the multi-constrained QoSR problem, N × N neurons will be used to present a valid route from a source to a destination node. The neurons are grouped into N groups of N neurons. In a WMN composed of five nodes (see Fig. 2), 25 neurons will be required to represent a route by an output matrix BoldItalic.

For example, let

\mathit{V}=\left(\begin{array}{lllll}\mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)

The matrix represents a valid route from node A to node C (e.g., where A-A-C-C-C is interpreted as A-C). There are other ways, such as A-C-C-C-C, A-A-A-A-C and A-A-A-A-C, that can be used to represent the same path. The total delay of route A-A-A-C-C would be

(21)\xi ={\xi }_{AA}+{\xi }_{AA}+{\xi }_{AA}+{\xi }_{AC}+{\xi }_{CC}.

Self looping is allowed, and there is no cost associated with it. The actual cost would be the {\xi }_{AC} in the route.

Some key points of MFA-RS

1) The proposed energy function is defined as follows:

(22)E={\displaystyle \frac{1}{2}}{\displaystyle \sum _{x=1}^N{\displaystyle \sum _{y=1}^N{\displaystyle \sum _{i=2}^{N-1}{\mathrm{\Psi }}_{xy}{v}_{xi}\left(v_{y,i+1}+v_{y,i-1}\right)+{\displaystyle \frac{\eta }{2}}}}}{\displaystyle \sum _{x=1}^N{\displaystyle \sum _{i=1}^N{v}_{xi}^2}},

where x, y refer to the nodes, η is a reinforcement term, i is the position in the route, v denotes the current state (value) of the pertinent neuron, and the cost function {\mathrm{\Psi }}_{xy}={\xi }_{xy}/{\zeta }_{xy}. (For the convenience of comparison with the SA-based algorithm in Ref [18], we only take two QoS parameters, {\xi }_{xy} and {\zeta }_{xy}, into consideration. Here, {\xi }_{xy} is the delay between nodes x and y, and {\zeta }_{xy} is the transmission success rate.) The first term deals with the constrained parameters, and the second term adds local positive feedback around neurons that stabilize the mean field network and eliminate chaotic behavior (parasitic oscillations) during the optimization process. Then, the mean field and the thermal average become

(23)h_{xi}=-{\displaystyle \frac{\partial E\left(\mathit{v}\right)}{\partial v_{xi}}}=-T{\displaystyle \sum _{y=1}^N{\mathrm{\Psi }}_{xy}\left(v_{y,i+1}+v_{y,i-1}\right)+T\mathit{\eta }{v}_{xi}},

(24)

2) The critical temperature is defined at the temperature at which the sharp state transition starts. That is, each neuron is likely pushed toward the “0” or “1” state. Here, by running simulations and plotting the energy with respect to temperature, we set T_c=\mathrm{50}.

3) We stop the annealing when all the neuron values are within the range [0,0.1] or within the range [0.9,1] or when the temperature reaches zero.

4) The temperature control function reflects the way the temperature is reduced, and in our simulations, we adopt the following empirical annealing schedule:

(25)

5) At each temperature, the iteration will stop when the mean difference of the value of the neuron of the neighboring iteration is less than 10^-3.

Performance evaluation

We have carried out many simulations in different scenarios using Matlab 6.5. Wireless mesh networks with different number nodes (routes) (i.e., 10 (36), 20 (725), and 30 (11375)) are considered. The performance achieved by MFA-RS is compared with the method based on SA proposed in Ref [18]. because it shows that the SA-based method outperformed other pertinent algorithms there. Each algorithm is executed for 500 times, and the convergence time is averaged over the 500 runs. We first initialize the delay and transmission success rate of the valid wireless links randomly and then set pertinent parameters according to Section 3.2.2. Here, these two QoS parameters are selected from uniform distributions under no correlation between them, that is, both QoS parameters are independently selected from uniform distributions. As to the method based on SA, we initialize the pertinent parameters as follows: let T_{\mathrm{0}}=\mathrm{10}, T_t\to \mathrm{0}, respectively, the length of Markov chain is 10², and the control function is given as T_{k+\mathrm{1}}=\alpha T_k (let α = 0.90).

The performance metrics we considered were convergence time (CT) and success ratio (SR), respectively. If an algorithm finds a path for a connection request, we count this request as a routed connection request. CT means how long is the average time needed to find a feasible path; SR, which shows how often an algorithm finds a path that satisfies the given constraints, refers to the ratio of total number of routed connection requests to the total number of connection requests.

Figure 3 denotes the convergence time of MFA-RS with respect to (w.r.t.) different annealing schedule. We set α in Eq. (23) with different values and tend to find the correlation between convergence time and annealing schedule. When the temperature is lowed down more quickly, e.g., when α = 0.85, the needed convergence time will be correspondingly shorter, that is, the computational efficiency of MFA-RS will be raised.

Figure 4 shows the success ratio of MFA-RS w.r.t. different annealing schedule. Though the difference between the SRs in one group is not very apparent, the tendency can be seen that with the temperature decreasing more quickly, the corresponding SR will be lowered down, that is, the quality of the final configuration will be deteriorated.

Figure 5 shows CT versus the number of nodes (routes). In different scenarios where only the numbers of existing nodes (routes) are different, we performed these two different methods. As in Fig. 5 shows, with the number of nodes (routes) increasing, the running time increases but not as rapid as the exponent time, and MFA-RS shows better performance than the method based on SA. For example, when the number of nodes is ten (accordingly, the number of the feasible routes from a source to a destination is 36), the convergence time of MFA-RS is 0.4 ms, while the time of the SA-based method is 5 ms, which is longer than MFA-RS. The reasons are listed as follows: 1) SA-RS and MFA-RS are all polynomial algorithms that could be used to solve the NP complete problems and could reach the (approximately) global optima asymptotically. 2) Further, in MFA-RS, we use a set of deterministic equations to replace the stochastic process in the method based on SA and use saddle point approximation in the calculation of the stationary probability distribution at equilibrium; thus, the convergence time is much less than the SA-based method. Finally, as the result shows, when the scale of the network is relatively small, the time needed can be tolerated in practice in order to meet the more rigorous QoS service request.

Then, we contrast another performance metric of MFA-RS against SA-RS. Figure 6 indicates the SR of these two algorithms used for multi-constrained QoS routing in WMNs. When there are 10 nodes in WMNs, the pertinent SR of these two algorithms are about 91% and 89%, respectively. When 20, 30 nodes are concerned, the SRs will be 95%, 91% and 92%, 95%, respectively. Conclusion can be drawn that MFA-RS provides nearly the same SR as SA-RS.

In conclusion, MFA-RS adds local positive feedback around neurons that stabilize the mean field network and eliminate chaotic behavior (parasitic oscillations) during the optimization process; thus, it can converge more quickly than SA-based algorithm. The proposed method is an effective approximate algorithm, showing good performance in seeking the (approximate) optimal configuration within a period of polynomial time.

Conclusion

Searching for the optimal route that can satisfy more than one QoS parameters simultaneously in wireless mesh networks is an NP complete combinatorial optimization problem. Existing methods proposed for wired networks cannot be used directly under these circumstances. SA-based method is a powerful stochastic optimization method in searching for global optimal solutions, but it is time-consuming. In this paper, a novel multi-constrained routing method named MFA-RS using mean field annealing is proposed. Mean field annealing, which adopts saddle point approximation, uses a set of deterministic equations to replace the stochastic process in SA; thus, it is more efficient than SA. Numeric results have shown that MFA-RS can find the comparable solutions more quickly than the SA-based methods, and it is a promising multi-constraints QoS routing algorithm with optimization for wireless mesh networks.

References

[1] Bruno R, Conti M, Gregori E. Mesh networks: Commodity multihop ad hoc networks. IEEE Communications Magazine, 2005, 3(3): 123–131

[2] Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks. IEEE Wireless Communications, 2003, 10(5): 8–14

[3] Jaffe J M. Algorithms for finding paths with multiple constraints. Networks, 1984, 14(1): 95–116

[4] Wang Z, Crowcroft J. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228–1234

[5] Kuipers F, Mieghem P V, Korkmaz T, Krunz M. An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine, 2002, 40(12): 50–55

[6] Yuan X.Heuristic algorithms for multiconstrained quality-of-service routing. IEEE/ACM Transactions on Networking, 2002, 10(2): 244–256

[7] Chen S. Routing support for providing guaranteed end-to-end quality-of-service. Dissertation for the Doctoral Degree.Urbana-Champaign: University of Illinois at Urbana-Champaign, 1999, 23–79

[8] Korkmaz T, Krunz M. Multi-constrained optimal path selection. In: Proceedings of Twentieth annual Joint Conference of the IEEE Computer and Communications Societies.2001, 2: 834–843

[9] Chen S, Nahrstedt K. On finding multi-constrained paths. In: Proceedings of IEEE International Conference on Communications. Atlanta, 1998, 2: 874–879

[10] Korkmaz T, Krunz M. A ranomized algorithm for finding a path subject to multiple QoS constraints. Computer Networks, 2001, 36(3): 251–268

[11] Khadivi P, Samavi S, Todd T D, Saidi H. Multi-constraint QoS routing using a new single mixed metric. In. Proceedings of IEEE International Conference on Communications., 2004, 4: 2042–2046

[12] Xiao H, Seah W K G, Lo A, Chua K C. A flexible quality of service model for mobile ad-hoc networks. In: Proceedings of the 51st IEEE Vehicular Technology Conference.2000, 1: 78–89

[13] Ahn G S, Campbell A T, Veres A, Sun L H. Supporting service differentiation for real-time and best-effort traffic in stateless wireless ad hoc networks (SWAN). IEEE Transactions on Mobile Computing, 2002, 1(3): 192–207

[14] Lee S B, Ahn G S, Zhang X, Campbell A T. INSIGIA: An IP based quality of service framework for mobile Ad Hoc networks. Journal of Parallel and Distributed Computing, 2000, 60(4): 374–406

[15] Sivakumar R, Sinha P, Bharghavan V. CEDAR: A core-extraction distributed Ad-Hoc routing algorithm. IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1454–1465

[16] Chen S, Nahrstedt K. Distributed quality-of-service routing in ad-hoc networks. IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1–18

[17] Barolli L, Koyama A, Shiratori N A. QoS routing method for ad-hoc networks based on genetic algorithm.In: Proceedings of the 14th International Workshop on Database and Expert Systems Applications.2003, 175–179

[18] Liu L, Feng G. Simulated annealing based multi-constrained QoS routing in mobile ad hoc networks. Wireless Personal Communications, 2007, 41(3): 393–405

[19] Huang X, Fang Y. Multiconstrained QoS multipath routing in wireless sensor networks. Wireless Networks, 2008, 14(4): 465–478

[20] Liu L, Chen Z. Multi-constrained QoS path selection in wireless multimedia sensor networks. In: Proceedings of the 1st International Conference on Information Science and Engineering.2009, 5362–5365

[21] Pham D T, Karaboga D. Intelligent optimisation techniques.London: Springer-Verlagnt, 2000, 10–105

[22] Aarts E, Korst J. Simulated annealing and Boltzmann machine—a stochastic approach to combinatorial optimization and neural computing.New York: Wiley, 1989, 8–36

[23] Peterson C, Soderberg B. A new method for mapping optimization problems onto neural network. International Journal of Neural Systems, 1989, 1(1): 3–22

[24] Hopfield J J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences of the United States of America, 1982, 79(8): 2541–2554

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg