# A Simple and Efficient Way to Save Energy in Multihop Wireless Networks with Flow Aggregation

Authors: Alexandre Laube; Dominique Quadri; Steven Martin; Khaldoun Al Agha
Journal: Journal of Computer Networks and Communications
 (2019)

---

## Abstract

Today, whether in industry, research, or civil applications, there are many incentives to reduce the energy footprint of automated systems. In multihop wireless networks, the main objective in that regard is usually to maximize the lifetime of the network by distributing the load over all nodes. In this paper, we improve a solution that aggregates flows to optimize the number of nodes that can be turned off. We introduce interference awareness in a routing metric designed to aggregate flows to avoid overloading the network and to preserve the quality of service required by the flows. This way, it becomes possible to integrate this metric into classical shortest path routing algorithms that do not consider interference. We also show that flow aggregation and overall energy consumption are equivalent problems.


---

## Body

## 1. Introduction

For a long time, web services, social networking, mail, and online shopping contributed to develop a kind of network centralization. It is now common to see the application layer of the network running on large data centers that aggregate tons of data and provide services to users. Moreover, the adoption of cellular phones, followed by smartphones, has led to the deployment of wireless network architectures based on wireless access points, creating fully centralized services from the user’s perspective at the application and network layers. Although this type of architecture can achieve high performance, its deployment and maintenance can be very costly both financially and in terms of energy. Indeed, if a network provider wishes to cover a new area, for example, a large number of antennas must be deployed. For each of them, it must buy or rent a place, build the infrastructure to support the antenna, wire it up to its backbone network, and finally supply it. In addition, achieving full and effective coverage requires addressing spatial constraints that can lead to many logistical, financial, or political problems. Furthermore, we have seen an increasing demand in terms of network capacity in recent years. Mainly caused by HD video and audio streaming as well as social networking applications that create a lot of data, it has highlighted the limitations of such centralized architectures. Thus, recent work on edge computing [1] or fog networking [2] tends to redistribute part of the network’s resources and services as close as possible to end users in order to increase the network’s performance and energy efficiency.Developed in parallel, multihop wireless (or ad hoc) networks were mainly dedicated to specific applications such as satellite systems, sensor networks, device-to-device communications, or areas without infrastructure (e.g., military field, disaster recovery, and last mile) covering. The low popularity of these networks is due to the extreme difficulty in optimizing these distributed systems, which leads to lower performance than centralized wireless networks. Nevertheless, multihop wireless networks have an advantage in terms of flexibility that allows them to be deployed almost anywhere, as long as there is a way to power the nodes. Moreover, interest in these networks will certainly increase in the coming years with the expansion of the Internet of Things.In addition, since multihop wireless networks represent an increasingly important part of our society’s total energy consumption, a lot of work must be done to minimize it. In the past, most of the work on energy efficiency in ad hoc networks focused on wireless sensor networks and aimed at maximizing their lifespan. Although perfectly legitimized by energy constraints (e.g., battery-powered nodes), the proposed solutions are based on the basic principle of uniformly distributing the load over the entire network. In this context, nodes reduce their energy supply at the same location. However, this approach becomes less relevant when the network is composed of more traditional nodes (or things) that are not necessarily battery powered, such as in MESH networks, and where radio components are not the most consuming.In the case of more complex wireless nodes (such as Wi-Fi routers, connected vehicles, and urban equipment), a static amount of energy is consumed by turning them on. Hence, we proposed the use of flow aggregation, which consists of routing flows along common paths to maximize the number of nodes that can be turned off to minimize overall energy consumption. This paradigm is based on the observation that the energy cost of data transmission is lower than the static energy cost required to have a node turned on. It then becomes more interesting to make nodes process more data and turn off others that can be unloaded.In this paper, we confirm this observation by comparing our flow aggregation routing with a routing solution that minimizes the overall energy consumption of the network. We also extend our Flow Aggregation MEtric [3] (FAME) so that it considers interference and prevents excessive aggregation. Our contributions are twofold:(i)
We show that the maximization of flow aggregation and the minimization of overall energy consumption are equivalent in the assumption that most of the energy consumption is induced by the powering up of the nodes. In the following, this part will be called the static energy consumption of a node.(ii)
We extend our Flow Aggregation MEtric by taking into account interference to avoid network overload.These contributions are evaluated by simulation using CPLEX [4] and adopting the same methodology and parameters as in [3, 5]. To obtain our results, we first generate 5 random networks of 49 nodes. Then for each of these networks, we create random sets of flows of different size. For each identified size, we create 100 scenarios where we insert those flows. For all of the available configurations, we will route flows using the routing algorithms that will be presented in this paper. Then we analytically calculate average values, with their 95% confidence interval, over all of these simulated configurations. The parameters we will illustrate in this paper are global energy consumption, number of used (active) nodes, and network load.The remainder of this paper is organized as follows. In Section2, we present the related work on energy saving in multihop wireless networks at the routing layer. Section 3 defines the models and notations we use. Section 4 is dedicated to our solution minimizing the overall energy consumption of the network. In Section 5, we extend our heuristic solution to the flow aggregation problem to avoid network congestion. We finally conclude and give future works in Section 6.


## 2. Related Work

The state of the art defines two types of routing protocols: reactive and proactive. In the former, a node calculates a route to reach the destination when it has data to send. The most common protocols in this family are Dynamic Source Routing (DSR) [6] and Ad hoc On-Demand Distance Vector (AODV) [7]. However, these two protocols do not integrate any energy considerations. That is why extensions have been proposed to make them more effective on this point. In [8], the authors use the residual energy of nodes to define energy states and adapt the behavior of the nodes. When the residual energy of a node is above a threshold, it is in a normal state and performs AODV normally. When it is below a threshold, the node is set in a warning state and will add a delay before forwarding route request messages to reduce the probability to be selected as a relay. Finally, when the residual energy is below a critical threshold, the node stops forwarding route request messages so that it no longer becomes a relay. This solution gives good results in improving the lifetime of the network but does not allow to conclude on the overall energy consumption or to take into account interference. Similarly, the authors in [9] propose to insert a delay proportional to the missing residual energy before forwarding a route response message. In this way, the more a node has depleted its energy, the less likely it is to be selected as a relay. The same comment applies here. Although the lifetime of the network has been improved, no conclusions have been drawn on the overall energy consumption, except that it has been balanced on all nodes and that interference is still not considered.In proactive protocols, the Optimized Link State Routing (OLSR) protocol [10] is the most popular for multihop wireless networks. Like DSR and AODV, the initial specification of OLSR does not take into account energy consumption. In [11], the authors propose to use a metric based on the residual energy and node consumption to select new multipoint relays (MPRs), which are nodes basically selected in the network to optimize flooding and forwarding processes. The routing algorithm can also be modified in order to use energy routing metrics such as Maximum Transmission Power Routing [12], Max-Min Battery Cost Routing [13], or Minimum Drain Rate [14]. Once again, this solution improves results in terms of network lifetime but does not focus on the overall energy consumption of the network.Most of the work dealing with energy savings in multihop wireless networks tends to focus on wireless sensor networks. Thus, considering that nodes are powered by batteries, the problem is to improve the lifetime of the network. However, multihop wireless networks can be composed of other types of nodes. These nodes can have generators to draw power from the environment or may be powered by a renewable energy source. This is the case for mesh networks that have different energy constraints. Since the nodes can be switched on continuously, the objective of energy saving in mesh networks is to reduce the energy footprint of the network globally. A solution based on integer linear programming to route flows in order to maximize the number of nodes that can be turned off is proposed in [15]. Nevertheless, this approach is designed for operator-led networks and assumes that the destination nodes of the flows are gateways that provide Internet access. Moreover, this solution requires a global view of the network and the optimal solution is obtained by solving the optimization problem iteratively while increasing the constraint on the number of nodes to be turned off until no solution can be found.In [5], we proposed a solution also based on integer linear optimization to achieve this optimum in one iteration for any set of source and destination nodes while maintaining the quality of service (QoS) in terms of throughput. However, this solution requires a lot of computing power to reach the optimum, which makes it inapplicable to networks with high flow fluctuations. We solved this problem in [3] by developing a routing metric to allow the shortest path routing algorithms to aggregate flows close to optimality, increasing the number of nodes that can be turned off. However, this work does not take into account interference, which leads to overloading the network areas where flows are aggregated. We propose a solution to this problem in Section 5.2.


## 3. Models and Notations

### 3.1. Network Model

Usually, multihop wireless networks are represented with a directed graph notedG=V,E where V is the set of nodes and E is the set of links between these nodes. We consider that a couple i,j belongs to E if node i can send data to node j. This link is defined by a ranged communication model, meaning that node j can receive data from i if and only if the distance between them is less than or equal to the transmission range of node i. In this paper, we also consider that nodes share the same transmission range. Thus, if a link i,j is in E, then link j,i is too.


### 3.2. Interference Model

Interference can be modeled using two different methods [16]. A first one considers interference as noise at the physical layer and its impact on the signal as an interference ratio. However, since our work focuses on the network layer, we use the second approach. Indeed, we consider that any node j can successfully receive a transmission from node i if the distance between them is lower than the distance between j and any other node transmitting at the same time. This model allows us to determine conflicting links in the network; they are links that cannot be used at the same time as they interfere with each other. This approach can be approximated using a k-hop interference model, meaning that a node interferes with its neighborhood up to a distance of k hops. In this paper, we set k to 2 as in [17].Then, we use the conflicts between the links to build a conflict graph [18] and derive cliques [19] from it. These cliques are sets of interfering links that cannot be used at the same time in the network. Finally, we define the utilization rate of a clique as the sum of the utilization rates of links that compose it. A network is considered to be overloaded if there exists a clique whose utilization rate is above 100%.


### 3.3. State Energy Model

To estimate the energy consumption of the network, we use a state energy model [20, 21]. The energy consumption of a node is calculated in function of the time spent by the node in each state. A node can be in four operating states, each one having a specific energy consumption:(i)
Transmission mode (Tx), the most energy-consuming state. The node sends data by activating its transceiver to emit radio signals that can be received by every node in its transmission range.(ii)
Reception mode (Rx), using less energy than the previous one. In this state, the node activates its receiver to interpret incoming radio signals and convert them into digital data before sending them to the upper layer of the communication stack.(iii)
Idle mode, in which a node spends most of the time. This is an intermediary state from which a node can be set either in Tx mode or in Rx mode. Although a node remains passive in this state, its ability to detect the need to send or receive data means that the idle mode consumes a comparable amount of energy as the reception mode.(iv)
Sleep mode, where the node shuts down most of its components, leading to a significant reduction in its energy consumption. Thus, the node becomes unable to transmit or receive data. As it also makes the node unable to detect network events, this state can only be left through user or algorithmic interruptions.


### 3.4. Notations

We present in Figure1 below the notations used in the rest of the paper.Figure 1
Notations used throughout this paper.


## 3.1. Network Model

Usually, multihop wireless networks are represented with a directed graph notedG=V,E where V is the set of nodes and E is the set of links between these nodes. We consider that a couple i,j belongs to E if node i can send data to node j. This link is defined by a ranged communication model, meaning that node j can receive data from i if and only if the distance between them is less than or equal to the transmission range of node i. In this paper, we also consider that nodes share the same transmission range. Thus, if a link i,j is in E, then link j,i is too.


## 3.2. Interference Model

Interference can be modeled using two different methods [16]. A first one considers interference as noise at the physical layer and its impact on the signal as an interference ratio. However, since our work focuses on the network layer, we use the second approach. Indeed, we consider that any node j can successfully receive a transmission from node i if the distance between them is lower than the distance between j and any other node transmitting at the same time. This model allows us to determine conflicting links in the network; they are links that cannot be used at the same time as they interfere with each other. This approach can be approximated using a k-hop interference model, meaning that a node interferes with its neighborhood up to a distance of k hops. In this paper, we set k to 2 as in [17].Then, we use the conflicts between the links to build a conflict graph [18] and derive cliques [19] from it. These cliques are sets of interfering links that cannot be used at the same time in the network. Finally, we define the utilization rate of a clique as the sum of the utilization rates of links that compose it. A network is considered to be overloaded if there exists a clique whose utilization rate is above 100%.


## 3.3. State Energy Model

To estimate the energy consumption of the network, we use a state energy model [20, 21]. The energy consumption of a node is calculated in function of the time spent by the node in each state. A node can be in four operating states, each one having a specific energy consumption:(i)
Transmission mode (Tx), the most energy-consuming state. The node sends data by activating its transceiver to emit radio signals that can be received by every node in its transmission range.(ii)
Reception mode (Rx), using less energy than the previous one. In this state, the node activates its receiver to interpret incoming radio signals and convert them into digital data before sending them to the upper layer of the communication stack.(iii)
Idle mode, in which a node spends most of the time. This is an intermediary state from which a node can be set either in Tx mode or in Rx mode. Although a node remains passive in this state, its ability to detect the need to send or receive data means that the idle mode consumes a comparable amount of energy as the reception mode.(iv)
Sleep mode, where the node shuts down most of its components, leading to a significant reduction in its energy consumption. Thus, the node becomes unable to transmit or receive data. As it also makes the node unable to detect network events, this state can only be left through user or algorithmic interruptions.


## 3.4. Notations

We present in Figure1 below the notations used in the rest of the paper.Figure 1
Notations used throughout this paper.


## 4. Optimization of Overall Energy Consumption

Integer Linear programming (ILP) is a powerful mathematical tool used to study optimality in many areas of research. In networking, it is typically used to solve network provisioning, performance improvement, and routing problems [23–25]. This approach has the advantage of being extremely modular because a change in the properties of the routing algorithm consists only in modifying all the constraints, and possibly the objective function, of the linear program. We use I2ILP, denoted the shortest path in this paper and defined in [17], as the basis for our formulation that we extend to deliver a set of flows instead of a single flow on the shortest path. The resulting ILP model can be formulated as depicted in Figure 2.Figure 2
Shortest path routing algorithm using integer linear programming formulation.This formulation models a shortest path routing algorithm. Here, the objective function minimizes the sum of the paths’ lengths, which is calculated as the sum of the weight of nodes that make the path, used to route a set of flows. The first eight constraints are state-of-the-art constraints used to model a routing algorithm and will be common to all the solutions we will present later in this paper.Constraint (1) is the capacity constraint and is based on the interference model described in Section3.2. This constraint ensures that the utilization rate of any clique will never be greater than 100% and then prevents to overload some parts of the network. Constraint (2) models the flow conservation rule. Constraints (3) and (4) guarantee that a flow does not loop back to its source and that a source uses one of its out links to send the flow. Similarly, constraints (5) and (6) prevent a flow to leave its destination and make sure it is received on one of the inlinks of its destination. Constraint (7) is the QoS constraint and ensures that each flow can send its traffic with the expected bit rate demand. Constraint (8) models the single path routing, meaning that a flow cannot be split into several paths. Finally, constraint (9) calculates the length of the path used by each flow according to links associated with it. For this purpose, all links have a weight according to their length. If this function gives a constant value to each link, the formulation is then like routing a set of flows over the shortest paths in terms of hops.


### 4.1. Minimizing the Energy Consumption

In this paper, we aim at minimizing the overall energy consumption of the network by allowing unused nodes to be turned off (or put into sleep mode) instead of remaining in idle mode. We model this behavior by a set of linear constraints that we integrate into the previous ILP. Figure3 shows the ILP formulation that optimally routes a set of flows over the network while minimizing the overall energy consumption.Figure 3
ILP formulation for minimal energy consumption routing.In this formulation, we have modified the objective function so that the program is now minimizing the overall energy consumption of the network. The first unnumbered constraints are the same as those seen above and are mandatory to implement the routing algorithm regardless of the objective function. Constraint (1) calculates the total energy consumption of any nodei, that is, Ei, as the sum of energy consumed when it is in transmission state EiT, in reception state EiR, and in passive state EiP (i.e., neither transmitting or receiving), respectively. Constraints (2), (3), (4), and (5) are about the energy consumption of a node when it is in the four different states. These values are calculated according to the energy consumption related to each state and the time spent in it. We consider that a node always transmits at the highest available bit rate in order to maximize the time spent in the passive mode, allowing to save more energy [20]. Thus, we can deduct from the utilization rates of the links the proportion of time a node spends in transmission and reception modes. The reverse proportion is then used as the time spent by the node in a passive (idle or sleep) mode. Finally, to save energy, constraints (6.1) and (6.2) are used to determine if a node is used and set its passive mode accordingly. We consider that any node i is useful to the network if it is used as a relay to route flows. This behavior is defined by constraints (7.1), (7.2), and (7.3). Constraints (7.1) and (7.2) force the value of xi to 1 if there is traffic going in or out of node i, which means that it is used to route flows. Inversely, constraint (7.3) sets the value to 0 if there is no traffic passing through the node. Then, if variable xi is equal to 1, the solution selects the idle mode as its passive mode. Otherwise, the node remains in sleep mode at all times.Figure4(a) shows the overall energy consumption when increasing the number of flows routed over the network. We see that a significant part of energy can be saved by routing the set of flows according to our optimal solution compared to this using a shortest path algorithm. However, this solution is not satisfactory enough because it uses the energy parameters which are data from the physical layer. Figure 4(b) gives an indication that could help us avoid having to rely on cross-layer information. It indicates the number of nodes that remain unused after all flows have been routed. These nodes are the ones that have been turned off to save energy. We can see that the difference in terms of the number of unused nodes is as important as the difference we have in terms of energy consumption. This leads to assume that this may be an effective criterion for designing a routing algorithm that can minimize energy consumption based solely on information available at the routing layer of the communication stack. We have called this routing approach flow aggregation in a preliminary study [5]. In the next subsection, we show that flow aggregation routing is equivalent to our minimized overall energy consumption solution.Figure 4
Comparison of a classical shortest path routing and our optimal solution. (a) Overall energy consumption. (b) Number of unused nodes.
(a)
(b)


### 4.2. Optimal Flow Aggregation

In our preliminary study [5], we proposed RA (routing with aggregation), an optimal routing algorithm implemented using ILP. This solution aims at routing a set of flows while minimizing the number of forwarding nodes. The key idea is to find the smallest set of nodes capable of routing as many flows as possible while respecting their required quality of service in terms of bit rate, without overloading cliques, so that the remaining nodes can be turned off to save energy. This is what we called flow aggregation, routing flows together over common paths so that we can maximize the number of nodes that can be turned off. We remind the ILP formulation we proposed in Figure 5.Figure 5
ILP formulation to minimize the number of used nodes when routing a set of flows.In this formulation, the objective function is changed so that the program now minimizes the number of nodes used. Again, we can see the unnumbered constraints that model the routing algorithm. Constraints (9.∗) are the constraints (7.∗) of the program presented in the previous subsection. Finally, constraint (10) comes from the formulation of the Traveling Salesman Problem (TSP) [26]. This constraint solves a problem caused by the new objective function that could allow flows to be routed on loops disconnected from their main path.In Figure6, we compare our minimal energy consumption routing (MinEnergy) introduced in this paper with our previous optimal aggregation routing (RA) solution. We illustrate the relation between the global energy consumption of the network and the number of nodes that can be turned off. More precisely, we show that minimizing energy consumption (MinEnergy) and maximizing the number of unused nodes are equivalent problems. Indeed, we can see in Figure 6(a) that the two plots overlap which means that aggregating flows with RA allows to reach the optimal energy consumption that we have with MinEnergy. In the same way, Figure 6(b) shows that minimizing the overall energy consumption with MinEnergy allows to reach the minimal number of active nodes to route a set of flows.Figure 6
Equivalence between energy consumption and number of nodes used. (a) Overall energy consumption. (b) Number of unused nodes.
(a)
(b)Thus, by using flow aggregation, we can minimize the global energy consumption of a multihop wireless network while respecting the QoS, without requiring cross-layer information (energy-related information). The only information we need is the set of flows, which can be determined at the routing layer, and the links’ capacity which is a constant that can be known. However, as optimal as ILP can be, the complexity of the algorithms used to solve this problem makes our solution inapplicable. Nevertheless, it gives an optimal bound to which we can refer when evaluating the innovative solutions that will be described in the next section.


## 4.1. Minimizing the Energy Consumption

In this paper, we aim at minimizing the overall energy consumption of the network by allowing unused nodes to be turned off (or put into sleep mode) instead of remaining in idle mode. We model this behavior by a set of linear constraints that we integrate into the previous ILP. Figure3 shows the ILP formulation that optimally routes a set of flows over the network while minimizing the overall energy consumption.Figure 3
ILP formulation for minimal energy consumption routing.In this formulation, we have modified the objective function so that the program is now minimizing the overall energy consumption of the network. The first unnumbered constraints are the same as those seen above and are mandatory to implement the routing algorithm regardless of the objective function. Constraint (1) calculates the total energy consumption of any nodei, that is, Ei, as the sum of energy consumed when it is in transmission state EiT, in reception state EiR, and in passive state EiP (i.e., neither transmitting or receiving), respectively. Constraints (2), (3), (4), and (5) are about the energy consumption of a node when it is in the four different states. These values are calculated according to the energy consumption related to each state and the time spent in it. We consider that a node always transmits at the highest available bit rate in order to maximize the time spent in the passive mode, allowing to save more energy [20]. Thus, we can deduct from the utilization rates of the links the proportion of time a node spends in transmission and reception modes. The reverse proportion is then used as the time spent by the node in a passive (idle or sleep) mode. Finally, to save energy, constraints (6.1) and (6.2) are used to determine if a node is used and set its passive mode accordingly. We consider that any node i is useful to the network if it is used as a relay to route flows. This behavior is defined by constraints (7.1), (7.2), and (7.3). Constraints (7.1) and (7.2) force the value of xi to 1 if there is traffic going in or out of node i, which means that it is used to route flows. Inversely, constraint (7.3) sets the value to 0 if there is no traffic passing through the node. Then, if variable xi is equal to 1, the solution selects the idle mode as its passive mode. Otherwise, the node remains in sleep mode at all times.Figure4(a) shows the overall energy consumption when increasing the number of flows routed over the network. We see that a significant part of energy can be saved by routing the set of flows according to our optimal solution compared to this using a shortest path algorithm. However, this solution is not satisfactory enough because it uses the energy parameters which are data from the physical layer. Figure 4(b) gives an indication that could help us avoid having to rely on cross-layer information. It indicates the number of nodes that remain unused after all flows have been routed. These nodes are the ones that have been turned off to save energy. We can see that the difference in terms of the number of unused nodes is as important as the difference we have in terms of energy consumption. This leads to assume that this may be an effective criterion for designing a routing algorithm that can minimize energy consumption based solely on information available at the routing layer of the communication stack. We have called this routing approach flow aggregation in a preliminary study [5]. In the next subsection, we show that flow aggregation routing is equivalent to our minimized overall energy consumption solution.Figure 4
Comparison of a classical shortest path routing and our optimal solution. (a) Overall energy consumption. (b) Number of unused nodes.
(a)
(b)


## 4.2. Optimal Flow Aggregation

In our preliminary study [5], we proposed RA (routing with aggregation), an optimal routing algorithm implemented using ILP. This solution aims at routing a set of flows while minimizing the number of forwarding nodes. The key idea is to find the smallest set of nodes capable of routing as many flows as possible while respecting their required quality of service in terms of bit rate, without overloading cliques, so that the remaining nodes can be turned off to save energy. This is what we called flow aggregation, routing flows together over common paths so that we can maximize the number of nodes that can be turned off. We remind the ILP formulation we proposed in Figure 5.Figure 5
ILP formulation to minimize the number of used nodes when routing a set of flows.In this formulation, the objective function is changed so that the program now minimizes the number of nodes used. Again, we can see the unnumbered constraints that model the routing algorithm. Constraints (9.∗) are the constraints (7.∗) of the program presented in the previous subsection. Finally, constraint (10) comes from the formulation of the Traveling Salesman Problem (TSP) [26]. This constraint solves a problem caused by the new objective function that could allow flows to be routed on loops disconnected from their main path.In Figure6, we compare our minimal energy consumption routing (MinEnergy) introduced in this paper with our previous optimal aggregation routing (RA) solution. We illustrate the relation between the global energy consumption of the network and the number of nodes that can be turned off. More precisely, we show that minimizing energy consumption (MinEnergy) and maximizing the number of unused nodes are equivalent problems. Indeed, we can see in Figure 6(a) that the two plots overlap which means that aggregating flows with RA allows to reach the optimal energy consumption that we have with MinEnergy. In the same way, Figure 6(b) shows that minimizing the overall energy consumption with MinEnergy allows to reach the minimal number of active nodes to route a set of flows.Figure 6
Equivalence between energy consumption and number of nodes used. (a) Overall energy consumption. (b) Number of unused nodes.
(a)
(b)Thus, by using flow aggregation, we can minimize the global energy consumption of a multihop wireless network while respecting the QoS, without requiring cross-layer information (energy-related information). The only information we need is the set of flows, which can be determined at the routing layer, and the links’ capacity which is a constant that can be known. However, as optimal as ILP can be, the complexity of the algorithms used to solve this problem makes our solution inapplicable. Nevertheless, it gives an optimal bound to which we can refer when evaluating the innovative solutions that will be described in the next section.


## 5. Heuristic for Flow Aggregation

Solving the flow aggregation problem using integer linear programming has two issues. Firstly, the complexity is very high. Secondly, it requires that the routing problem be solved with the same method. Thus, it becomes difficult to distribute this solution and only routes between the sources and their respective destinations can be found. If the set of flows changes, all routes have to be recalculated through integer linear programming. To deal with this, we have proposed the Flow Aggregation MEtric (FAME) [3].


### 5.1. Flow Aggregation MEtric

FAME is a routing metric that can be integrated into a classic shortest path routing algorithm. Its purpose consists in routing flows according to a set of attractive nodes. These nodes can be defined statically when the network is deployed or dynamically when network conditions change. We call them nodes of interest. Let NI be the set of such nodes.As we are using a shortest path routing algorithm, our goal is to give a weight small enough to the nodes of interest so that they naturally attract flows. In this way, the path they are in is shorter and the routing algorithm can route flows over them and their close neighborhood, leading to aggregation. NI can be determined in several ways using, for example, a connected dominating set or a Steiner tree. However, our results in [3] have showed that the use of sources and destinations is the best choice. This can be explained by the fact that these nodes have to be turned on anyway to send and receive data. From this point of view, it is more interesting to reuse them as relays for other flows.We consider two cases to calculate the weight of a node:(i)
If the node does not belong to NI, its weight is a function of the distance with its nearest node of interest and the number of such nodes at this distance (in terms of hops)(ii)
The weights of the nodes in NI are set to the minimal value that the other nodes can theoretically haveHence, we determine the weight of any nodei as follows:(1)FAMEi=1V−1,ifi∈NI,distminNEIi,distmin∩NI,otherwise,where NEIv,d represents the neighborhood of node v at distance distmin, distmin is the distance between node i and its closest node of interest, and V is the number of nodes in the network. This metric allows to route flows over NI, leading to flow aggregation.Figure7 illustrates the performance of FAME in terms of aggregation and compares it to these of our optimal solution RA and a traditional shortest path routing. Here we can see that, starting very close to our optimal solution, FAME does not diverge from RA as much as the shortest path routing. In [3], we depicted an experiment where we inserted up to 40 flows and show that when we increase the number of flows inserted in the network, FAME approaches RA again to eventually reach the same performances.Figure 7
Number of unused nodes.Figure8 shows the impact of flow aggregation on network load. It can be seen that flow aggregation increases the load of the network, which has an impact on its capacity. It represents the cost of energy savings. Figure 8(a) illustrates the average load of the network. We can see that when using RA, the load of the network increases the most. This can be explained by the way flows are routed by giving priority to common nodes. Indeed, such an approach leads to an increase in the average length of the flows, which implies a greater number of transmissions. Figure 8(b) shows the utilization rate of the most loaded area of the network, dense areas being mainly those in which flows are aggregated. As expected, the aggregation of flows over a small number of nodes significantly increases the load of the area covered by these nodes.Figure 8
Load of the network through the cliques’ utilization rates. (a) Average utilization rate of cliques. (b) Utilization rate of the most used clique.
(a)
(b)Once again, we can notice from these figures that FAME approximates very well our optimal aggregation solution. However, to avoid that our results are biased by the implementation of routing algorithms, we have introduced our metric into the shortest path ILP formulation. This means we were able to benefit from the centralized interference model defined by the cliques. Thus, we need to go a step further in order to consider a fully distributed algorithm.


### 5.2. Adaptive Flow Aggregation MEtric

Our metric FAME allows shortest path routing algorithms to aggregate flows close to an optimal level. Nevertheless, if this is done without consideration of interference, the network may quickly become overloaded. To overcome this difficulty, we propose the Adaptive Flow Aggregation MEtric (A-FAME). This takes into account the network load. More precisely, when it is low, the metric routes flow almost optimally, in the same way as FAME. When it is high, the weights of nodes are calculated so that flows are routed according to the shortest path, by releasing the attraction of nodes of interest. To achieve this, we first need to simplify our interference model.We now consider interference between nodes instead of links. This allows us to move from the determination of cliques, which is complex, to neighborhoods. Based on the same principle of the previous model, we calculate the transmission rate of nodes (out rate of nodes divided by the capacity of the wireless transmission medium) to evaluate the utilization rate of a neighborhood. As with cliques, it can be interpreted as the load of a neighborhood and is calculated as the sum of the transmission rates of the nodes that compose it:(2)∀v∈V,NLv=∑i∈NEIv,2∑i,j∈Edi,jCi,j,where NLv is the load of the neighborhood of node v. As we are considering a 2-hop interference model, this value is calculated using the 2-hop neighborhood of the node. The loads of neighborhood are used the same way as cliques. They model local loads of the network. When their value is higher than 1, it means that this area of the network is overloaded. To use it in our A-FAME, we set a threshold. If the load of the neighborhood of a node is below, its weight is the same as this given by FAME. Otherwise, its weight will be adjusted around the average FAME weight of all nodes in the network, as follows:(3)A−FAMEv=αv⋅FAMEv+1−αv1V∑j∈VFAMEj,where αv is the aggregation force of node v, that is the ability to attract flows. When it is equal to 1 (i.e., 100% aggregation), the weight of the node is given by FAME. When it is 0, this weight is the average value of the FAME weights of all nodes. In this way, the node stays neutral by not attracting or rejecting flows. If all nodes have such an average weight, the routing algorithm will behave as a shortest path in terms of number of hops.To implement A-FAME, two parameters need to be set. The first one is the reduction thresholdRt. It is used to evaluate the load of the node’s neighborhood. If the load is above Rt, we consider that the neighborhood of the node is overloaded and thus activate the A-FAME. Otherwise, we use the FAME one. The second parameter is the starting value of the aggregation force Ba. It represents the maximum aggregation force that a node can have when the A-FAME is activated. Using these two parameters and the neighborhood load NL of any node v, the aggregation force of a node can be calculated as follows:(4)αv=1ifNLv≤Sr,max0,Ba−NLv−Srotherwise,∀v∈V.The aggregation force of a node, when its neighborhood load is greater than the reduction threshold, is calculated by subtracting the excess from theBa threshold. Thus, the more the load in the neighborhood of a node exceeds the threshold, the more its aggregation force is reduced.Finding the optimal value for these parameters is still an open question and will remain out of the scope of this paper. However, interested readers may investigate multiobjective optimization [27] in the area of operational research to address this question. Another approach we identified to find the optimal values for these parameters involves machine learning. Indeed, interesting works have been conducted for wireless networks using reinforcement learning [28] and deep learning [29].In this paper, we expect that if the reduction threshold is high, we may not be able to detect network overload, resulting in underutilization of the A-FAME. Indeed, the higher the threshold is, the less the impact of the excess is on the aggregation force. On the other hand, a low threshold can activate the A-FAME mechanism more often with a potentially greater excess, resulting in a lower aggregation force. With regard to the initial value of the aggregation force, a high value can limit the range of the force of a node, which can reduce the adaptability of the metric. However, a low value may reduce excessively the aggregation, resulting in an oscillation problem where each metric (FAME and A-FAME) is used in turn.In Figures9 and 10, we compare our solution to the following references:(i)
FAME (without cliques), a specific application of FAME in a routing algorithm that does not take interference into account. This reference is added only as an indication to show that FAME is not an acceptable solution to aggregate flows if the routing algorithm does not consider interference. Indeed, although Figure 9 shows that this solution is able to turn off more nodes than FAME (applied with an interference aware routing algorithm), Figure 10(b) indicates that it tends to overload the network as flows are inserted into the network.(ii)
FAME, the reference we want to approach. The purpose of this is to emphasize the effectiveness of A-FAME when interference is taken into account.(iii)
Shortest path, which represents our lower bound reference and our worst-case scenario in terms of aggregation.(iv)
A-FAME (x-y), our solution applied in a routing algorithm that did not take into account interference, where x and y are the parameters of the metric.Figure 9
Number of unused nodes with various parameters for the A-FAME.Figure 10
Impact of A-FAME parameters on the network load. (a) Average utilization rate of cliques (b) Utilization rate of the most used clique.
(a)
(b)Figure9 indicates that when A-FAME is used with two high parameters (Bs=80% and Sr=80%), its performance in terms of aggregation is very close to that of FAME. This can be explained by the fact that these high parameters avoid significantly reducing aggregation. Then, when the base value is reduced for the aggregation force (Ba), the performance of A-FAME decreases. Finally, lowering the reduction threshold (Th) also leads to limit aggregation. Indeed, with such a low threshold, the A-FAME is triggered more often and the amplitude of the excess increases.Figures10(a) and 10(b) show the impact of the parameters of A-FAME on the network load. It behaves in the same way as in the previous figure. Thus, as the parameters improve aggregation performance, the network load increases to approach that of FAME. Figure 10(b) also illustrates that A-FAME follows FAME when there are not much flows in the network. As soon as more flows are added, increasing the network load, the two solutions diverge. This difference appears at different levels, which depend mainly on the reduction threshold.


## 5.1. Flow Aggregation MEtric

FAME is a routing metric that can be integrated into a classic shortest path routing algorithm. Its purpose consists in routing flows according to a set of attractive nodes. These nodes can be defined statically when the network is deployed or dynamically when network conditions change. We call them nodes of interest. Let NI be the set of such nodes.As we are using a shortest path routing algorithm, our goal is to give a weight small enough to the nodes of interest so that they naturally attract flows. In this way, the path they are in is shorter and the routing algorithm can route flows over them and their close neighborhood, leading to aggregation. NI can be determined in several ways using, for example, a connected dominating set or a Steiner tree. However, our results in [3] have showed that the use of sources and destinations is the best choice. This can be explained by the fact that these nodes have to be turned on anyway to send and receive data. From this point of view, it is more interesting to reuse them as relays for other flows.We consider two cases to calculate the weight of a node:(i)
If the node does not belong to NI, its weight is a function of the distance with its nearest node of interest and the number of such nodes at this distance (in terms of hops)(ii)
The weights of the nodes in NI are set to the minimal value that the other nodes can theoretically haveHence, we determine the weight of any nodei as follows:(1)FAMEi=1V−1,ifi∈NI,distminNEIi,distmin∩NI,otherwise,where NEIv,d represents the neighborhood of node v at distance distmin, distmin is the distance between node i and its closest node of interest, and V is the number of nodes in the network. This metric allows to route flows over NI, leading to flow aggregation.Figure7 illustrates the performance of FAME in terms of aggregation and compares it to these of our optimal solution RA and a traditional shortest path routing. Here we can see that, starting very close to our optimal solution, FAME does not diverge from RA as much as the shortest path routing. In [3], we depicted an experiment where we inserted up to 40 flows and show that when we increase the number of flows inserted in the network, FAME approaches RA again to eventually reach the same performances.Figure 7
Number of unused nodes.Figure8 shows the impact of flow aggregation on network load. It can be seen that flow aggregation increases the load of the network, which has an impact on its capacity. It represents the cost of energy savings. Figure 8(a) illustrates the average load of the network. We can see that when using RA, the load of the network increases the most. This can be explained by the way flows are routed by giving priority to common nodes. Indeed, such an approach leads to an increase in the average length of the flows, which implies a greater number of transmissions. Figure 8(b) shows the utilization rate of the most loaded area of the network, dense areas being mainly those in which flows are aggregated. As expected, the aggregation of flows over a small number of nodes significantly increases the load of the area covered by these nodes.Figure 8
Load of the network through the cliques’ utilization rates. (a) Average utilization rate of cliques. (b) Utilization rate of the most used clique.
(a)
(b)Once again, we can notice from these figures that FAME approximates very well our optimal aggregation solution. However, to avoid that our results are biased by the implementation of routing algorithms, we have introduced our metric into the shortest path ILP formulation. This means we were able to benefit from the centralized interference model defined by the cliques. Thus, we need to go a step further in order to consider a fully distributed algorithm.


## 5.2. Adaptive Flow Aggregation MEtric

Our metric FAME allows shortest path routing algorithms to aggregate flows close to an optimal level. Nevertheless, if this is done without consideration of interference, the network may quickly become overloaded. To overcome this difficulty, we propose the Adaptive Flow Aggregation MEtric (A-FAME). This takes into account the network load. More precisely, when it is low, the metric routes flow almost optimally, in the same way as FAME. When it is high, the weights of nodes are calculated so that flows are routed according to the shortest path, by releasing the attraction of nodes of interest. To achieve this, we first need to simplify our interference model.We now consider interference between nodes instead of links. This allows us to move from the determination of cliques, which is complex, to neighborhoods. Based on the same principle of the previous model, we calculate the transmission rate of nodes (out rate of nodes divided by the capacity of the wireless transmission medium) to evaluate the utilization rate of a neighborhood. As with cliques, it can be interpreted as the load of a neighborhood and is calculated as the sum of the transmission rates of the nodes that compose it:(2)∀v∈V,NLv=∑i∈NEIv,2∑i,j∈Edi,jCi,j,where NLv is the load of the neighborhood of node v. As we are considering a 2-hop interference model, this value is calculated using the 2-hop neighborhood of the node. The loads of neighborhood are used the same way as cliques. They model local loads of the network. When their value is higher than 1, it means that this area of the network is overloaded. To use it in our A-FAME, we set a threshold. If the load of the neighborhood of a node is below, its weight is the same as this given by FAME. Otherwise, its weight will be adjusted around the average FAME weight of all nodes in the network, as follows:(3)A−FAMEv=αv⋅FAMEv+1−αv1V∑j∈VFAMEj,where αv is the aggregation force of node v, that is the ability to attract flows. When it is equal to 1 (i.e., 100% aggregation), the weight of the node is given by FAME. When it is 0, this weight is the average value of the FAME weights of all nodes. In this way, the node stays neutral by not attracting or rejecting flows. If all nodes have such an average weight, the routing algorithm will behave as a shortest path in terms of number of hops.To implement A-FAME, two parameters need to be set. The first one is the reduction thresholdRt. It is used to evaluate the load of the node’s neighborhood. If the load is above Rt, we consider that the neighborhood of the node is overloaded and thus activate the A-FAME. Otherwise, we use the FAME one. The second parameter is the starting value of the aggregation force Ba. It represents the maximum aggregation force that a node can have when the A-FAME is activated. Using these two parameters and the neighborhood load NL of any node v, the aggregation force of a node can be calculated as follows:(4)αv=1ifNLv≤Sr,max0,Ba−NLv−Srotherwise,∀v∈V.The aggregation force of a node, when its neighborhood load is greater than the reduction threshold, is calculated by subtracting the excess from theBa threshold. Thus, the more the load in the neighborhood of a node exceeds the threshold, the more its aggregation force is reduced.Finding the optimal value for these parameters is still an open question and will remain out of the scope of this paper. However, interested readers may investigate multiobjective optimization [27] in the area of operational research to address this question. Another approach we identified to find the optimal values for these parameters involves machine learning. Indeed, interesting works have been conducted for wireless networks using reinforcement learning [28] and deep learning [29].In this paper, we expect that if the reduction threshold is high, we may not be able to detect network overload, resulting in underutilization of the A-FAME. Indeed, the higher the threshold is, the less the impact of the excess is on the aggregation force. On the other hand, a low threshold can activate the A-FAME mechanism more often with a potentially greater excess, resulting in a lower aggregation force. With regard to the initial value of the aggregation force, a high value can limit the range of the force of a node, which can reduce the adaptability of the metric. However, a low value may reduce excessively the aggregation, resulting in an oscillation problem where each metric (FAME and A-FAME) is used in turn.In Figures9 and 10, we compare our solution to the following references:(i)
FAME (without cliques), a specific application of FAME in a routing algorithm that does not take interference into account. This reference is added only as an indication to show that FAME is not an acceptable solution to aggregate flows if the routing algorithm does not consider interference. Indeed, although Figure 9 shows that this solution is able to turn off more nodes than FAME (applied with an interference aware routing algorithm), Figure 10(b) indicates that it tends to overload the network as flows are inserted into the network.(ii)
FAME, the reference we want to approach. The purpose of this is to emphasize the effectiveness of A-FAME when interference is taken into account.(iii)
Shortest path, which represents our lower bound reference and our worst-case scenario in terms of aggregation.(iv)
A-FAME (x-y), our solution applied in a routing algorithm that did not take into account interference, where x and y are the parameters of the metric.Figure 9
Number of unused nodes with various parameters for the A-FAME.Figure 10
Impact of A-FAME parameters on the network load. (a) Average utilization rate of cliques (b) Utilization rate of the most used clique.
(a)
(b)Figure9 indicates that when A-FAME is used with two high parameters (Bs=80% and Sr=80%), its performance in terms of aggregation is very close to that of FAME. This can be explained by the fact that these high parameters avoid significantly reducing aggregation. Then, when the base value is reduced for the aggregation force (Ba), the performance of A-FAME decreases. Finally, lowering the reduction threshold (Th) also leads to limit aggregation. Indeed, with such a low threshold, the A-FAME is triggered more often and the amplitude of the excess increases.Figures10(a) and 10(b) show the impact of the parameters of A-FAME on the network load. It behaves in the same way as in the previous figure. Thus, as the parameters improve aggregation performance, the network load increases to approach that of FAME. Figure 10(b) also illustrates that A-FAME follows FAME when there are not much flows in the network. As soon as more flows are added, increasing the network load, the two solutions diverge. This difference appears at different levels, which depend mainly on the reduction threshold.


## 6. Conclusion and Perspectives

Our work focused on aggregating flows in multihop wireless networks to minimize overall energy consumption, while maintaining the quality of service offered in terms of throughput. In this paper, we have shown that maximizing energy savings and maximizing the number of nodes that can be turned off are equivalent problems. Then, we have improved our previous solution [3, 5], where our Flow Aggregation MEtric (FAME) tends to overload some parts of the network. To do so, an adaptive metric (A-FAME) has been proposed, taking interference into account in order to adjust the aggregation force of the nodes in loaded areas. The performance of our solution has been evaluated by simulation. The results have illustrated the interest and effectiveness of our approach.Future work should focus on finding an effective way to implement flow aggregation in current applications. To do this, we need to disseminate two pieces of information: the network topology which is necessary to determine the routes and the nature of nodes of interest. Our first studies on the adaptation of the OLSR protocol [10] seem very promising. Another interesting research topic would be to investigate whether the results of this work can now be used to improve duty-cycle solutions. More precisely, a fundamental question is how long a node can be turned off without hindering network responsiveness. Our next work will therefore focus on the extinction time of a node according to the dynamicity of the network, based on robust programming.



---

*Source: 7059401-2019-10-10.xml*