When physical communication network infrastructures fail, infrastructure-less communication networks such as mobile ad-hoc networks (MANET), can provide an alternative. This, however, requires MANETs to be adaptable to dynamic contexts characterized by the changing density and mobility of devices and availability of energy sources. To address this challenge, this paper proposes a decentralized context-adaptive topology control protocol. The protocol consists of three algorithms and uses preferential attachment based on the energy availability of devices to form a loop-free scale-free adaptive topology for an ad-hoc communication network. The proposed protocol has a number of advantages. First, it is adaptive to the environment, hence applicable in scenarios where the number of participating mobile devices and their availability of energy resources is always changing. Second, it is energy-efficient through changes in the topology. This means it can be flexibly combined with different routing protocols. Third, the protocol requires no changes on the hardware level. This means it can be implemented on all current phones, without any recalls or investments in hardware changes. The evaluation of the protocol in a simulated environment confirms the feasibility of creating and maintaining a self-adaptive ad-hoc communication network, consisting of multitudes of mobile devices for reliable communication in a dynamic context.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abkürzungen
MANET
Mobile ad-hoc networks
P2P
peer-to-peer
Introduction
Connectivity is essential to today’s society, and relies heavily on the availability and reliability of physical network infrastructures (Sterbenz et al. 2010). There are, however, periods of time when physical network infrastructures fail, for example due to cascading failures, extreme weather events, humanitarian crises or intentional shutdown of communication infrastructures (Howard et al. 2011; Pidd 2012). In these periods mobile ad-hoc networks (MANETs), i.e., infrastructure-less communication networks, can provide an alternative (Rabbi and Arefin 2006; Gunasekaran and Harmantzis 2007; George et al. 2010; Lu et al. 2017). The performance of MANETs depends on its dynamic context characterized by the mobility of devices, changing density of devices, and depleting battery charge of nodes (Nishiyama et al. 2012; Maan and Mazhar 2011; Aloi et al. 2014; Mitra and Poellabauer 2012; Roy 2011). To ensure efficient MANET deployment, adaptive use of available energy resources is required within such dynamic contexts (Vanjale et al. 2018; Conti and Giordano 2014).
To address this challenge this paper proposes a decentralized adaptive topology control protocol consisting of three algorithms. The algorithms use context information on the available energy of nodes as a basis for preferential attachment. This leads to the formation of a loop-free scale-free adaptive topology for an ad-hoc communication network. The novelty of the proposed protocol is that it allows for energy efficiency without any adaption on the hardware level as the adaptations are made at the level of topology. There is no manipulation on the physical layer or the link layer to mitigate limited battery charge of participating nodes (Miliotis et al. 2014; Mekikis et al. 2014).
Anzeige
The protocol’s performance is evaluated in terms of reliability, scalability and longevity of the network. Reliability is defined as the assurance that a message that is sent from one device to another will be delivered. Scalability is defined as the ability of the network to scale up or down with respect to the number of available devices without affecting its primary goal of reliable communication. Finally, longevity is defined as the lifetime of a MANET and depends upon efficient energy utilization.
The rest of the article is structured as follows. Section Background: forms of energy consumption in ad-hoc networks discusses energy consumption in mobile ad-hoc networks, followed by a review of different approaches proposed in the literature for energy efficiency through topology creation and maintenance. The knowledge gap identified is that of context-adaptive topologies. In the “Methodology: protocol design and pseudo-code of algorithms” section, three algorithms that constitute the decentralized context-aware adaptive topology creation protocol are presented. In Section Protocol evaluation and performance analysis, modeling and simulation used to evaluate the performance of the proposed protocol are presented. This is followed by the results section. The next section presents a comparative analysis with existing work. Finally the last section, concludes the article and proposes future work.
Background: forms of energy consumption in ad-hoc networks
Current approaches on energy-efficiency mainly focus on reducing energy associated with the routing procedure. A generic approach is to optimize the route by decreasing the number of hops to decrease relaying cost in order to increase performance and decrease delay in message delivery. Examples of protocols that follow this approach are Dynamic source routing (DSR), Ad-hoc on demand distance vector routing (AODV), Dynamic distance-vector routing (DSDV), Optimum link state routing (OLSR), Zone routing protocol (ZRP), and Location aware routing (LAR) (Clausen and Jacquet 2003; Johnson and Maltz 1996; Perkins and Bhagwat 1994; Ko and Vaidya 2000).
These approaches either conserve individual node energy promoting opportunistic behaviour (Toh 2001; Singh and Raghavendra 1998; Rajaram and Sugesh 2011), or they focus on extending the entire lifetime of a network by minimizing total cost of transmitting a message from source to destination by choosing only high energy nodes depleting specific nodes faster (Singh et al. 1998; PalChaudhuri and Johnson 2002). In short, some approaches have been shown to work relatively well in stable environments of densely populated areas whereas some approaches such as Delay tolerant networks (DTNs) work better in sparsely populated areas (Zhao et al. 2004).
Anzeige
Energy efficiency however, requires not only efficient routing but also an effective and efficient topology. A topology determines the layout of connections between devices along which messages can be exchanged. A route is defined by the nodes/hops1 it follows and is very context-dependent. To maintain connectivity, a topology should ideally reflect this dynamic context to avoid high end-to-end delay and high energy consumption (Ishibashi and Boutaba 2005; Burkhart et al. 2004). To control the creation and maintenance of a topology various mechanisms are deployed.
Existing topology control mechanisms
Topology control mechanisms in the literature distinguish functions either by manipulating the transmission range (power control) or by allotting roles to nodes (topology management). Both have the capability of providing energy efficiency but are different in their approaches as explained below.
Topology control by Power Control: A power control approach creates and maintains a topology by manipulating the transmission range (Narayanaswamy et al. 2002; Santi 2005). This option is considered beneficial in sensor networks where transmission ranges can be varied with a predetermined purpose (Deniz et al. 2016). However in most communication devices, the transmission range is fixed. Hence this approach is impractical for mobile phones. This paper focuses on mobile phones hence approaches for energy efficiency in wireless sensor networks are out of scope.
Topology control by Topology Management: An alternative approach is to assign roles to nodes in a topology or clustering (Younis and Fahmy 2004). A topology is either flat, hierarchical or a hybrid of both. In a flat topology, all nodes have the same role in communication. In contrast, in a hierarchical topology leader roles are assigned based on, for example, a node’s resources or number of connections to other nodes (node degree). Nodes with a high battery charge or a high number of connections are declared leaders. All other nodes communicate with each other via these leader nodes. This reduces transmission and routing energy cost by removing one-to-one links and building new links via these leader nodes.
There are two drawbacks to this type of approach during a power outage. First, it is difficult to assign leader roles based on node resources, as these cannot be known in advance and change over time as the battery charge is used. Second, it is difficult to predict the density of participating devices in a given vicinity at any point in time (Bao and Garcia-Luna-Aceves 2010).
To summarize, current approaches to the design of infrastructure-less communication networks are based on predetermined assumptions that (by definition) lack consideration of energy constraints of individual nodes or changing context. The context as defined by mobility and density of mobile phones, varies by a geographic area as does availability of charging facilities. Designing an adaptive distributed topology is a necessity to ensure reliability of message delivery and maximize the probability of finding new high energy nodes, especially given that nodes only have a local view. Thus, an energy-efficient decentralized approach for self-organization is needed with context-adaptive topology.
Methodology: protocol design and pseudo-code of algorithms
This section describes the design of a decentralized adaptive topology control protocol. The protocol consists of three separate algorithms that work together to create and maintain a topology that allows message exchange over an ad-hoc communication network, while maintaining reliability, scalability and longevity.
The algorithms use spatio-temporal resource information of individual nodes and the nodes in their transmission range to determine their local context information. This information is used by each node for preferential attachment to form a loop-free scale-free adaptive topology for an ad-hoc communication network. Algorithm 1 creates the topology for a mobile ad-hoc network, followed by algorithm 2 that allows nodes to communicate and finally algorithm 3 that maintains the topology by reconfiguring to ensure reliability, longevity and scalability.
An ad-hoc network is conceptualized as an undirected graph with devices as nodes and connections as edges. Each node maintains its own context information tuple t as depicted in Table 1, and it consists of a unique identifier (\(U_{id}\)), a unique sub-tree identifier (\(S_{id}\)), the amount of battery charge left (e) and the view \(l_{v}\).
Table 1
The information stored in t is exchanged with other nodes within a node’s transmission range r
t
Type
\(U_{id }\)
Unique Identification number of the node
\(S_{id}\)
The unique network number, where this node is connected
When disconnected set to its own unique identification number
e
Battery charge or residual energy of the node
\(l_{v}\)
View: List of potential nodes for connection and their residual energy in the transmission range,initially empty
Each node also maintains its local view of its neighbours (\(l_{v}\)) within its transmission range (r). This view contains spatio-temporal resource information and is updated as the node changes location. Specifically, the view is a list of (i) a unique identifier of potential neighbours to which it can connect in its transmission range and (ii) their energy or battery life left at that point in time. The view is guaranteed to change and is updated continuously as neighbouring nodes move in and out of transmission range.
To form a connection, a node chooses to connect with only one other node from its local view (\(l_{v}\)): the node with the highest battery charge left. As each node follows this procedure independently, nodes with the highest residual energy will ‘automatically’ take a more critical central position in the network.
To prevent loops in the network (and thus redundant connections that need to be maintained and cost energy) each node compares the sub-tree ID in its individual view with that of the to-be-connected node before connecting to another node. If their sub-tree IDs do not match indicating they belong to separate networks they connect, otherwise the node tries to connect to the node with the second highest energy within its transmission range, etc.
Once this condition is fulfilled, the nodes exchange the context information—an information tuple t given in Table 1. Control information is only exchanged between nodes that wish to connect. The procedure of getting connected and preventing loops is explained below in more detail.
Creation: the connection procedure
The process starts with each node maintaining its own information tuple t. Initially a new node is not part of a network. In this case the sub-tree identifier \(S_{id}\) is set equal to its own unique identifier \(U_{id}\). As nodes turn on their Bluetooth interface, they start discovering neighbouring nodes in their transmission range r. They receive information from neighbours in their transmission range on which they form their \(l_{v}\).
×
From \(l_{v}\), each node then considers the residual energy of all of the potential nodes in its view to which it can potentially connect and sorts them in order of neighbours with the highest residual battery charge first. The neighbour with the highest residual battery charge left is selected and the sub-tree IDs of both nodes are compared. This ensures that the new connection is part of a different sub-tree (representing a different, as of yet not connected, network). If they have the same \(S_{id}\) this indicates that the nodes are connected through different nodes in the same network that might not be visible to the node, and if they connect they create a loop. Hence they only connect if the \(S_{id}\) are different to ensure a loop-free network. The node that initiates the connection changes its sub-tree identifier to match the network to which it wishes to connect. This procedure maintains uniformity among the network and additionally the uniqueness of each network. The pseudo-code for this procedure is shown below in Algorithm 1. Figure 1 shows the emergence of a connected network following Algorithm 1. The next section describes message delivery.
Fig. 1
An example of an emerged network of 500 nodes spread over an area of 25x25 with a transmission range of 5. The picture shows the visualization of the network in the simulation environment NetLogo (see Protocol evaluation and performance analysis)
×
Communication: the message exchange procedure
As described above in the introduction, this paper focuses on the design and development of a self-adaptive topology and not on the design of a new routing protocol. Hence any routing protocol that works on the proposed topology to return a route enquiry based on shortest route between sender and receiver can be used. The algorithm described in this section works after Algorithm 1 has created a network and a node decides to communicate. Based on route enquiry, the node decides when to trigger a reconfiguration. It triggers reconfiguration of the topology (1) to maintain connectivity for reliably sending a message when no route is present and (2) to ensure that the loss of energy for relaying messages is distributed among various high energy nodes. Algorithm 2 below determines the need for reconfiguration. Initially a Sender node sends a route inquiry using a routing protocol. This inquiry is to confirm if a route exists through which a message can be sent. Two results are possible. First, the relay nodes confirm that they have energy left to relay the message and that they are still part of the network. In this case the Sender node forwards the actual message to the next hop or relay in the network. Second, the Sender node receives a response that no route is possible.
×
The absence of a route can happen if the network has become temporarily fragmented. Network fragmentation can be due to relay nodes moving out of transmission range or one or more relay nodes leaving the network due to exhausted battery charge. In this case the Sender node stores the message as pending and triggers the reconfiguration algorithm. It confirms if it is part of a network. If the response is true, it triggers a reconfiguration only for the local neighbours connected to it. In case the node is completely disconnected, it reconfigures itself to find a new network or neighbouring nodes to connect with, in its transmission range. Reconfiguration allows nodes to adapt to the dynamic environment and change their connections thus providing new routing options. This reconfiguration Algorithm 3 is explained in the next section and addresses the challenge of creating a dynamic self-adaptive self-organised topology.
Maintenance: reconfiguration and relabeling procedure
Reconfiguration using Algorithm 3 is proposed to ensure reliable message communication despite network segmentation. While relaying a message a route can be unavailable due to mobility of devices or nodes leaving due to loss of energy. In this case the relaying node is informed to reconfigure. During reconfiguration, the relaying node looks for new connections in its transmission range to connect with the highest battery charge left belonging to a different network. Each node follows three steps during this adaptive reconfiguration process. Each step ensures that the network keeps updating the changing availability of high energy nodes while considering the mobility and density of the dynamic context. This ensures that nodes are connected with a new network and routes exist for the delivery of messages.
In the first step a node, let’s call it A, disconnects from any node that either has no battery charge left or is running so low on charge that it will not be able to receive any more messages. In the second step nodes that are no longer within the transmission range are removed from the node’s local view \(l_{v}\) and their possible links are disconnected. If all connections were removed during the previous steps then the node also changes its own sub-tree identifier back to its own unique identifier and it recursively asks all still connected nodes to change their sub-tree identifier back to the caller’s unique identifier i.e., to the unique identifier of node A. This ensures that all subnetworks that emerge from this step have unique identifiers, thereby maintaining consistency.
In the final step the node looks for possible new neighbours to which to connect. As nodes are mobile, they follow the same connection procedure described before in Algorithm 1 to prevent loops and still connect to new nodes with high energy.
×
This results in a newly connected network with a different topology and new routes for message exchange. Once these three steps are completed the design goal of ensuring reliable message delivery, scalability and longevity of the network for different densities are achieved.
Protocol evaluation and performance analysis
This section presents the implementation of the algorithms and simulations that were run to evaluate the performance. To focus on interaction of autonomous agents, needed for self-organisation and emergence NetLogo was chosen over alternatives such as ns-2, ns-3 and OMNeT++, as a level of abstraction for the changing spatio-temporal context of mobile devices (Duckham 2012; Tisue and Wilensky 2004; García-Magariño et al. 2019; Kiess and Mauve 2007) (rather than the simulators used in electronic engineering for studying hardware-level modifications).
Modelling an ad-hoc communication network
The model assumes a two-dimensional square world divided into a grid. Agents2 move freely over the grid and interact. The size of the world can be changed so that the agent density can be controlled. NetLogo executes the algorithms for each agent individually and once all agents have completed their computations the simulation time, denoted as a tick, is incremented by one and every node again executes the algorithms outlined in the previous section, etc.
Agents represent devices/nodes, each with their own battery capacity. Different types of devices are modelled: a percentage of high-end phones such as Apple iPhones (with a maximum battery charge of 3000 mAh) and a percentage of low-end budget phones, non-smartphones such as earlier versions of Nokia or Samsung (with maximum battery capacity of 2000 mAh). The average assumed battery capacity is 2500 mAh. To replicate a resource-constrained environment with sudden power loss, batteries are on average assumed to be 60% charged thus with an average charge of around 1500 mAh. From a normal distribution with a mean of 1500 mAh and a standard deviation of 275 mAh values are drawn to initialize the battery charge of each agent.
Phones are assumed to use Bluetooth Low Energy (BLE) to make direct peer-to-peer connections to other agents within their transmission range (r). All agents are assumed to have the same transmission range. Agents can only directly send and receive messages with other agents within their transmission range. This paper assumes a transmission range of 5 units (in NetLogo) unless otherwise indicated. How this translates to actual values in more realistic environments is outside the scope of the paper. Furthermore, each agent is initialized at a random starting position in the grid, where agents can move independently at a fixed constant speed, turning randomly. Following connection procedure Algorithm 1 a scale-free network emerges with agents with high battery capacity at central locations in the network.
The algorithms from section “Methodology: protocol design and pseudo-code of algorithms” are implemented in NetLogo agents, whereby each action, i.e., either getting connected, sending or receiving messages, or reconfiguring has an associated energy cost. At each iteration, sender agents are selected to send messages to other agents selected as receiver agents. Each sender agent enquires a route and if a route is present relays the message to the next relay or hop in the route. The next relay node or hop relays the message in the next tick. If a route is not present it triggers a reconfiguration.
The transmission range, residual battery capacity, the cost of sending, receiving, and relaying messages, and the cost of reconfiguration are all based on empirical results for BLE 5.0 (Texas Instruments 2018) on mobile devices. Table 2 shows the cost associated with sending, receiving and relaying a single message over the network by a mobile device.
Table 2
Energy consumption associated with sending and receiving a single SMS over a BLE connection (Texas Instruments 2018)
Activity
Power draw (mA)
Duration (mS)
Size bytes
Time*current (mAmS)
Wakeup preprocessing
5
1000
5000
Receiving (Rx)
22
1120
140
24,620
Inter Frame Space (IFS)
15
150
2250
Transmission (Tx)
28
1120
140
31,360
Post processing
8
1400
11,200
Total time
4790
Total time * current
74,450
To calculate the energy consumption of a node, each action is converted to same unit of milliAmpere per minute. Table 2 is used to calculate the battery cost of sending and receiving messages. Other actions and their associated energy cost involved such as wakeup preprocessing, Inter Frame Space (IFS) and post processing are also defined in the table for the Bluetooth connection procedure (Lindh et al. 2017).
During the simulation set-up, each node loses battery charge based on these activities. When the node follows Algorithm 2 for communication, it loses energy based on the size of the message. Each message is assumed to be 140 bytes long.
The amount of lost battery charge is calculated as the product of the power drawn per byte (in milliWatts) and the duration associated with sending the message (in miliseconds). Using Ohm’s law, the product is then converted to milliAmpere-minute, that represent the cost of sending or receiving per message.
Relaying is the sum of the cost associated with sending and receiving. Every node also has a specific cost associated with advertising its view multiplied by the number of neighbors in its view (Lindh et al. 2017). Once an agent connects to the network, the next step is to send or receive information. Algorithm 2 is executed by agents as explained above in the message exchange procedure.
To analyze the performance of the protocol (all the algorithms together) and validate the expected energy efficiency, a set of experiments has been designed to evaluate longevity, reliability and scalability of the proposed approach. Density, population (number of agents) and transmission range are varied to simulate the dynamic circumstances under which the protocol is envisioned to function.
Longevity evaluation
The first experiment is designed to evaluate the longevity of the network. The longevity of the network is measured as the lifetime of the network, where participating nodes are able to communicate. In this evaluation a 3 × 3 factorial experiment is used with varied density and transmission ranges. The number of nodes and repetition are kept constant. To vary the density area is changed.
Therefore, 0.39 density equals 100 nodes in a area of 17 × 17, followed by 0.17 where the area is 25 × 25, and finally by 0.04 which equals area of 50 × 50. For each density, the number of messages exchanged also varies from 1 message per node to 5 messages and finally to 10 messages per node.
The outcome is the amount of time in ticks it takes before there are only 10% nodes left with battery capacity to communicate. Density is manipulated by varying the canvas size of the world in NetLogo 6.0.4, keeping the number of nodes constant. The parameter settings for this experiment are given in Table 3.
Table 3
Longevity evaluation parameters for varying density and message exchange
Parameter
Value
Number of nodes
100
Density
0.39, 0.17, 0.04
Transmission range
5
Total messages sent and received per iteration
1, 5, 10 (per node)
Repetition
100
Scalability evaluation
To evaluate scalability, i.e., whether the network can scale up and down with a changing population (number of nodes), the density is fixed and the population is varied. Density is again defined as the number of nodes per unit of area and calculated by dividing the population by the unit area. In this evaluation the simulation area varies according to the population that varies between 50, 100 and 200 to maintain the density.
For example for 50 nodes the area is fixed at 35 × 35 providing a density of 0.04. To keep the density fixed, the area changes as the population changes, therefore, for 100 nodes the area is 51 × 51, for 200 nodes the area is 71 × 71.
For each population, the number of messages exchanged also varies from 1 message per node to 5 messages and finally to 10 messages per node. Each simulation cycle the transmission range remains the same with 5 units. The battery charge assumptions are similar to the earlier longevity evaluation. This experimental evaluation is again repeated with 100 runs for each population size and parameters given in Table 4.
Table 4
Scalability evaluation parameters
Parameter
Value
Number of nodes
50, 100, 200
Density
0.04
Transmission range
5
Total messages sent and received per iteration
1, 5, 10 (per node)
Repetition
100
Population is varied for fixed density
In the last of the experiments, density is varied by varying the number of nodes between 50, 100 and 200, keeping the area constant at 25x25. This gives us a density of 0.08, 0.16 and 0.32. In each case nodes sent either 1, 5 or 10 messages. The settings are provided in Table 5.
Table 5
Scalability evaluation parameters
Parameter
Value
Number of nodes
50, 100, 200
Density
0.08, 0.16, 0.32
Transmission range
5
Total messages sent and received per iteration
1, 5, 10 (per node)
Repetition
100
Density is varied for fixed area of 25 × 25
Reliability evaluation
To determine if messages are reliably sent and received this experiment is designed to determine the number of undelivered messages throughout the whole network lifetime the same experiment setting as scalability. The evaluation parameters are the same as depicted in Table 4 and are similar to before.
Results and discussion
This section presents the results from the experiments discussed in the previous section. Three major performance outcomes are considered, as described above: longevity, scalability and reliability.
Longevity
The evaluation varies the density across three levels, and the number of messages sent range across three different levels, for a 3 by 3 design. As a test of statistical significance, Analyses of Variance (ANOVA) were performed (Franklin and Agresti 2007). The main effects of the density and number of messages, and the interaction effect of density and number of messages, on longevity, were examined, to test if longevity would be affected by differences in density and number of messages. Longevity was significantly different for different densities (\(\text {F}(2, 891) = 52293.5\), \(\text {p} < 0.001\)). Longevity was different for different number of messages sent (\(\text {F}(2, 891) = 64164.4\), \(\text {p} < 0.001\)). The effect of the number of messages sent on longevity was significantly different for different densities (\(\text {F}(4, 891) = 7707.6\), \(\text {p} < 0.001\)).
Figure 2 shows that for the sparse density of 0.04, the simulation runs longer in comparison to higher densities of 0.17 and 0.39. This can be explained because when the density is very low the chances of getting connected and relaying reduce, hence the simulation runs longer. However, the nodes are disconnected with hardly any routes to relay. In a medium dense area represented with density 0.17, the longevity is lower than for a sparsely populated area because there are higher chances of being connected but longer relaying routes, thus increasing the number of relays and minimizing the lifetime.
Fig. 2
The longevity of the network for 100 nodes at different densities and transmission ranges
×
In 0.39, the chances of a higher number of relays with higher energy is more than for other densities. Thus agents/nodes can stay connected longer than with density 0.17 but since it provides ample opportunity to form a network, it runs longer than 0.04. Similarly, the effect of number of messages can be easily seen on a lower density as sending a single message does not require too many reconfigurations. However when there are multiple messages to be sent, the nodes need to reconfigure a lot to find routes for pending messages.
This explains the declined longevity in sparsely populated areas for sending multiple messages. Whereas for densely populated areas, the number of messages does not cause many changes in their longevity due to the nodes being connected and relays being present. Higher density implies more connections being formed during the lifetime of the network. Note that run times of real networks will be highly dependent on specific circumstances such as actual battery charges and number of messages sent.
Scalability
To assess scalability, the effect of the number of nodes on the time it takes for the network to stop functioning is evaluated. The number of nodes is varied between 50,100 and 200, while the density is kept constant at 0.04 by changing the simulation area accordingly. The number of message exchanged is varied between 1, 5 and 10.
Scalability was significantly different for different numbers of nodes (\(\text {F}(2, 891) = 1175.8\), \(\text {p} < 0.001\)). Scalability was different for different number of messages sent (\(\text {F}(2, 891) = 30625.7\), \(\text {p} < 0.001\)). The effect of the number of messages sent on scalability was significantly different for different numbers of nodes (\(\text {F}(4, 891) = 15.6\), \(\text {p} < 0.001\)). Figure 3 shows that the run time of the network extends as the population size increases. This can be explained as follows:
Fig. 3
The Scalability plot of the network for different population at fixed density = 0.04 and transmission range = 5
×
As the battery charges of the devices are assumed to be distributed as a normal distribution (see previous section), for higher population sizes, the total number of nodes with high battery charge is higher. With a higher total number of nodes there are significantly more high energy node outliers with a residual battery capacity that is higher than the rest. These nodes are crucial in the functioning of the network, because they use a relatively large amount of energy for routing purposes. While the average routing length in the network becomes higher, the larger number of high-energy nodes mitigates this effect and prolongs the lifetime of the network.
On the contrary for smaller populations such as 50 nodes, the number of nodes with a high battery capacity is small due to the initialization using a normal distribution. This results in a few critical nodes and thus lower run times. With the assumption that battery charge in a population is normally distributed, the presented algorithm shows that it scales up for larger population sizes.
The effect of number of messages is the same as for longevity, higher frequency of messages results in more sending, receiving and relaying along with pending messages. Thus for lower frequency of just one message, the network runs longer. However, for higher frequency there is significant decrease in the run time. The assumption that the battery charge is normally distributed for a random population sample is unverifiable. Actual real life experiments are needed to evaluate this further, but the presented results show promise.
In the previous simulations, density was either kept constant, or the density was varied by keeping the number of nodes constant in a varying area. Density can also be varied by keeping the area constant, while the number of nodes is varied. This allows for the assessment of the effect of introducing more nodes. As the population increases, the number of connections and relays increase as well. As can be seen in Fig. 4, the simulation runs longer for a sparse population. However, the effect of relaying seems to be much smaller than the effect of the number of connections for denser populations: A higher message frequency has little impact.
Fig. 4
The Scalability plot of the network for different densities at fixed area = 25. Density is varied for fixed area of 25 × 25 and transmission range = 5
×
Reliability
To evaluate the reliability of messages, the number of messages sent, received and failed were calculated for the same settings as when evaluating scalability. Reliability was significantly different for different numbers of nodes (\(\text {F}(2, 891) = 853.8\), \(\text {p} < 0.001\)). Reliability was different for different number of messages sent (\(\text {F}(2, 891) = 1204.7\), \(\text {p} < 0.001\)). The effect of the number of messages sent on reliability was significantly different for different numbers of nodes (\(\text {F}(4, 891) = 8.5\), \(\text {p} < 0.001\)).
Figure 5 displays the boxplot with the x-axis representing the percentage of messages delivered ranging from 0 to 100% and y-axis representing the increasing number of nodes. In all scenarios, the reliability is always observed above 80%. Thus in general most messages are delivered, unless the receiver dies before the message is relayed to it.
Fig. 5
The reliability of the network for varying density and message exchange for a density of 0.04
×
There is a difference observed while varying number of nodes. This is because a sparsely populated network runs longer than a densely populated network, thus giving nodes more time to stay alive and deliver messages when there is an encounter and a network forms. Whereas in a densely populated area, the nodes quickly die as there is a network present and more relaying is done.
If nodes die quickly, a central node when leaving the network can result in many messages being dropped. This explains the similar trend observed while frequency of messages being sent is varied. However, the reliability remains above 80% in all densities and frequency of messages.
Comparative analysis: similarities and differences with existing work
To the authors’ knowledge there is no existing work that achieves energy efficiency through topology control for mobile ad hoc networks of mobile phones, with little preparation needed in advance. The proposed solution is positioned at the intersection of three research areas, each of which are described below in more depth:
Hybrid ad-hoc networks: mobile ad hoc networks that focus primarily on restoration of existing infrastructure, centrally designing and maintaining a new topology positioning wireless access points (and UAVs) strategically with respect to stationary access points to acquire connectivity.
Wireless sensor networks: mobile ad hoc networks that specifically cater to power-constrained sensors and focus on energy efficiency of these sensors with respect to the task at hand that mandates temporal connectivity through topology and power control.
Peer-to-peer (P2P) phone-based applications: Peers form ad hoc networks for routing most often based on mesh topology. There are, however, P2P phone-based applications that deploy an adaptable topology that are, to some extent comparable, as discussed below.
Hybrid ad-hoc networks
There is some overlap between this field and the proposed protocol, as the access points and high-energy nodes play a similar role, as they take over the burden of relaying messages and act as routers between phones (Raza et al. 2016; Santos et al. 2009). However, they are different because access points have their own power supply and are centrally managed, while the proposed protocol is distributed and works on local interaction, while still being immediately implementable. Therefore, the proposed protocol is preferred over hybrid ad hoc networks in situations where logistics issues prevent bringing in equipment, time is of the essence, or situations where centralized solutions are undesirable. Hybrid ad hoc networks may be preferred for situations where solutions are required for long periods of time as it is easier to keep the access points charged.
Wireless sensor networks
The proposed protocol achieves energy efficiency through topology control. This is also common in the field of wireless sensor networks (Rault et al. 2014; Kiani et al. 2015; Piechowiak and Zwierzykowski 2014; Aziz et al. 2013) within which battery-powered sensors are used primarily for long-term data collection. The algorithms developed for wireless sensor networks, however, make use of unique abilities of sensors, such as: their ability to sleep for long periods of time (as used in, for example, the SPAN protocol) (Chen et al. 2002a); their ability to manipulate their transmission range (Chen et al. 2002b); their ability to reduce the amount of information exchanged, e.g. using data reduction techniques (Naeem et al. 2013). These options are not available or feasible for mobile phones.
The primary similarity of the proposed protocol and such distributed topology protocols is that they are based on the fundamental design choice of local context awareness and distributed topology formation. Sensor networks often use local optimization or location-based topology control mechanisms such as LMSTs (Local Minimum Spanning Trees) (Santi 2005). LMSTs have also been shown to be used effectively for energy efficiency (Li et al. 2005). The protocol proposed in this paper extends this work by creating local minimum spanning trees on the fly, dynamically adapting the topology to the frequently changing spatial-temporal-resource context without manipulating transmission range nor relying on knowledge of node connectivity (Ingelrest et al. 2004; Cartigny et al. 2005; Abiuzi et al. 2016).
Peer-to-peer phone-based applications
The proposed protocol is not that different from P2P networks of mobile devices that exploit their WiFi or Bluetooth capacity to form direct connections. The difference lies in the topology, as current P2P networks employ a full mesh topology, in which all phones are assumed to be connected to all other phones within their range. Current P2P protocols for energy efficiency focus primarily on improving routing (Tsai et al. 2017; Chou et al. 2007; Mokryn et al. 2012) by minimizing the amount of information maintained by each peer and exchanged between peers. Routing and topology, however, are fundamentally different aspects of communication. Topology forms the backbone on which routing protocols can be run, while routing is a process of maintaining updated routes of mobile nodes to ensure reliable delivery of messages. The topology control protocol proposed in this paper is compatible with most routing protocols, and possibly, synergistic energy efficiency increases can be achieved by combining the energy efficient loop-free scale-free topology of the proposed protocol with the newest developments in energy-efficient routing (Ramrekha et al. 2012; Abiuzi et al. 2016; Anand and Prakash 2010; De Rango et al. 2008). This is subject to future research.
Conclusion and future work
When physical network infrastructures fail, infrastructure-less communication networks such as mobile ad-hoc networks (MANET), can provide an alternative. This paper introduces a protocol that consists of three algorithms for creation, maintenance and message exchange for an infrastructure-less ad-hoc communication network using mobile devices. In three evaluations in a simulated environment, this protocol was demonstrated to be scalable, long-lasting, and reliable, in a variety of contexts.
Energy efficiency was a primary design consideration for this protocol. Participating devices may vary in their battery charges, and recharging facilities are not guaranteed. Once nodes run out of battery charge and leave the network, nodes become disconnected and the network may become fragmented. It was vital in the new design to take spatio-temporal resource information into account. The proposed protocol achieves this through preferential attachment to high resource nodes in the nodes’ transmission range. In this manner, a loop-free, scale-free adaptive topology is formed, that avoids network fragmentation through the preservation of battery charge in low-energy nodes, and restores fragmented networks through flexible adaptation.
The proposed protocol has a number of advantages. First, it is adaptive to the environment. This means it is applicable in scenarios that may vary in the density and mobility of devices, and in the availability of energy sources. Second, it is energy-efficient through changes in topology. This means it can be flexibly be combined with different routing protocols. Third, the protocol requires no changes on the hardware level. This means it can be implemented on all current phones, also in the Third World, without any recalls or investments in hardware changes.
The results of the evaluation confirm that the self-organizing context-adaptive protocol enables mobile devices to connect and communicate reliably and scale up despite changing energy availability and density of nodes. Future work will necessarily focus on a number of factors. These include trade-offs between reliability and robustness. Furthermore, the effects of churn, and the costs of the reconfiguration step need to be studied further. Lastly, the performance of the self-adaptive ad-hoc communication network needs to be evaluated outside of lab conditions.
Although more work is needed, the current article has demonstrated one solution that can be implemented on multitudes of phones, without further requirements on the hardware. In this way, implementation can be as simple as the development of a new mobile app, and the improvements in energy efficiency can have an immediate positive impact.
Acknowledgements
The authors kindly acknowledge support from the Engineering social technologies for a responsible digital future programme at TUDelft.
Competing interests
The authors declare that they have no competing interests.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Note that the terms nodes and devices are used interchangeably in this paper. Both refer to a device that has a Wi-Fi or Bluetooth interface and can join other devices that are part of a network within its transmission range, such as a mobile phone
