Keywords

1 Introduction

With millimetre Wave (mmWave) small cells densely deployed in 5G for the applications, such as Internet of Things, Virtual Reality and so on, it is costly to connect the small cells with the core network, and to forward data to the gateway using fiber based backhaul [1]. Although mmWave wireless backhaul can be a competitive backhaul solution for the small cells in 5G networks, backhaul path planning is an important issue that needs to be addressed.

Recently, there is a few related works on designing wireless backhaul path. A joint routing and scheduling algorithm of backhaul link for ultra dense mmWave network is proposed in [2], and an maximum flow model based path planning method for the static mesh network with directional antenna is proposed in [3]. However, both of them do not consider the energy conservation issues. Ref. [4] presents a cognitive green topology management mechanism in 5G network. However, each node in the algorithm is assumed to be with cognitive ability, and the algorithm is not suitable to the scenes with massive data transmissions for mmWave backhaul network. Ref. [5] proposes an energy saving method which dynamically change the operating states of the small cells. Although the energy consumption can be saved, the algorithm assumed that all of the mmWave small cells could be connected to macro base station in one hop, so the path planning problem of the multi hop backhaul is not considered.

To the best knowledge of ours, there has been few related works focusing on designing the backhaul path with minimum energy consumption based on the maximum traffic in given time period for mmWave small cells, which reasonably motivates our work. The main contributions of this paper can be summarized as follows. Firstly, the problem of path planning which is aiming at minimizing energy consumption on the basis of maximizing the backhaul traffic is formulated as an integer-programming (IP) problem for ultra dense mmWave small cells. Secondly, the IP problem is made more easier to resolve using liner relaxation. Thirdly, a flow network based backhaul path planning algorithm (FBPA) is proposed to solve the problem. Finally, simulation results show that the proposed algorithm outperforms the existing path planning algorithms, in terms of backhaul traffic and energy consumption.

2 System Modelling and Problem Formulation

The network scenario that considered in this paper is shown in Fig. 1. Suppose that the network is composed of N small cells (SCs) that connect with mmWave link, and M gateway nodes that connect the core network using fiber. Without loss of generality, the number of the mmWave links between adjacent nodes can be equal, which is denoted as K.

Fig. 1.
figure 1

Network scenario.

Full size image

The network that shown in Fig. 1 can be modelled as an undirectional multi-graph, i.e., \(\mathcal {G}=\left( \mathcal {V},\mathcal {E}\right) \), \({\mathcal {V = \{ }}{{\mathcal {V}}_S}{\mathcal {,}}{{\mathcal {V}}_G}{\mathcal {\}}}\), where \(\mathcal {V}_{S} = \left\{ {{s_i}\left| {1 \le i \le N} \right. } \right\} \) denotes the node set of SCs, \(\mathcal {V}_{G} = \{ {{g_j} | {1 \le j \le M}} \}\) denotes the node set of gateways, and \({\mathcal {E = \{}}{{\mathcal {E}}_{SS}}{\mathcal {,}}{{\mathcal {E}}_{SG}} {\mathcal {\}}}\), where \({{\mathcal {E}}_{SS}}\mathrm{{ = }} \{ {e_{s_{i_1} \leftrightarrow s_{i_2}}^k | {1 \le {i_1},{i_2} \le N,{i_1} \ne {i_2},1 \le k \le K}} \}\), while \({{\mathcal {E}}_{SG}}\mathrm{{ = }} \{ {e_{s_{i} \rightarrow g_{j}}^k | {1 \le i \le N,1 \le j \le M,1 \le k \le K} } \}\) denotes the set of wireless edges from SC to gateway. Besides, denote \(T_{{i_1}{i_2}}^k\) and \(t^{k}_{i_{1}i_{2}}\) as the total number of available time slots and active slots on the k-th mmWave link \(e^{k}_{s_{i_{1}}\leftrightarrow s_{i_{2}}}\). Similarly, denote \(T^{k}_{ij}\) and \(t^{k}_{ij}\) as the total number of available time slots and active slots on the k-th mmWave link \(e^{k}_{s_{i} \rightarrow g_{j}}\), where \(0 \le t_{{i_1}{i_2}}^k \le T_{{i_1}{i_2}}^k\) and \(0 \le t_{ij}^k \le T_{ij}^k\). Let \(R^{k}_{i_{1}i_{2}}\),\(R^{k}_{ij}\) be the transmission rate within a slot on the k-th mmWave link \(e^{k}_{s_{i_{1}} \leftrightarrow s_{i_{2}}}\), \(e^{k}_{s_{i}\rightarrow g_{j}}\). \(L_{i}\) is the backhaul load of \(s_{i}\) generated by cell users. \(S_{j}\) is the total receiving capacity of \(g_{j}\). \(P^{k}_{i_{1}i_{2}}\), \(P^{k}_{ij}\) is the consumed energy within a time slot on the k-th mmWave link \(e^{k}_{s_{i_{1}}\leftrightarrow s_{i_{2}}}\), \(e^{k}_{s_{i}\rightarrow g_{j}}\).

The goal of the proposed problem is to plan the backhaul paths between each mmWave SC and gateway node, which aims to minimize the total energy consumption with maximum backhaul traffic in given time period. The problem is formulated as follows.

$$\begin{aligned} \min (\sum \limits _{{i_1} = 1}^N {\sum \limits _{{i_2} = 1}^N {\sum \limits _{k = 1}^K {t_{{i_1}{i_2}}^k \times P_{{i_1}{i_2}}^k + } } } \sum \limits _{i = 1}^N {\sum \limits _{j = 1}^M {\sum \limits _{k = 1}^K {t_{ij}^k \times P_{ij}^k} } } ) \end{aligned}$$
(1)
$$\begin{aligned} \textit{s.t.} \,\,\max \sum \limits _{i = 1}^N {\sum \limits _{k = 1}^K {\sum \limits _{j = 1}^M {t_{ij}^k\,\times \,} } } R_{ij}^k, \end{aligned}$$
(2)
$$\begin{aligned} \textit{s.t.}\,\, 0 \le t_{{i_1}{i_2}}^k \le T_{{i_1}{i_2}}^k, \mathrm{{ }}1 \le {i_1},{i_2} \le N,\mathrm{{ }}1 \le k \le K, \end{aligned}$$
(3)
$$\begin{aligned} 0 \le t_{ij}^k \le T_{ij}^k,\mathrm{{ }}1 \le i \le N,\mathrm{{ }}1 \le j \le M,\mathrm{{ }}1 \le k \le K, \end{aligned}$$
(4)
$$\begin{aligned} \mathrm{{ }}t_{{i_1}{i_2}}^k,t_{ij}^k \in {\mathcal{Z} }\mathrm{{ }} \forall i, 1\le i \le N, \end{aligned}$$
(5)
$$\begin{aligned} \mathrm{{ }}{L_i} + \sum \limits _{k = 1}^K {\sum \limits _{{i_1} = 1}^N {t_{{i_1}i}^k\,\times }\,} R_{{i_1}i}^k \le \sum \limits _{k = 1}^K {\sum \limits _{{i_2} = 1}^N {t_{i{i_2}}^k\,\times }\,} R_{i{i_2}}^k, \end{aligned}$$
(6)
$$\begin{aligned} \sum \limits _{k = 1}^K {\sum \limits _{i = 1}^M {t_{ij}^k\,\times }\,} R_{ij}^k \le {S_j},\forall j,1 \le j \le M, \end{aligned}$$
(7)

The problem is denoted as Problem-I, where Eqs. (3) and (4) mean that number of actual active slots within the mmWave links do not exceed the maximum number of active slots. Equation (5) denotes that the number of actual active slots is an integer, where \({\mathcal{Z}}\) is the set of integers. Equation (6) denotes that for any one of mmWave SCs, the total amount of data being sent out is no less than total amount of data being received and the traffic loads that generated by itself. Equation (7) represents that the total amount of data that flows into the gateway node is no more than the maximum capacity of the fiber. Problem-I is an IP problem, which is always an NP-hard problem. A new variable \(d_{{i_1}{i_2}}^k\) is introduced, which denotes the amount of data on the k-th backhaul link from \({s_{{i_1}}}\) to \({s_{{i_2}}}\), i.e., \({e_{s_{{i_1}} \rightarrow s_{{i_2}}}^k}\). Similarly, the other variable \(d_{{i}{j}}^k\) is also introduced, which denotes the amount of data on the k-th backhaul link from \({s_{{i}}}\) to \({g_{{j}}}\), i.e., \({e_{s_{{i}} \rightarrow g_{{j}}}^k}\). The relationship between variables \(d_{{i_1}{i_2}}^k\), \(d_{{i}{j}}^k\) and \(t^{k}_{i_{1}i_{2}}\), \(t^{k}_{ij}\) can be obtained as

$$\begin{aligned} t_{{i_1}{i_2}}^k = \left\lceil {\frac{{d_{{i_1}{i_2}}^k}}{{R_{{i_1}{i_2}}^k}}} \right\rceil , t_{ij}^k = \left\lceil {\frac{{d_{ij}^k}}{{R_{ij}^k}}} \right\rceil . \end{aligned}$$
(8)

Then, the Eq. (2) can be rewritten as

$$\begin{aligned} \mathrm{{max}}\sum \limits _{i = 1}^N {\sum \limits _{j = 1}^M {\sum \limits _{k = 1}^K {d_{ij}^k} } }. \end{aligned}$$
(9)

The Eqs. (3)–(4) can be rewritten as

$$\begin{aligned} 0 \le d_{{i_1}{i_2}}^k \le T_{{i_1}{i_2}}^k \times R_{{i_1}{i_2}}^k,\mathrm{{ }}1 \le {i_1},{i_2} \le N,\mathrm{{ }}1 \le k \le K, \end{aligned}$$
(10)
$$\begin{aligned} 0 \le d_{ij}^k \le T_{ij}^k \times R_{ij}^k,\mathrm{{ }}0 \le i \le N,\mathrm{{ }}1 \le j \le M,\mathrm{{ }}1 \le k \le K, \end{aligned}$$
(11)

respectively. For each \({s_{{i}}}\), Eq. (6) can be rewritten as

$$\begin{aligned} {L_i} + \sum \limits _{k = 1}^K {\sum \limits _{{i_1} = 1}^N {d_{{i_1}i}^k} } = \sum \limits _{k = 1}^K {\sum \limits _{{i_2} = 1}^N {d_{i{i_2}}^k} }, \forall i, 1\le i\le N, \end{aligned}$$
(12)

and the constraint (7) can be rewritten as

$$\begin{aligned} \sum \limits _{k = 1}^K {\sum \limits _{i = 1}^M {d_{ij}^k} } \le {S_j},\forall j,1 \le j \le M. \end{aligned}$$
(13)

Finally, denote \( \eta _{i_{1}i_{2}}^{k} \) and \( \eta _{ij}^{k} \) as the energy efficiencyFootnote 1 on the k-th transmission link between \(s_{i_{1}}\) and \(s_{i_{2}}\), \(s_{i}\) and \(s_{j}\), which are given as \(\eta _{{i_1}{i_2}}^k = \frac{{P_{{i_1}{i_2}}^k}}{{R_{{i_1}{i_2}}^k}}\), \(\eta _{ij}^k = \frac{{P_{ij}^k}}{{R_{ij}^k}}\). Thus, the objective of Problem-I defined in formula (1), can be rewritten as

$$\begin{aligned} \sum \limits _{{i_1} = 1}^N {\sum \limits _{{i_2} = 1}^N {\sum \limits _{k = 1}^K {d_{{i_1}{i_2}}^k \times \eta _{{i_1}{i_2}}^k + } } } \sum \limits _{i = 1}^N {\sum \limits _{j = 1}^M {\sum \limits _{k = 1}^K {d_{ij}^k \times \eta _{ij}^k} } }. \end{aligned}$$
(14)

Therefore, Problem-I can be transformed as a linear program (LP) problem. The LP problem above is denoted as Problem-II. Note that Eq. (12) satisfy the demands of flow conservation in the flow network model, Eqs. (10) and (11) satisfy the capacity constraints of the flow network model. Therefore, the method named minimum cost maximum flow in the flow network model is used to obtain the optimal solution of Problem-II, and this optimal solution is considered as an approximate solution of the Problem-I.

3 The Proposed FBPA Algorithm

Note that mmWave backhaul network \(\mathcal {G}=\left( \mathcal {V},\mathcal {E}\right) \) is an undirected multi graph, where there exist multiple undirected edges between two adjacent nodes. Therefore, to solve Problem-II, the FBPA algorithm is proposed. Firstly, the undirected multigraph is transformed into a directed multi-graph. Secondly, the directed multi-graph is transformed into a directed simple graph. Thirdly, a flow network graph is constructed based on the transformed directed simple graph, the problem with minimum cost and maximum traffic of the flow network graph is solved using the Push-Relabel method.

  • Step 1: As shown in Fig. 2, any two connected nodes \({s_{{i_1}}}\) and \({s_{{i_2}}}\) in the undirected multi-graph \(\mathcal {G}=\left( \mathcal {V}, \mathcal {E}\right) \) are transformed into two node sets \(\{{{s_{i_1^{in}}},{s_{i_1^{out}}}} \}\), \(\{{{s_{i_2^{in}}}, {s_{i_2^{out}}}} \}\), where \({s_{i_1^{in}}}\) and \({s_{i_2^{in}}}\) are virtual entry nodes, which are belong to the set \({\mathcal {V}}_{s_{in}}\). In addition, \({s_{i_1^{out}}}\) and \({s_{i_2^{out}}}\) are virtual export nodes, which are belong to the set \({\mathcal {V}}_{s_{out}}\).

  • Step 2: The edges \({e_{{s_{i_1^{in}}} \rightarrow {s_{i_1^{out}}}}}\) and \({e_{{s_{i_2^{in}}} \rightarrow {s_{i_2^{out}}}}}\) are added respectively, where \({e_{{s_{i_1^{in}}} \rightarrow {s_{i_1^{out}}}}}\) and \({e_{{s_{i_2^{in}}} \rightarrow {s_{i_2^{out}}}}}\) are belong to the set \(\mathcal {E}_{{s_{in}}{s_{out}}}\). Then the undirected edges (denoted as \(e_{{s_{{i_1}}} \leftrightarrow {s_{{i_2}}}}^k\)) between \({s_{{i_1}}}\) and \({s_{{i_2}}}\) are transformed into a directed edges set \(\{ {e_{{s_{i_1^{out}}} \rightarrow {s_{i_2^{in}}}}^k, e_{{s_{i_2^{out}}} \rightarrow {s_{i_1^{in}}}}^k} \}\).

  • Step 3: As shown in Fig. 3, k virtual entry nodes \(s_{i_1^{in}}^k\) and \(s_{i_2^{in}}^k\) that belong to the set \({\mathcal {V}_{s_{in}^k}}\), are added for \({s_{i_1^{in}}}\) and \({s_{i_2^{in}}}\) in the directed multi-graph. Similarly, k virtual export nodes \(s_{i_1^{out}}^k\) and \(s_{i_2^{out}}^k\) that belong to the set \({\mathcal {V}_{s_{out}^k}}\), are introduced for \({s_{i_1^{out}}}\) and \({s_{i_2^{out}}}\).

  • Step 4: The k-th edge from \(s_{i_1^{out}}\) to \(s_{i_2^{in}}\) in the directed multi-graph, i.e., \(e_{{s_{i_1^{out}}} \rightarrow {s_{i_2^{in}}}}^k\) is transformed into a set of edges \(\{ e_{{s_{i_1^{out}}} \rightarrow s_{i_1^{out}}^k}, e_{s_{i_1^{out}}^k \rightarrow s_{i_2^{in}}^k},e_{s_{i_2^{in}}^k \rightarrow {s_{i_2^{in}}}}\}\), \(e_{{s_{i_2^{out}}} \rightarrow {s_{i_1^{in}}}}^k\) is transformed into a set of edges \(\{ e_{{s_{i_2^{out}}} \rightarrow s_{i_2^{out}}^k}, e_{s_{i_2^{out}}^k \rightarrow s_{i_1^{in}}^k}, e_{s_{i_1^{in}}^k \rightarrow {s_{i_1^{in}}}} \}\). For clarity, the sets are separately defined as \(\mathcal E_{s_{out}s_{out}^k}= \{e_{{s_{i_1^{out}}} \rightarrow s_{i_1^{out}}^k}, e_{{s_{i_2^{out}}} \rightarrow s_{i_2^{out}}^k}\}\), \(\mathcal {E}_{{s_{out}^ks_{in}^k}} = \{ e_{s_{i_1^{out}}^k \rightarrow s_{i_2^{in}}^k}, e_{s_{i_2^{out}}^k \rightarrow s_{i_1^{in}}^k} \}\), \(\mathcal {E}_{s_{in}^k{s_{in}}} = \{e_{s_{i_1^{in}}^k \rightarrow s_{i_1^{in}}}, e_{s_{i_2^{in}}^k \rightarrow s_{i_2^{in}}} \}\).

  • Step 5: A virtual source node x and a virtual destination node y are introduced. Correspondingly, the edges from x to \({s_{i_1^{in}}}\) and \({s_{i_2^{in}}}\) are introduced, i.e., \({e_{x \rightarrow {s_{i_1^{in}}}}}\) and \({e_{x \rightarrow {s_{i_2^{in}}}}}\), and the set of which is denoted as \({\mathcal {E}_{x{s_{in}}}}\). Moreover, the edges from \({g_{{j^{out}}}}\) to y are introduced, i.e., \({e_{{g_{{j^{out}}}} \rightarrow y}}\), and the set of which is denoted as \({\mathcal {E}_{{g_{out}}y}}\).

  • Step 6: The attributes of each edge in the directed simple graph can be assigned as follows. In \({\mathcal {E}_{x{s_{in}}}}\), the capacity and cost of each edge are given as \(a({e_{x \rightarrow {s_{i^{in}}}}})=L_i,c({e_{x \rightarrow {s_{i_1^{in}}}}})=0\). In \({\mathcal {E}_{s_{in}^k{s_{in}}}}\), \({\mathcal {E}_{{s_{in}}{s_{out}}}}\), \({\mathcal {E}_{{s_{out}}s_{out}^k}}\), \({\mathcal {E}_{g_{in}^k{g_{in}}}}\) and \(\mathcal {E}_{{g_{in}}{g_{out}}}\), the capacity and cost of each edge are given in Eq. (15). In \(\mathcal {E}_{_{s_{out}^ks_{in}^k}}\) and \(\mathcal {E}_{_{s_{out}^kg_{in}^k}}\), the capacity and cost of each edge are given in Eq. (16). Besides, in \(\mathcal {E}_{{g_{out}}y}\), the capacity and cost of each edge are given as \(a({e_{{g_{{j^{out}}}} \rightarrow y}})=S_j\), \(c({e_{{g_{{j^{out}}}} \rightarrow y}}) = 0\).

    $$\begin{aligned} \left\{ \begin{array}{l} a({e_{s_{i^{in}}^k \rightarrow {s_{i^{in}}}}})=a({e_{{s_{i^{in}}} \rightarrow {s_{i^{out}}}}})=a({e_{{s_{i^{out}}} \rightarrow s_{i^{out}}^k}})=a({e_{g_{{j^{in}}}^k \rightarrow {g_{{j^{in}}}}}})=a({e_{{g_{{j^{in}}}} \rightarrow {g_{{j^{out}}}}}})=Inf \\ c({e_{s_{i^{in}}^k \rightarrow {s_{i^{in}}}}}) = c({e_{{s_{i^{in}}} \rightarrow {s_{i^{out}}}}}) = c({e_{{s_{i^{out}}} \rightarrow s_{i^{out}}^k}}) = c({e_{g_{{j^{in}}}^k \rightarrow {g_{{j^{in}}}}}}) = c({e_{{g_{{j^{in}}}} \rightarrow {g_{{j^{out}}}}}}) = 0 \\ \end{array} \right. \end{aligned}$$
    (15)
    $$\begin{aligned} \left\{ \begin{array}{l} a({e_{s_{i_1^{out}}^k \rightarrow s_{i_2^{in}}^k}}) = a({e_{s_{i_2^{out}}^k \rightarrow s_{i_1^{in}}^k}}) = T_{{i_1}{i_2}}^k \times R_{{i_1}{i_2}}^k,\;a(e_{{s_i} \rightarrow {g_j}}^k) = T_{ij}^k \times R_{ij}^k \\ c({e_{s_{i_1^{out}}^k \rightarrow s_{i_2^{in}}^k}}) = c({e_{s_{i_2^{out}}^k \rightarrow s_{i_1^{in}}^k}}) = \eta _{{i_1}{i_2}}^k,\; c(e_{{s_i} \rightarrow {g_j}}^k) = \eta _{ij}^k \end{array} \right. \end{aligned}$$
    (16)

  • Step 7: The minimum cost with maximum flow of \({\mathcal{G}_m} = \left( {{\mathcal{V}_m},{\mathcal{E}_m}} \right) \) can be obtained, using the Push-Relabel algorithm. Therefore, the values of data flow on each edge of the Problem-II is obtained as \(\mathcal {F}_m = \{f_{i_1^{out}i_2^{in}}^k,f_{{i^{out}}{j^{in}}}^k\}\).

Fig. 2.
figure 2

Undirected multi-graph is transformed into directed multi-graph.

Full size image
Fig. 3.
figure 3

Directed multi-graph is transformed into directed simple graph.

Full size image

According to the solution of the Problem-II, it can be transformed into the solution of the Problem-I as \(t_{{i_1}{i_2}}^k = \left\lceil {\frac{{f_{i_1^{out}i_2^{in}}^k}}{{R_{{i_1}{i_2}}^k}}} \right\rceil , t_{ij}^k = \left\lceil {\frac{{f_{{i^{out}}{j^{in}}}^k}}{{R_{ij}^k}}} \right\rceil \). The maximum amount of data and the minimum energy consumption are given as

$$ \left\{ \begin{array}{l} {d_{\max }} = \sum \limits _{i = 1}^N {\sum \limits _{j = 1}^M {\sum \limits _{k = 1}^K {t_{ij}^k \times R_{ij}^k} } } \\ {P_{\min }} = \sum \limits _{{i_1} = 1}^N {\sum \limits _{{i_2} = 1}^N {\sum \limits _{k = 1}^K {t_{{i_1}{i_2}}^k\times P_{{i_1}{i_2}}^k + } } } \sum \limits _{i = 1}^N {\sum \limits _{j = 1}^M {\sum \limits _{k = 1}^K {t_{ij}^k \times P_{ij}^k} } } \end{array} \right. $$

4 Simulation Results

In the simulations, SCs are uniformly distributed within 500 m * 500 m square, and the maximum distance between two SCs or SC and gateway node is 120 m. There exist four gateway nodes respectively. Besides, it is assumed that line-of-sight (LOS) mmWave links are located at 60 GHz, the bandwidth of each is 2G MHz. Other simulation parameters are given [6]. We compare our proposed FBPA algorithm with the shortest path algorithm and exhaustive algorithm.

Figure 4 are the path selection results generated from FBPA algorithm. It can be seen that FBPA algorithm can establish multiple paths to multiple gateway nodes, e.g., SC that marked with rectangle in Fig. 4.

Fig. 4.
figure 4

FBPA path selection.

Full size image
Fig. 5.
figure 5

Backhaul traffic vs load of SC.

Full size image
Fig. 6.
figure 6

EC vs load of SC.

Full size image
Fig. 7.
figure 7

EE vs number of SCs.

Full size image

Figures 5 and 6 show the backhaul traffic and energy consumption against backhaul load of each SC. As shown in Fig. 5, with the constantly increasing of the load, the proposed FBPA algorithm and the exhaustive algorithm outperform the shortest path algorithm, this is because the SCs in both algorithms can select multiple paths to different gateway nodes. When the backhaul load of each SC exceeds 14 Gbit, the backhaul traffic of the proposed FBPA algorithm outperforms the shortest path algorithm by nearly 62% and is close to the exhaustive algorithm, the difference of which is less than 5%. As shown in Fig. 6, the energy consumption for the three algorithms increase when the backhaul load is relatively small, and the network energy consumption using shortest path algorithm is almost highest until the backhaul load is about 11 Gbit, this is because the path selection in the shortest path algorithm is only based on the distance, the energy consumption is not considered. Moreover, the gap between the FBPA algorithm and the exhaustive algorithm is small, which is about 10%.

Figure 7 shows the average energy efficiency of three algorithms against the number of SCs, where the traffic load of each SC is 10 Gbits, and the number of SCs varies from 50 to 60. The average energy efficiency is defined as amount of transmission traffic within unit joule. As we can see from Fig. 7, with the increase number of SCs, the average energy efficiency of three algorithm increase. Although the average energy efficiency of the FBPA algorithm is lower than the exhaustive algorithm’s, it much better than the shortest path algorithm. The gain between FBPA algorithm and the shortest path algorithm is nearly 18%.

5 Conclusions

We have studied the backhaul path planning problem in a mmWave small cell network. We aimed at exploring the path planning with minimum energy consumption based on maximum traffic in given time slot. The problem is formulated as an IP problem, then the IP problem is transformed into a easier LP using liner relaxation. FBPA is proposed to find the approximate solution of the IP problem. Extensive simulation are conducted and the efficiency of the proposed algorithm are demonstrated.