Performance Analysis of Multi-Hop Wireless Link under Maximum Flow Algorithm

Sarwar Jahan¹, Md. Imdadul Islam², M. Ruhul Amin³

¹Department of Electronics and Communications Engineering, East West University, Dhaka, Bangladesh.
²Department of Computer Science and Engineering, Jahangirnagar University, Savar, Bangladesh.
³Deparment of Mathematical and Physical Sciences, East West University, Dhaka, Bangladesh.

DOI: 10.4236/jcc.2019.78002                

Abstract

To enhance link capacity of a wireless link one or more repeater is used between the sender and the receiver. Recent literature deals with multiple parallel links to enhance throughput instead of conventional single path. In case of a multidirectional and multi-hop wireless network, the selection of link of maximum signal to noise ratio (SNR) does not guarantee the maximum throughput. In this paper, we use augmenting path of Ford-Fulkerson algorithm in detection of maximum flow from sender to receiver. To reduce the process time at the sending node, minimum-cut theorem is used to determine maximum flow like power flow of previous work. Using the maximum flow algorithm, we obtain the capacity of multi-hop wireless link higher than the conventional theorem. The concept of the paper is applicable in MANET (Mobile Ad-hoc Network), WSN (Wireless Sensor Network) and CRN (Cognitive Radio Network).

Keywords

Ford Fulkerson Algorithm, Flow-Conservation, Minimum Cut Theorem, SNR, Channel Capacity

1. Introduction

There are many applications of maximum flow algorithm which are found in our real-life situations. For example, in [1] , the modified Edmonds-Karp algorithm is applied in water supply system of a campus. In [2] , instead of Ford-Fulkerson algorithm, a parallel Genetic algorithm is applied in a weighted directed graph to find a maximum flow. In [3] , the authors deal with maximum end-to-end spectral efficiency in multi-hop wireless link. Instead of a single path from source to destination, they have searched for multiple simultaneous source-destination routes using the optimal routing algorithm. Trade-off is made between complexity of network layer in determining route and MAC sub-layer in scheduling time slot. The normalized throughput (bps/Hz) or spectral efficiency is varied against the number of nodes for both fixed and variable time slot algorithms. In case of minimum spectral efficiency, the fixed time slot algorithm provides better results but in case of average spectral efficiency, the variable time slot gives better throughput. The throughput is also varied against SNR (signal to noise ratio) and the number of “source to destination” pairs. In [4] , the gain of transmitting antenna array of single-hop link is evaluated to achieve equivalent throughput of dual-hop wireless link. The authors determine BER (Bit Error Rate) and probability of symbol error against SNR of links in the Rayleigh and Nakagami-m fading cases under 16-QAM and QPSK modulation techniques.

Closed-form solution of two-hop cooperative cognitive underlay relay network is found in [5] to estimate secrecy outage. Secrecy outage probability is plotted against secrecy data rate using MRC (maximal ratio combining), with power control as well as without power control under analytical and simulation techniques. Similar analysis is found in [6] for α-μ fading channel where SER (Symbol Error Rate) and outage probability is plotted against SNR in dB. Much the same results are also found in [7] under both analytical and simulation techniques in multi-hop amplify-and-forward (AF) relay systems with cooperative diversity; where authors convert multi-hop relay system to its approximate equivalent dual-hop system. Application of maximum flow algorithm (Ford-Fulkerson Algorithm) along with Shortest Path (Dijkstra’s Algorithm) is found in congestion control of vehicle traffic [8] . Traffic volumes of roads are collected by manual traffic count and video recordings for the road network from Bandaraya Mosque to Kampung Air in Kota Kinabalu, Malaysia. Application of Ford-Fulkerson Algorithm is also found in [9] [10] [11] [12] ; where the algorithm is applied for electrical load flow under minimum cut theorem and also in wireless sensor networks based on route minimum key set.

In our present paper, we use maximum flow algorithm to obtain the capacity of multi-hop wireless link higher than that of the conventional theorem.

The rest of the paper is organized as follows: section II deals with the system model along with the solution of multi-hop wireless link using maximum flow algorithm. Section III provides results based on the analysis of section II, while section IV concludes the entire analysis.

2. System Model

This section deals with the maximum flow algorithm and the way of its application in multi-hop wireless link.

2.1. Basic of the Maximum Flow Algorithm

According to maximum flow algorithm, the sender and the receiver are equivalent to source and sink. All the other nodes, i.e., repeaters of the network where data can be redirected without consuming or adding any amount of data resembles intermediate nodes like Figure 1. In a repeater, the total amount of data entering must be equal to the total amount of data leaving it; hence, it obeys the following flow-conservation requirement:

${\displaystyle \underset{j:\left(j,i\right)\in E}{\sum }{C}_{ji}}={\displaystyle \underset{j:\left(i,j\right)\in E}{\sum }{C}_{ij}}$ for i = 2, 3, 4, …, n − 1, (1)

where a network is often abstractly defined as a graph G, that has a set of vertices V, connected by a set of edges E and here the network contains n nodes and the node 1 and node n correspond to the source and the sink respectively.

Because of the flow-conservation of intermediate nodes, the total amount of data leaving the source/transmitter must end up at the sink/receiver like Figure 2 and can be expressed as

${\displaystyle \underset{j:\left(1,j\right)\in E}{\sum }{C}_{1j}}={\displaystyle \underset{j:\left(j,n\right)\in E}{\sum }{C}_{jn}}$ (2)

If the total outgoing flow from the source or total incoming flow to the sink is c, then the requirements for the maximum flow are:

Maximize

$v={\displaystyle \underset{j:\left(1,j\right)\in E}{\sum }{C}_{1j}}$

Subjected to

${\displaystyle \underset{j:\left(j,i\right)\in E}{\sum }{C}_{ji}}-{\displaystyle \underset{j:\left(i,j\right)\in E}{\sum }{C}_{ij}}=0$ for i = 2, 3, 4, …, n − 1 (3)

$C_{ij}\ge 0$ for every edge $\left(i,j\right)\in E$ .

The algorithm of maximum flow (Ford-Fulkerson Algorithm) is given below [10] [11] .

Figure 1. Flow-conservation of intermediate node i.

Figure 2. Realization of flow-conservation.

2.2. Ford-Fulkerson Algorithm (G, s, t)

Inputs: Given a graph G = (V, E) with flow capacity c, a source nodes, and a sink node t where $s,t\in V$ .

Output: Compute a flow r from s to t of maximum value.

1) For all edges $\left(u,v\right)\in E$ ;

2) $r\left(u,v\right)=0\text{and}r\left(v,u\right)=0$ ;

3) Where there is a path p from s to t in G_r, such that $c_r\left(u,v\right)>0$ for each $\left(u,v\right)\in p$ ;

4) Do $c_r\left(p\right)=\min \left\{c_r\left(p\right)=\min \left\{c_r\left(u,v\right):\left(u,v\right)\in p\right\}\right\}$ ;

5) For each edge $\left(u,v\right)\in p$ ;

6) $r\left(u,v\right)=r\left(u,v\right)+c_r\left(p\right)$ ;

7) $c\left(u,v\right)=c\left(u,v\right)-c_r\left(p\right)$ ;

8) $r\left(v,u\right)=r\left(v,u\right)-c_r\left(p\right)$ ;

9) $c\left(v,u\right)=c\left(v,u\right)+c_r\left(p\right)$ .

Let us first consider a multi-hop wireless link, like Figure 3 where γ₁ is the SNR between the sender S and the first rely R₁, γ_i is the SNR between the (i − 1)th and the ith relay and ${\gamma }_{n+1}$ is that of between the nth relay and the destination D. The overall SNR between S and D is like equivalent capacitor in series connection or parallel resistor [12] :

${\gamma }_{eq}={\gamma }_1\Vert {\gamma }_2\Vert \cdots \Vert {\gamma }_{n+1}={\left({\displaystyle \underset{i=1}{\overset{n+1}{\sum }}1/{\gamma }_i}\right)}^{-1}.$ (4)

In this paper, we consider a wireless network with distributed repeaters like Figure 4 where each node (transmitter or receiver) and the repeater can communicate with one another to acquire channel knowledge, i.e. SNR between two

Figure 3. Multi-hop wireless link.

Figure 4. Multi-hop wireless network with distributed repeater.

nodes. The main objective of a sender S is to transmit data to the destination node D with maximum rate under the provision of multiple paths. The network equivalent matrix will be

$U=\left[\begin{array}{cccccc}{\gamma }_{S,R_1}& {\gamma }_{S,R_2}& 0& 0& 0& 0\\ 0& {\gamma }_{R_1,R_2}& 0& {\gamma }_{R_1,R_4}& 0& {\gamma }_{R_1,D}\\ {\gamma }_{R_2,R_1}& 0& {\gamma }_{R_2,R_3}& 0& 0& {\gamma }_{R_2,D}\\ 0& {\gamma }_{R_3,R_2}& 0& 0& 0& {\gamma }_{R_3,D}\\ {\gamma }_{R_4,R_1}& 0& 0& 0& 0& {\gamma }_{R_4,D}\\ 0& 0& 0& 0& 0& 0\end{array}\right].$ (5)

Once the SNR of a link is known, its channel capacity is estimated as $C_{R_i{R}_j}=B{\log }_2\left(1+{\gamma }_{R_i{R}_j}\right)$ in bps; where ${\gamma }_{R_i{R}_j}$ is the SNR between the ith and the jth relay and B is the bandwidth of the baseband transmission. The capacity matrix will be

$C=\left[\begin{array}{cccccc}{C}_{S,R_1}& C_{S,R_2}& 0& 0& 0& 0\\ 0& C_{R_1,R_2}& 0& C_{R_1,R_4}& 0& C_{R_1,D}\\ C_{R_2,R_1}& 0& C_{R_2,R_3}& 0& 0& C_{R_2,D}\\ 0& C_{R_3,R_2}& 0& 0& 0& C_{R_3,D}\\ C_{R_4,R_1}& 0& 0& 0& 0& C_{R_4,D}\\ 0& 0& 0& 0& 0& 0\end{array}\right].$ (6)

We apply the maximum flow algorithm with minimum cut theorem to evaluate the amount of data flow from the source S to the destination D using the capacity matrix as the input to the algorithm. The repetition of the maximum flow algorithm with rapid change in SNR of any link is time-consuming; hence, minimum cut theorem, like power flow of [9] can be applied.

There are a lot of possible cut of network in Figure 4 as:

1) The set of vertices of with source, X = {S, R₁, R₂, R₃, R₄} and its complementary set is, $\bar{X}$ = {D}. Now the cut, C(X, $\bar{X}$ ) = {(R₄, D), (R₁, D), (R₂, D), (R₃, D)}.

2) The set of vertices of with source, X = {S, R₁, R₂} and $\bar{X}$ = {R₄, R₃, D}, C(X, $\bar{X}$ ) = {(R₁,R₄), (R₁, D), (R₂, D), (R₂, R₃)}.

3) The set of vertices of with source, X = {S, R₂, R₃} and $\bar{X}$ = {R₁, R₄, D}, C(X, $\bar{X}$ ) = {(S, R₁), (R₂, R₁), (R₂, D), (R₃, D)}.

4) The set of vertices of with source, X = {S, R₁} and $\bar{X}$ = {R₄, R₃, R₂, D}, C(X, $\bar{X}$ ) = {(R₁, R₂), (R₁, R₄), (R₁, D), (S, R₂)}.

5) The set of vertices of with source, X = {S, R₂} and $\bar{X}$ = {R₄, R₃, R₁, D}, C(X, $\bar{X}$ ) = {(R₂, R₁), (R₂, R₃), (R₂, D), (S, R₁)}.

6) The set of vertices of with source, X = {S, R₁, R₂, R₃} and $\bar{X}$ = {R₄, D}, C(X, $\bar{X}$ ) = {(R₁, R₄), (R₁, D), (R₂, D), (R₃, D)}.

7) The set of vertices of with source, X = {S} and $\bar{X}$ = {R₁, R₂, R₃, R₄, D}, C(X, $\bar{X}$ ) = {(S, R₁), (S, R₂)}, etc.

The maximum flow from source to sink is the capacity of the minimum cut.

The basic algorithm of acquiring maximum flow is given below.

2.3. Algorithm

1) Sender first acquire channel knowledge, i.e. SNR of links, S-R_i, R_i-R_j, R_j-D; where i = 1, 2, 3, …, j = 1, 2, 3 … using shortest path algorithm.

2) The sender only selects m repeaters R_k; k = 1, 2, 3, …, m, where the link capacity of S-R_i, R_i-R_j, R_j-D, symbolically C_k ≥ C_th.

3) The sender creates a network with the selected nodes of Step 2; where the sending node S is considered as the source and destination node D as the sink.

4) Apply the maximum flow algorithm using minimum cut on the network of Step 3. The details of the algorithm will be shown in the next section.

5) The sender then sends data along the final augmenting paths.

6) In case of difficulty on the flow of data (message sent by D to S), repeat Steps 1 to 5.

2.4. Numerical Example

Let us consider the network of Figure 5. Let the source (S) be denoted as node 1 and the destination (D) as node 6, where 1 → 2, SNR = 5 dB; 1 → 4, SNR = 4 dB; 2 → 4, SNR = 3 dB; 4 → 5, SNR = 7 dB; 4 → 6, SNR = 5 dB; 2 → 6, SNR = 7 dB; 2 → 3, SNR = 6 dB; 3 → 6, SNR = 5 dB; 5 → 6, SNR = 3 dB. Here we use the notation i → j, SNR = a; indicates the connection between node i and j with SNR of a in absolute scale. Here Node 1 is source S and node 6 is destination D. Taking bandwidth of baseband transmission of B = 4 KHz, we get link capacity in bps as, 1 → 2, C = 10,340; 1 → 4, C = 9288; 2 → 4, C = 8000; 4 → 5, 12,000; 4 → 6, C = 10,340; 2 → 6, C = 12,000; 2 → 3, C = 11,229; 3 → 6, C = 10,340; 5 → 6, C = 8000.

Applying the Ford-Fulkerson algorithm, we obtain the maximum flow of 1.9628e+04 bps.

3. Results

We use MATLAB 16 to evaluate the link capacity of the network of Figure 6(a) and Figure 6(b), where both SNR in dB and capacity of each link in Kbps are shown. In Figure 6(a), Augmenting path coincides with the dual-hop parallel

Figure 5. Network of numerical example.

(a)(b)

Figure 6. Network with link SNR in dB and capacity in Kbps. (a) Augmenting path coincide with dual-hop parallel link; (b) Augmenting paths are different with dual-hop parallel link.

link (augmenting paths are heighted) but in Figure 6(b), Augmenting paths are different with dual-hop parallel link. Varying the SNR of link 1-2 and 1-4 we determine the capacity of the combined parallel link, i.e., 1-4-7 and 1-2-7 of Figure 6. The SNR of link 1-4-7 is found using the theory of parallel resistor:

${\text{SNR}}_{1\text{-}4\text{-}7}={\text{SNR}}_{1\text{-}4}\Vert {\text{SNR}}_{4\text{-}7}=\frac{{\text{SNR}}_{1\text{-}4}{\text{SNR}}_{4\text{-}7}}{{\text{SNR}}_{1\text{-}4}+{\text{SNR}}_{4\text{-}7}}$ ,

and that of link 1-2-7 is

Figure 7. Comparison of capacity of combined parallel and maximum flow model.

${\text{SNR}}_{1\text{-}2\text{-}7}={\text{SNR}}_{1\text{-}2}\Vert {\text{SNR}}_{2\text{-}7}=\frac{{\text{SNR}}_{1\text{-}2}{\text{SNR}}_{2\text{-}7}}{{\text{SNR}}_{1\text{-}2}+{\text{SNR}}_{2\text{-}7}}.$

Therefore, the total SNR will be ${\text{SNR}}_{1\text{-}4\text{-}7}+{\text{SNR}}_{1\text{-}2\text{-}7}$ . The maximum flow from the combined parallel link in Figure 6(a) is found as: 14.63 Kbps and that of Figure 6(b) provides 8.5124 Kbps, but the Ford-Fulkerson algorithm provides 19.6276 Kbps in both the cases.

A comparison of capacity of the combined parallel link and that of the Ford-Fulkerson algorithm is shown in Figure 7, where the capacity of the Ford-Fulkerson algorithm is found much higher than the case of the combined parallel link theory. When a link is outside of the augmenting path, the capacity remains fixed under the Ford-Fulkerson algorithm. Again, when a link of a network is not used under the theorem of multi-hop wireless link, then SNR of that link becomes independent of the capacity of the source to the destination. Such phenomenon is also visualized from Figure 7.

4. Conclusion

In this paper, the Ford-Fulkerson algorithm is applied in multi-hop wireless network which consists of several repeaters to determine the possible maximum data flow from the source to the destination. We have found better results under the Ford-Fulkerson algorithm compared to the generalized formula of multi-hop link. Under the Ford-Fulkerson algorithm the process time at the sender node decreases and also the capacity of the multi hop wireless link increases compare to the conventional theorem.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Mallick, K.K., Khan, A.R., Ahmed, M.M., Arefin, M.S. and Uddin, M.S. (2016) Modified EDMONDS-KARP Algorithm to Solve Maximum Flow Problems. Open Journal of Applied Sciences, 6, 131-140. https://doi.org/10.4236/ojapps.2016.62014
[2]	Surakhi, O.M., Qatawneh, M. and Al Ofeishat, H.A. (2017) A Parallel Genetic Algorithm for Maximum Flow Problem. International Journal of Advanced Computer Science and Applications, 8, 159-164. https://doi.org/10.14569/IJACSA.2017.080620
[3]	Saad, M. (2018) Optimal Multicommodity Spectrum-Efficient Routing in Multihop Wireless Networks. Hindawi. Wireless Communications and Mobile Computing, 2018, Article ID: 7985756. https://doi.org/10.1155/2018/7985756
[4]	Rahaman, A.S.M.M., Akhter, J., Jani, M.R. and Islam, M.I. (2018) Determination of Array Gain of Single Hop to Achieve the Performance of a 2-Hop Wireless Link. Journal of Computer and Communications, 6, 84-98. https://doi.org/10.4236/jcc.2018.67008
[5]	Chakraborty, P. and Prakriya, S. (2017) Secrecy Outage Performance of a Cooperative Cognitive Relay Network. IEEE Communications Letters, 21, 326-329. https://doi.org/10.1109/LCOMM.2016.2564380
[6]	Arzykulov, S., Nauryzbayev, G. and Tsiftsis, T.A. (2017) Underlay Cognitive Relaying System Over α-μ Fading Channels. IEEE Communications Letters, 21, 216-219. https://doi.org/10.1109/LCOMM.2016.2617043
[7]	Lim, S. and Ko, K. (2017) Approximation of Multi-Hop Relay to Dual-Hop Relay and Its Error Performance Analysis. IEEE Communications Letters, 21, 342-345. https://doi.org/10.1109/LCOMM.2016.2627054
[8]	Abdullah, N. and Hua, T.K. (2017) The Application of the Shortest Path and Maximum Flow with Bottleneck in Traffic Flow of Kota Kinabalu. Journal of Computer Science & Computational Mathematics, 7, 37-43. https://doi.org/10.20967/jcscm.2017.02.003
[9]	Werho, T., Vittal, V., Kolluri, S. and Wong, S.M. (2016) Power System Connectivity Monitoring Using a Graph Theory Network Flow Algorithm. IEEE Transaction on Power Systems, 31, 4945-4952. https://doi.org/10.1109/TPWRS.2016.2515368
[10]	Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009) Introduction to Algorithms. Third Edition, The MIT Press Cambridge, London.
[11]	Levitin, A. (2012) Introduction to Design and Analysis of Algorithms. Pearson Education, Boston.
[12]	Wu, G.W., Chen, X.J., Obaidat, M.S. and Lin, C. (2013) A High Efficient Node Capture Attack Algorithm in Wireless Sensor Network Based on Route Minimum Key Set. Journal of Security and Communication Networks, 6, 230-238.