# GreenLink: An Energy Efficient Scatternet Formation for BLE Devices

Authors: Xiaoliang Wang; Ke Xu; Bo Mao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Formation technology of Bluetooth scatternet has been researched for over a decade and promoted by rapid development of wearable computing. Limited by technical features, the traditional scatternet formation technology has not been widely used in real commercial chipsets. As new features are introduced into the Bluetooth core field, the ability to use Bluetooth Low Energy (BLE) technology to construct a network becomes the reality and puts forward new challenges. The scatternet formation technology facing to BLE and wearable devices requires significant improvement in energy efficiency. According to our experiments, 92% of the system energy consumption can be attributed to central nodes. In this paper, we presented a Bluetooth scatternet formation technology focused on energy efficiency, GreenLink, which minimizes the amount of central nodes by enhancing system aggregation degree to ensure excellent energy-saving performance. Meanwhile, we implemented a prototype of GreenLink on Nordic nRF51822 chipsets, conducted experiments, and verified in practice. According to the experiments, GreenLink used only 30% central nodes and reduced 50% system energy consumption compared with traditional technology.


---

## Body

## 1. Introduction

Since its appearance in the 1990s, Bluetooth has become a widely used technology for short-range communication. With an explosive growth of smart home and wearable computing, lots of smart devices such as smart lights, smart switches, smart watches, and smart scales are based on Bluetooth because of its simplicity, energy efficiency, and low cost. However, the short transmission range and low ability to cross over obstacles still limit the wider use of Bluetooth in smart home scenarios. For instance, you may fail to control your lamps in the bedroom from your living room because it is out of the control range. On the other hand, you have to use your smart scale with holding your smartphone so that the application can record your weight through the Bluetooth link. Multihop transmission is unavailable between Bluetooth nodes, which has limited many features and use cases.Network formation technology of Bluetooth has over a decade of research history. Piconet is a simple network of Bluetooth nodes, and it allows only one master device to interconnect with up to seven active slave devices. Scatternet is a group of piconets which are connected by bridge nodes and supports communication between more than eight devices. Among those scatternet formation algorithms for mobile ad-hoc devices, there are several for Bluetooth devices such as BluesStars [1], Bluemesh [2], Bluetrees [3], and SHAPER [4]. Previous works on Bluetooth scatternet formation are nonapplicable to BLE due to performance enhancement and introduction of new features.In 2017, Bluetooth Special Interest Group proposed Bluetootch Mesh which is a new bluetooth networking technology and is based on Bluetooth Core v4.0. The Bluetooth Mesh Profile builds on the broadcasting of data over the Bluetooth low-energy advertising channels and the mesh network will be based on flooding communication model. However, consider that the BLE devices are energy-constrained, flooding communication may not be the best choice, and it will cost extra energy and may cause high congestion. How to design a scatternet formation technology focusing on enhancing energy efficiency would be an essential issue for BLE devices.Scatternet includes two kinds of nodes. One is called central node, which works in dual mode as a bridge connecting two piconets. And the other one is called peripheral node, which only works in slave mode. According to our experiments on BLE chipsets, compared with the peripheral nodes, the energy consumption attributed to central nodes is the main source of the system energy consumption (ratio up to 92%). Through our experiment on BLE chipsets, although reducing the amount of central nodes in a scatternet will cause an extra overhead for residual central nodes, it is possible to achieve a considerable improvement of energy efficiency. The additional energy consumption of the residual central nodes caused by extra overhead is negligible to their original energy consumption. Therefore, the system energy consumption is significantly reduced. Meanwhile, this approach can also obtain another benefit to enhance energy efficiency. As in a tree topology network, reducing the number of central nodes can lead to a decrease in number of layers and average path length between any two nodes would be reduced. As a result, the reduction of system transmitting overhead will cause lower energy consumption.This paper proposes a new technology of scatternet formation for BLE called GreenLink. GreenLink is the first technology to focus on energy efficiency of BLE scatternet formation. We conducted experiments both in simulation environment and in existing Bluetooth chipset Nordic nRF51822. According to our experiments, in contrast with SHAPER, GreenLink reduces about 70% central nodes and 50% system energy consumption. This paper makes the following contributions:(i)
Within the scope of our knowledge, this paper firstly proposes a scatternet formation technology for energy-constrained devices focused on system energy efficiency.(ii)
We also propose the idea of optimizing the system energy consumption by reducing the number of central nodes and enhancing aggregation degree of scatternet.(iii)
We implement the prototype of GreenLink on a real BLE chipset named Nordic nRF51822, conduct experiments, and verify in practice. It paths the way to various researches on similar application.


## 2. Architecture of GreenLink

### 2.1. Motivation

On the basis of the Bluetooth Low Energy, BLE allows a Bluetooth node to work on both master mode and slave mode since version 4.1 in which the scatternet formation can be supported on protocol level for the first time. In the researches of the traditional scatternet formation technologies, the appearance of this feature helps the design of combining multiple piconets into a scatternet to become possible by bridge nodes. However, BLE devices have a high sensitive level to energy consumption, and scatternet formation will cause extra energy consumption. Therefore, we need a scatternet formating scheme to attain the networking features and reduce energy consumption for Bluetooth Low Energy as far as possible.In scatternet, nodes can classify as central nodes and peripheral nodes. Central nodes usually include root node and the nodes working in master/slave mode. Peripheral nodes contain the nodes working in slave mode. Slave node can connect to only one master node, and master node can connect to a plurality of slave nodes. We use Nordic nRF51822 Bluetooth chipsets to conduct experiments for measuring the real energy consumption of different types of node in scatternet.We implemented the topological structure shown in Figure1(a) with 10 Nordic nRF51822 chipsets, to test the chipset energy consumption in different working status. Because chipsets have the same working voltage, we use average working current as a measure of energy consumption (Table 1).Table 1
Energy consumption of different nodes.
Network Topology a Network Topology b Number of central nodes 6 4 Number of peripheral nodes 4 6 Energy proportion of peripheral nodes 1.1% 2.6% Energy proportion of central nodes 92.29% 84.14% System energy consumption 46.71mA 34.13mAFigure 1
System energy consumption in different topologies.
(a) (b)According to the experiment, we find that the energy consumption of central nodes is the main part of the system energy consumption. Therefore, we adjust the networking topology and test again, as shown in Figure1(b). In the next experiment, we reduce the amounts of central nodes, and the result has a significant reduction in energy consumption.Based on experiments above, we believe that reducing the number of central nodes as much as possible can bring a significant reduction of the whole system energy consumption. However, the reduction of the number of central nodes causes extra overhead for residual central nodes. We conducted following experiment for measuring the increase of energy consumption of central nodes.We respectively measured the extra energy consumption when we increase connections and transfer rate of central nodes. The results of our preliminary experiments are shown in Tables2 and 3. According to the experiments, increasing the connections and transfer rate of central nodes will cause extra energy consumption. But compared with original energy consumption, the increase is negligible.Table 2
Energy consumption of connection.
Connections of central node Average working current (mA) Percentage of increased energy consumption 1 7.012 +0.00% 2 7.237 +3.21% 3 7.485 +6.75%Table 3
Energy consumption of transmission.
Transfer rate of central node(KB/s) Average working current (mA) Percentage of increased energy consumption Percentage of max transfer rate 0 7.485 +0.00% +0.00% 0.54 8.080 +7.95% +10.13% 2.96 8.290 +10.75% +55.53% 5.33 8.700 +16.23% +100.00%Therefore, reducing the number of central nodes as much as possible will not greatly increase the energy consumption of other nodes but significantly reduces the system energy consumption by changing parts of central nodes into peripheral nodes.Meanwhile, the reduction of number of central nodes and layers of topology helps to decrease the count of average hop between any two nodes, which has a positive effect on optimizing the system energy consumption by reducing the overhead of system forwarding.Above all, we proposed a scatternet formation technology for Bluetooth 4.1 protocol called GreenLink. Energy efficiency is an essential issue for BLE devices. GreenLink focus on reducing system energy consumption by minimizing the number of central nodes.


### 2.2. Design of GreenLink

To improve the aggregation degree of scatternet and minimize the number of central nodes, Bluetooth nodes need to know the relative position of all nodes as much as possible and tend to connect with the node which can link with more nodes. Obviously, a master controller who knows the global information can calculate a better network topology. However, Bluetooth node’s radio range is limited. It is difficult to find a node to get global information only by scanning broadcast packet before connection established. Furthermore, there are some mobile nodes whose relative position always changes so that controller is difficult to quickly grasp all changing information. Therefore, a distributed and localized mechanism is much more practical.Based on Bluetooth 4.1, we designed a distributed algorithm named GreenLink for scatternet formation. Our algorithm creates the scatternet and minimizes the system energy consumption as much as possible. The main idea of GreenLink is that each node tends to link the one which can connect with more nodes. This method makes lots of links concentrate on a few nodes, which can reduce the number of central nodes and system energy consumption.In GreenLink, each node should store and keep updating some parameters shown in Tables4, 5, and 6.Table 4
Parameters list of each node.
Parameter Description N s The number of neighbours discovered by scanning broadcast message N i n d The sum number of scanned nodes’Ns L n e a r ​ Data list of the nodes scanned P a r e n t Master node’s MAC address N c The number of slave nodes L c h i l d ​ List of slave nodesTable 5
Contents ofLnear​.
Node 0 Node 1 Node 2 … M A C _ A D D R M A C _ A D D R M A C _ A D D R … N s N s N s … N i n d N i n d N i n d …Table 6
Contents ofLchild​.
Node 0 Node 1 Node 2 … M A C _ A D D R M A C _ A D D R M A C _ A D D R …At first, we design a mechanism of node discovery and message exchange; each node can get enough information to choose a node to connect with.Bluetooth 4.1 allows a node to keep broadcasting and scanning at the same time. Each node keeps sending out broadcast packets including itsNs and Nind. Meanwhile, each node keeps scanning and receiving broadcast packet. If a node receives a broadcast packet from node X, it begins to find whether the node X has been recorded in Lnear. If it has been recorded, update the parameters of node X in the Lnear according to the broadcast packet. Otherwise, add a new piece of record into Lnear, and Ns add 1. Then, calculate Nind by the following formula:(1)Nind=∑i=0Ns-1Lneari.NsAfter a period of broadcasting and scanning, there are two conditions to stop nodes discovery phase:(i)
Continue to receiveTp broadcast packets but not change any parameters.(ii)
Have beenTt seconds not change any parameters.ValuesTp and Tt can be set according to the specific situation or experience. Algorithm 1 shows the process of node discovery phase.Algorithm 1:BroadcastScan.
1:Ns ← 0, Nind ← 0, Nchild ← 0, Parent ← NULL 2:while not  Timeout()  do 3:if  Receive  BroadcastPacket  then 4:pB ← BroadcastPacket 5:if  pB.ADDR∈Lnear​  then 6:UpdateNearlist() 7:else 8:Lnear[Ns].Ns←pB.Ns 9:Lnear[Ns].Nind←pB.Nind 10:Lnear[Ns].ADDR←pB.ADDR 11:Ns ← Ns + 1 12:Nind ← ∑Lnear​.Ns 13:LinkSelection() 14:returnAfter nodes discovery phase, nodes will apply the link selection algorithm to choose which node should link to it.At first, Bluetooth node sorts itsLnear. For any two nodes A and B, we use Algorithm 2 to decide the priority of connection.Algorithm 2:NodeCompare.
Require:  nodeA, nodeB Ensure:  1  : nodeA > nodeB;  0  : nodeA = nodeB;  −1: n o d e A < nodeB; 1:if  nodeA.Ns>nodeB.Ns  then 2:return1 3:if  nodeA.Ns<nodeB.Ns  then 4:return  -1 5:if  nodeA.Ns=nodeB.Ns  then 6:if  nodeA.Nind<nodeB.Nind  then 7:return1 8:if  nodeA.Nind>nodeB.Nind  then 9:return  -1 10:if  nodeA.Nind=nodeB.Nind  then 11:if  nodeA.ADDR>nodeB.ADDR  then 12:return1 13:if  nodeA.ADDR<nodeB.ADDR  then 14:return  -1 15:if  nodeA.ADDR=nodeB.ADDR  then 16:return0Then, find the node with the highest level of priority fromLnear, named nodem. If nodem is larger than the current node, current node sends a link request to nodem and then establishes a connection with nodem. Current node sets the value of Parent to nodem’s MAC address.Based on Bluetooth 4.1, nodes also keep scanning broadcast packets at the same time. Once the master node receives a link request broadcast packet, it will establish a connection with the slave node. Then itsNc increases by 1 and adds the source node into Lchild.After a period of time, most of nodes have been linked to a scatternet. For the rest of nodes whoseParent is NULL will trigger the timeout event and then try to link with a parent node, take a node from Lnear by order and call it nodem. If nodem is not found in Lchild, current node sends a link request to nodem by broadcasting and then establishes a connection with nodem. Current node updates the value of Parent to nodem’s MAC address. If each of the nodes in Lnear also belongs to Lchild, this means that current node is a root node.Finally, we will get a tree-shape scatternet. Algorithm3 shows our link selection algorithm.Algorithm 3:LinkSelection.
1:while  true  do 2:if  Receive  LinkRequestPacket  then 3:pR←LinkREquestPacket 4: Establish  link  with  pR.ADDR 5:Lchild​Nc  ←  pR.ADDR 6:Nc←Nc+1 7: Sort(Lnear​) 8:if  Parent≠NULL  then 9:continue; 10:nodem  ←    Lnear0 11:if  Compare(nodemyself,nodem)<0  then 12:Send  pR  to  nodem.ADDR 13:Parent  ←  nodem.ADDR 14:else  NodeComparenodemyself,nodem≥0 15:if  Timeout  then 16:for all  nodem∈Lnear​  do 17:if  nodem∉Lchild​  then 18:Send  pR  to  nodem 19:Parent  ←  nodem.ADDR 20:return 21:return


### 2.3. Topology Self-Healing

GreenLink guarantees a topology self-healing ability and node mobility by including nodes joining the topology and reconfiguring the network when a node abandons the network or moves. In order to adapt to the changes of network and to support node mobility, each node turns on broadcasting with certain frequency and broadcasting will not always be on for considering of the high energy consumption. When a new Bluetooth node arrives in the current network radio range, the new node will discover other nodes by scanning broadcast packets just like the node done in discovery phase. And then, the new node can connect with other nodes by running the link selection algorithm. Therefore new nodes always have the opportunity to enter the network. When a node loses connectivity with its parent, then it becomes the new root node of the subtree and search for the opportunity for join the network by scanning broadcast packets. If the new root node cannot find a suitable new bridge node for a certain time, it will send its child to join the discovery phase until one node of the subtree finds a new suitable bridge and its parent reconnects to it as its child. When a parent loses its child, it will update theNs and Nind for the neighbors and the topology will be reconfigured based on the update information if necessary.


### 2.4. Example of GreenLink

Now we illustrate GreenLink by describing a scatternet formation process with six Bluetooth nodes. Figure2(a) shows the communication range of each node. In Figure 2(b), for each node, the first number is Ns, and the second one is Nind. node3 broadcasts its Ns and Nind. node0 and node4 receive the broadcast packet and update their parameters. Figure 2(c) shows that node0 broadcasts its Ns and Nind, and adjacent nodes update their parameters after receiving broadcast packet. Keep running this process and finally get the status shown in Figure 2(d). Then nodes begin to run the link selection algorithm.Figure 2
Discovery process of 6 nodes.
(a) (b) (c) (d)n o d e 3 has saved parameters of node0 and node4 in its Lnear. Ns of node0 is greater than that of node4 and also greater than that of node3. So node3 sends a link request to node0 and then becomes a slave node of node0. node1,2,5 link with their parent node in a similar way. Figure 2(d) shows these links.However,node0 and node4 have not found a parent node yet. They have the highest priority in their own radio range. After a while, these nodes trigger the timeout event and begin to scan the nodes in Lnear. For node0, every node found in the Lnear has been its child, so the algorithm of node0 is stopped. node4 finds node3 and it is not the child of node4. node4 sends a link request packet to node3 and then link with node3.


### 2.5. Approximation Ratio of GreenLink

We try to find a scatternet formation with as fewer central nodes as possible, which aims to increase the number of peripheral nodes. This problem can be described as a graph theory problem trying to find a spanning tree with maximum number of leaf nodes. Each node represents a Bluetooth node and each peripheral represents the two Bluetooth nodes being able to communicate with each other. The graph can be described asG=V,E, V, and E, respectively, representing the set of nodes and the set of peripherals. So our problem can be described as(2)findTms.t.nTm=max⁡nT∣Twhere T and Tm are the spanning tree of G and n(T) is the leaf number of T. This problem is known as the max-leaf spanning tree problem and has been proved to be a NP-hard problem [5]. We measured the approximation ratio of GreenLink by comparing the leaf number of optimal solutions, GreenLink and SHAPER. We get the optimal solutions by traversing all solutions at first. Then we use GreenLink to generate spanning tree and compare the leaf number with optimal solution. We, respectively, process the experiments for 10 times by changing the total number of nodes from five to eighteen. On the other side, searching for a spanning tree with maximum leaf number is a NP-hard problem. So we limit the total number of nodes to ensure we can obtain the optimal solution in limited time. The result is shown in Figure 3.Figure 3
Approximation ratios of GreenLink and SHAPER.In Figure3, we found that compared with the leaf number of optimal solution, the approximate ratio of GreenLink is almost equal to 1. And the approximate ratio of SHAPER fluctuates around 60%.


## 2.1. Motivation

On the basis of the Bluetooth Low Energy, BLE allows a Bluetooth node to work on both master mode and slave mode since version 4.1 in which the scatternet formation can be supported on protocol level for the first time. In the researches of the traditional scatternet formation technologies, the appearance of this feature helps the design of combining multiple piconets into a scatternet to become possible by bridge nodes. However, BLE devices have a high sensitive level to energy consumption, and scatternet formation will cause extra energy consumption. Therefore, we need a scatternet formating scheme to attain the networking features and reduce energy consumption for Bluetooth Low Energy as far as possible.In scatternet, nodes can classify as central nodes and peripheral nodes. Central nodes usually include root node and the nodes working in master/slave mode. Peripheral nodes contain the nodes working in slave mode. Slave node can connect to only one master node, and master node can connect to a plurality of slave nodes. We use Nordic nRF51822 Bluetooth chipsets to conduct experiments for measuring the real energy consumption of different types of node in scatternet.We implemented the topological structure shown in Figure1(a) with 10 Nordic nRF51822 chipsets, to test the chipset energy consumption in different working status. Because chipsets have the same working voltage, we use average working current as a measure of energy consumption (Table 1).Table 1
Energy consumption of different nodes.
Network Topology a Network Topology b Number of central nodes 6 4 Number of peripheral nodes 4 6 Energy proportion of peripheral nodes 1.1% 2.6% Energy proportion of central nodes 92.29% 84.14% System energy consumption 46.71mA 34.13mAFigure 1
System energy consumption in different topologies.
(a) (b)According to the experiment, we find that the energy consumption of central nodes is the main part of the system energy consumption. Therefore, we adjust the networking topology and test again, as shown in Figure1(b). In the next experiment, we reduce the amounts of central nodes, and the result has a significant reduction in energy consumption.Based on experiments above, we believe that reducing the number of central nodes as much as possible can bring a significant reduction of the whole system energy consumption. However, the reduction of the number of central nodes causes extra overhead for residual central nodes. We conducted following experiment for measuring the increase of energy consumption of central nodes.We respectively measured the extra energy consumption when we increase connections and transfer rate of central nodes. The results of our preliminary experiments are shown in Tables2 and 3. According to the experiments, increasing the connections and transfer rate of central nodes will cause extra energy consumption. But compared with original energy consumption, the increase is negligible.Table 2
Energy consumption of connection.
Connections of central node Average working current (mA) Percentage of increased energy consumption 1 7.012 +0.00% 2 7.237 +3.21% 3 7.485 +6.75%Table 3
Energy consumption of transmission.
Transfer rate of central node(KB/s) Average working current (mA) Percentage of increased energy consumption Percentage of max transfer rate 0 7.485 +0.00% +0.00% 0.54 8.080 +7.95% +10.13% 2.96 8.290 +10.75% +55.53% 5.33 8.700 +16.23% +100.00%Therefore, reducing the number of central nodes as much as possible will not greatly increase the energy consumption of other nodes but significantly reduces the system energy consumption by changing parts of central nodes into peripheral nodes.Meanwhile, the reduction of number of central nodes and layers of topology helps to decrease the count of average hop between any two nodes, which has a positive effect on optimizing the system energy consumption by reducing the overhead of system forwarding.Above all, we proposed a scatternet formation technology for Bluetooth 4.1 protocol called GreenLink. Energy efficiency is an essential issue for BLE devices. GreenLink focus on reducing system energy consumption by minimizing the number of central nodes.


## 2.2. Design of GreenLink

To improve the aggregation degree of scatternet and minimize the number of central nodes, Bluetooth nodes need to know the relative position of all nodes as much as possible and tend to connect with the node which can link with more nodes. Obviously, a master controller who knows the global information can calculate a better network topology. However, Bluetooth node’s radio range is limited. It is difficult to find a node to get global information only by scanning broadcast packet before connection established. Furthermore, there are some mobile nodes whose relative position always changes so that controller is difficult to quickly grasp all changing information. Therefore, a distributed and localized mechanism is much more practical.Based on Bluetooth 4.1, we designed a distributed algorithm named GreenLink for scatternet formation. Our algorithm creates the scatternet and minimizes the system energy consumption as much as possible. The main idea of GreenLink is that each node tends to link the one which can connect with more nodes. This method makes lots of links concentrate on a few nodes, which can reduce the number of central nodes and system energy consumption.In GreenLink, each node should store and keep updating some parameters shown in Tables4, 5, and 6.Table 4
Parameters list of each node.
Parameter Description N s The number of neighbours discovered by scanning broadcast message N i n d The sum number of scanned nodes’Ns L n e a r ​ Data list of the nodes scanned P a r e n t Master node’s MAC address N c The number of slave nodes L c h i l d ​ List of slave nodesTable 5
Contents ofLnear​.
Node 0 Node 1 Node 2 … M A C _ A D D R M A C _ A D D R M A C _ A D D R … N s N s N s … N i n d N i n d N i n d …Table 6
Contents ofLchild​.
Node 0 Node 1 Node 2 … M A C _ A D D R M A C _ A D D R M A C _ A D D R …At first, we design a mechanism of node discovery and message exchange; each node can get enough information to choose a node to connect with.Bluetooth 4.1 allows a node to keep broadcasting and scanning at the same time. Each node keeps sending out broadcast packets including itsNs and Nind. Meanwhile, each node keeps scanning and receiving broadcast packet. If a node receives a broadcast packet from node X, it begins to find whether the node X has been recorded in Lnear. If it has been recorded, update the parameters of node X in the Lnear according to the broadcast packet. Otherwise, add a new piece of record into Lnear, and Ns add 1. Then, calculate Nind by the following formula:(1)Nind=∑i=0Ns-1Lneari.NsAfter a period of broadcasting and scanning, there are two conditions to stop nodes discovery phase:(i)
Continue to receiveTp broadcast packets but not change any parameters.(ii)
Have beenTt seconds not change any parameters.ValuesTp and Tt can be set according to the specific situation or experience. Algorithm 1 shows the process of node discovery phase.Algorithm 1:BroadcastScan.
1:Ns ← 0, Nind ← 0, Nchild ← 0, Parent ← NULL 2:while not  Timeout()  do 3:if  Receive  BroadcastPacket  then 4:pB ← BroadcastPacket 5:if  pB.ADDR∈Lnear​  then 6:UpdateNearlist() 7:else 8:Lnear[Ns].Ns←pB.Ns 9:Lnear[Ns].Nind←pB.Nind 10:Lnear[Ns].ADDR←pB.ADDR 11:Ns ← Ns + 1 12:Nind ← ∑Lnear​.Ns 13:LinkSelection() 14:returnAfter nodes discovery phase, nodes will apply the link selection algorithm to choose which node should link to it.At first, Bluetooth node sorts itsLnear. For any two nodes A and B, we use Algorithm 2 to decide the priority of connection.Algorithm 2:NodeCompare.
Require:  nodeA, nodeB Ensure:  1  : nodeA > nodeB;  0  : nodeA = nodeB;  −1: n o d e A < nodeB; 1:if  nodeA.Ns>nodeB.Ns  then 2:return1 3:if  nodeA.Ns<nodeB.Ns  then 4:return  -1 5:if  nodeA.Ns=nodeB.Ns  then 6:if  nodeA.Nind<nodeB.Nind  then 7:return1 8:if  nodeA.Nind>nodeB.Nind  then 9:return  -1 10:if  nodeA.Nind=nodeB.Nind  then 11:if  nodeA.ADDR>nodeB.ADDR  then 12:return1 13:if  nodeA.ADDR<nodeB.ADDR  then 14:return  -1 15:if  nodeA.ADDR=nodeB.ADDR  then 16:return0Then, find the node with the highest level of priority fromLnear, named nodem. If nodem is larger than the current node, current node sends a link request to nodem and then establishes a connection with nodem. Current node sets the value of Parent to nodem’s MAC address.Based on Bluetooth 4.1, nodes also keep scanning broadcast packets at the same time. Once the master node receives a link request broadcast packet, it will establish a connection with the slave node. Then itsNc increases by 1 and adds the source node into Lchild.After a period of time, most of nodes have been linked to a scatternet. For the rest of nodes whoseParent is NULL will trigger the timeout event and then try to link with a parent node, take a node from Lnear by order and call it nodem. If nodem is not found in Lchild, current node sends a link request to nodem by broadcasting and then establishes a connection with nodem. Current node updates the value of Parent to nodem’s MAC address. If each of the nodes in Lnear also belongs to Lchild, this means that current node is a root node.Finally, we will get a tree-shape scatternet. Algorithm3 shows our link selection algorithm.Algorithm 3:LinkSelection.
1:while  true  do 2:if  Receive  LinkRequestPacket  then 3:pR←LinkREquestPacket 4: Establish  link  with  pR.ADDR 5:Lchild​Nc  ←  pR.ADDR 6:Nc←Nc+1 7: Sort(Lnear​) 8:if  Parent≠NULL  then 9:continue; 10:nodem  ←    Lnear0 11:if  Compare(nodemyself,nodem)<0  then 12:Send  pR  to  nodem.ADDR 13:Parent  ←  nodem.ADDR 14:else  NodeComparenodemyself,nodem≥0 15:if  Timeout  then 16:for all  nodem∈Lnear​  do 17:if  nodem∉Lchild​  then 18:Send  pR  to  nodem 19:Parent  ←  nodem.ADDR 20:return 21:return


## 2.3. Topology Self-Healing

GreenLink guarantees a topology self-healing ability and node mobility by including nodes joining the topology and reconfiguring the network when a node abandons the network or moves. In order to adapt to the changes of network and to support node mobility, each node turns on broadcasting with certain frequency and broadcasting will not always be on for considering of the high energy consumption. When a new Bluetooth node arrives in the current network radio range, the new node will discover other nodes by scanning broadcast packets just like the node done in discovery phase. And then, the new node can connect with other nodes by running the link selection algorithm. Therefore new nodes always have the opportunity to enter the network. When a node loses connectivity with its parent, then it becomes the new root node of the subtree and search for the opportunity for join the network by scanning broadcast packets. If the new root node cannot find a suitable new bridge node for a certain time, it will send its child to join the discovery phase until one node of the subtree finds a new suitable bridge and its parent reconnects to it as its child. When a parent loses its child, it will update theNs and Nind for the neighbors and the topology will be reconfigured based on the update information if necessary.


## 2.4. Example of GreenLink

Now we illustrate GreenLink by describing a scatternet formation process with six Bluetooth nodes. Figure2(a) shows the communication range of each node. In Figure 2(b), for each node, the first number is Ns, and the second one is Nind. node3 broadcasts its Ns and Nind. node0 and node4 receive the broadcast packet and update their parameters. Figure 2(c) shows that node0 broadcasts its Ns and Nind, and adjacent nodes update their parameters after receiving broadcast packet. Keep running this process and finally get the status shown in Figure 2(d). Then nodes begin to run the link selection algorithm.Figure 2
Discovery process of 6 nodes.
(a) (b) (c) (d)n o d e 3 has saved parameters of node0 and node4 in its Lnear. Ns of node0 is greater than that of node4 and also greater than that of node3. So node3 sends a link request to node0 and then becomes a slave node of node0. node1,2,5 link with their parent node in a similar way. Figure 2(d) shows these links.However,node0 and node4 have not found a parent node yet. They have the highest priority in their own radio range. After a while, these nodes trigger the timeout event and begin to scan the nodes in Lnear. For node0, every node found in the Lnear has been its child, so the algorithm of node0 is stopped. node4 finds node3 and it is not the child of node4. node4 sends a link request packet to node3 and then link with node3.


## 2.5. Approximation Ratio of GreenLink

We try to find a scatternet formation with as fewer central nodes as possible, which aims to increase the number of peripheral nodes. This problem can be described as a graph theory problem trying to find a spanning tree with maximum number of leaf nodes. Each node represents a Bluetooth node and each peripheral represents the two Bluetooth nodes being able to communicate with each other. The graph can be described asG=V,E, V, and E, respectively, representing the set of nodes and the set of peripherals. So our problem can be described as(2)findTms.t.nTm=max⁡nT∣Twhere T and Tm are the spanning tree of G and n(T) is the leaf number of T. This problem is known as the max-leaf spanning tree problem and has been proved to be a NP-hard problem [5]. We measured the approximation ratio of GreenLink by comparing the leaf number of optimal solutions, GreenLink and SHAPER. We get the optimal solutions by traversing all solutions at first. Then we use GreenLink to generate spanning tree and compare the leaf number with optimal solution. We, respectively, process the experiments for 10 times by changing the total number of nodes from five to eighteen. On the other side, searching for a spanning tree with maximum leaf number is a NP-hard problem. So we limit the total number of nodes to ensure we can obtain the optimal solution in limited time. The result is shown in Figure 3.Figure 3
Approximation ratios of GreenLink and SHAPER.In Figure3, we found that compared with the leaf number of optimal solution, the approximate ratio of GreenLink is almost equal to 1. And the approximate ratio of SHAPER fluctuates around 60%.


## 3. Evaluation

The experiment contains three aspects: the number of central nodes, average hop count, and energy consumption of the system. Considering that GreenLink is a tree-structure scatternet formation algorithm, we have chosen SHAPER as the main comparison algorithm in the experiment. In addition, we increased BlueHRT as one more comparison algorithm in the first two aspects of the experiment. We implemented the prototypes on Nordic nRF51822 chipsets (shown in Figure5) and simulation platform called GreenPlatform designed by ourselves. Since the transmission distance of Bluetooth is significantly influenced by environment, we set 10m as the transmission distance of a Bluetooth node. We conducted two experiments on GreenPlatform. Those experiments measured the variation tendency of the number of central nodes and the average hop count using GreenLink, SHAPER, and BlueHRT, respectively. The number of nodes in the experiments increased from 5 to 80 in three environments: 15∗15m, 20∗20m and 25∗25m. Meanwhile, given the location relationships between twelve Nordic nRF51822 chipsets, we measured the energy consumption of the system using GreenLink and SHAPER on real BLE chipsets.Although there is no limit for the connection number of a Bluetooth node in BLE version 4.1, limitation still exits for real BLE chipsets considering the hardware performance. Considering this issue, we designed two groups of comparing experiments depending on whether there was a limitation of connection number or not.According to the experiments, SHAPER and BlueHRT are basically consistent in these first two aspects. BlueHRT has about 11%–17% more central nodes than SHAPER and about 40% less average hop count. Compared with SHAPER, the amount of central nodes with GreenLink is 30% and the average hop count is 20%. On the other hand, the system energy consumption of the scatternet applying GreenLink is only 35% of the scatternet using SHAPER when there is no limit of connection number. If we change the limitation of connection number to 7, the energy consumption of GreenLink is only about 50% of SHAPER.


### 3.1. Number of Central Nodes

In this group of experiments, we used GreenPlatform and conducted six experiments divided into two groups depending on whether there was a limit of connection number or not. If there was an upper limit of connection number for Bluetooth nodes, we set it to seven in which there were six connections for their children nodes and one connection for their parent nodes. We also set the communication distance to 10m for Bluetooth nodes and randomly created five to eighty Bluetooth nodes in three different size areas (15∗15m, 20∗20m, and 25∗25m). In the conditions mentioned above, we implemented GreenLink, SHAPER, and BlueHRT. Each experiment was repeated three times to get the average data of central nodes number shown in Figure 4.Figure 4
Number of central nodes.
(a)
15 ∗ 15 m, without connection number limit (b)
20 ∗ 20 m, without connection number limit (c)
25 ∗ 25 m, without connection number limit (d)
15 ∗ 15 m, limit of connection number is 7 (e)
20 ∗ 20 m, limit of connection number is 7 (f)
25 ∗ 25 m, limit of connection number is 7Figure 5
Nordic nRF51822 chipsets used in our experiments.According to the experiments, without limitation of connection number, GreenLink could achieve a high convergence degree scatternet; nearly every node within scope of communication connected to the same parent node. As shown in Figure4(a), in the experiment process of changing the total number of nodes from five to eighty, the number central nodes is almost equal to one. By contrast, the central nodes number of SHAPER and BlueHRT rises quickly with the nodes size increasing and reaches forty-five at most for SHAPER and forty-nine for BlueHRT, which is more than 50% of the scale of all nodes. That is because of random connection mechanism of SHAPER and the ring topology in the high density area of BlueHRT.In the 20∗20m area, the space expended about 1.8 times, node density decreased, and the central nodes number of GreenLink begins to rise slowly and is up to 4 times with changing the total number of nodes from five to eighty. However, the central nodes number is still only 1/8 of SHAPER’s and 1/9 of BlueHRTs.Then we set a limitation of connection number to seven. As shown in Figures4(d), 4(e), and 4(f), the number of the central nodes of SHAPER and BlueHRT hardly changes compared with all the group of experiments mentioned above. That is because one BLE node can hardly reach its maximum number of connections with random link selection with SHAPER and central nodes of BlueHRT is mainly related to node density and distribution location. On the other hand, the central nodes number of GreenLink has an obvious increase than the situation in experiments above because of the limitation of connection number. In the three different nodes density, the central nodes number of GreenLink rises from 1 to around 20 and is about 1/2 to 1/3 of SHAPER and BlueHRT.In conclusion, the reduction of central nodes number using GreenLink has an obvious difference in performance depending on whether there is a limitation of connection number or not. However, compared with traditional scatternet formation technology, there is a significant improvement for reducing central nodes number using GreenLink which can decrease about 70% central nodes in a scatternet.


### 3.2. Average Hop Count

In this group of experiments, we based it on the same settings as experiments above (connection number of node, nodes density, and node creating method). In three different size areas, we randomly created five to eighty nodes. And then we implemented GreenLink, BlueHRT, and SHAPER, each experiment repeated three times to get average count (using Floyd algorithm to calculate average hop count) shown in Figure6.Figure 6
Average hop count.
(a)
15 ∗ 15 m, without connection number limit (b)
20 ∗ 20 m, without connection number limit (c)
25 ∗ 25 m, without connection number limit (d)
15 ∗ 15 m, limit of connection number is 7 (e)
20 ∗ 20 m, limit of connection number is 7 (f)
25 ∗ 25 m, limit of connection number is 7As shown in Figure6(a), in the experiment process of changing the total number of nodes from five to eighty, the average hop count of GreenLink is almost equal to 2. Meanwhile, the average hop count of SHAPER reaches 9 because of the random connection mechanism. However the average hop count of BlueHRT is much less than SHAPER because of its ring topology in the high density area. Then we reduced the node density by expanding the experiment area. We find that the average hop count of GreenLink increases slowly and is up to 3. That means that the height of the spanning tree is about 2. While in the SHAPER spanning tree the average hop count increases to about 10, which is 3 times than GreenLink and 1.6 times than BlueHRT will increase more communication overhead and energy consumption.On the other hand, if we consider the limitation of connection number, the results show that the average hop count of SHAPER remains stable. But the average hop count of GreenLink has been significantly increased and the maximum value reached 5 with 66% growth rate. However, the maximum average hop count still is only 55% of SHAPER. That means that, with limitation of connection number, GreenLink can reduce about half of system communication overhead by comparing with the traditional formation. This not only decreases energy consumption, but also has a remarkable improvement on communication efficiency.In summary, the average hop count of GreenLink has increased obviously with limitation of connection number. However, compared with the traditional scatternet formation algorithm, GreenLink can significantly reduce the average hop count, which is important to the system energy consumption and communication overhead.


### 3.3. System Energy Consumption

In this experiment, we chose twelve Bluetooth 4.1 chipsets of Nordic nRF51822 and tested the energy consumption on real situation. We placed and connected these twelve chipsets as Figure7(a). Because nRF51822’s upper bound on connection number is three (nRF51822 chipset could connect with two child nodes and one parent node at same time), the real convergence degree is unable to reach the level of that in simulation environment. Meanwhile, we recorded all topological structures, the number of central nodes, and the number of peripheral nodes in different situations. Then we counted the number of central nodes and peripheral nodes. Combining the data in experiments above, we estimated the energy consumption of GreenLink and SHAPER in different situations, as shown in Figures 7(c) and 7(f).Figure 7
System energy consumption experiment.
(a)
SHAPER formation (b)
SHAPER topology (c)
Not limit connected node number (d)
GreenLink formation (e)
GreenLink topology (f)
Limit connected node numberBecause the working voltage of chipset was stable and consistent, we displayed the working current of nodes to represent the system energy consumption. The results showed that, in the situation of certain location and connection for each chipset, the formation of SHAPER, which is shown in Figure7(b), has up to nine central nodes, occupying 75% of the total nodes. While in the same situation, GreenLink has only six central nodes, which is shown in Figure 7(e). That means we have got a topology with minimum number of central nodes. According to the real working current for each chipset, the system working current of SHAPER and GreenLink are 67.512mA and 48.530mA. This result shows the working energy consumption of GreenLink is only 71.88% of that of SHAPER in the situation where there are few nodes and severe limitation on connection number.Meanwhile, by combining the data in the first two groups of experiments, we respectively counted the number of central nodes and peripheral nodes of GreenLink and SHAPER. By combining the average energy consumption of central node and peripheral node measured in Section II, we calculated the energy consumption ratio of GreenLink and SHAPER, shown in Figures7(c) and 7(f). In situations with different node density, GreenLink will enhance the performance by increasing the total number of nodes. In the Experiment C, without limitation of connection number, in the worst situation where there are five nodes randomly distributed in the space of 25m∗ 25m, the energy consumption is 90% of SHAPER. In this situation, the low node density where every 125 square meters have only one node makes it difficult to converge well. While in the best situation, the energy consumption is 23% of SHAPER. Enough nodes and without limitation of connection node number are the key to converge well. In most situations, the average energy consumption of GreenLink is 35% of SHAPER. On the other hand, if we consider the limitation of connection number, the energy consumption of GreenLink is 45% of SHAPER in the best situation. And in most situations, the average energy consumption of GreenLink is 50% of SHAPER.In summary, GreenLink has a significant optimization effect on system energy consumption. Without limitation on the connection number, it can save 65% system energy of traditional formation technology and can save 50% system energy in the situations with limitation.


### 3.4. System Performance

The core idea of GreenLink is to reduce the system energy consumption by decreasing the number of central nodes in the network, which requires the remaining central nodes in the network to connect more peripheral nodes. Such network formation technology can directly influence the network as a whole. More traffic will converge on the minor peripheral nodes, analyzing and forwarding the data packet will make the central node more likely to block the performance through the network. Also, it will pose some problem on single node invalidation due to the increasing loss in battery life.In terms of the extra energy consumption of the central nodes due to the increase in number of links and traffic, it indicates a very tiny increase judging by the data from Tables2 and 3. It will not cause single node invalidation because of loss in capacity of the central nodes. On the other hand, we conducted the following experiment on Nordic nRF51822 and tested that whether there is a remarkable influence on the performance of BLE network due to the decrease in number of central nodes.The key point of this experiment is to form a BLE network with Nordic chipsets given the condition of two different topologies with the same number of peripheral nodes and different number of central nodes. In the experiment, we recorded the average packet loss percentage of the network on the basis of sending same amount of data packets with different transmitting velocity. Through this experiment, we can compute the level of impact caused by the decrease in number of central nodes.To begin with, the topology A which represents GreenLink is shown in Figure8(a). There is only one central node connecting four peripheral nodes. In the network, node 1 and node 3 will send the one thousand data packets to the other three nodes at the same time. We record its packet loss percentage with different transmitting velocity. The result is displayed in Figure 8(c). We can conclude that, under the circumstances when the transmitting velocity is relatively low, the overall packet loss percentage slowly increases as the velocity increases. As for the central nodes 5, the total sending velocity increases by 64 times from 0.065KB/s to 2.08KB/s with the packet loss percentage increasing by 3 times from 1.5% to 5.92%. The total transmitting velocity reaches 2.66KB/s, when the amount of inputting velocity exceeds the speed for analyzing and forwarding, the throughout rate arrives its limit, and plenty of data packets start to get lost. With the transmitting velocity increasing, the packet loss percentage increases rapidly and tends to reach 100%.Figure 8
Experiment of system performance.
(a)
Topology A (b)
Topology B (c)
Packet loss rateThe topology of SHAPER is shown in Figure8(b). Different from topology A, the number of its central nodes increases from one to three, leaving other settings the same. It has four peripheral nodes, the same as topology A does. Starting from peripheral nodes 1 and 3, each of the nodes will send one thousand data packets to the other three nodes. We obtained its packet loss percentage under the circumstances of different sending velocity. The result is shown in Figure 8(c). The tendency of SHAPER’s curve is similar to that of topology A. Under the condition of low sending velocity, packet loss percentage remains stable and slowly increases. When the velocity reaches 3.08 KB/s, in which the amount of inputting velocity exceeds the speed for analyzing and forwarding, the throughout rate arrives its limit and plenty of data packets start to get lost. With the transmitting velocity increasing, the packet loss percentage increases rapidly and tends to reach 100%.After comparing the two curves, we conclude that topology A which represents GreenLink is not as good as topology B in network performance because it has less central nodes. The maximum throughout rate of topology A reaches 2.66KB/s and, for topology B, the number reaches 3.08KB/s. The throughout rate of topology B is 15.79% greater than that of topology A because of the traffic distribution of the additional two nodes. Concerning the moment when reaching maximum throughout rate, the packet loss percentage of topology B is only 59% of that of topology A.According to our experiment, we find out that the decrease in number of central nodes actually affects the performance of the network for GreenLink. However, in terms of Nordic nRF51822, under the condition of connection between the central and peripheral nodes, the maximum speed for uplink and downlink is only 2.66KB/s, so its transmitting capacity is limited. On the other hand, BLE devices are currently deployed on the hardware which is poor in computing capability. Those devices only require to transmission status and instruction information which is only as larger as several bytes. Therefore, compare with the transmitting capability, standby time and energy consumption of the BLE devices should be paid more attentions. We believe that topology A representing the GreenLink will meet more demands in the real life application.


## 3.1. Number of Central Nodes

In this group of experiments, we used GreenPlatform and conducted six experiments divided into two groups depending on whether there was a limit of connection number or not. If there was an upper limit of connection number for Bluetooth nodes, we set it to seven in which there were six connections for their children nodes and one connection for their parent nodes. We also set the communication distance to 10m for Bluetooth nodes and randomly created five to eighty Bluetooth nodes in three different size areas (15∗15m, 20∗20m, and 25∗25m). In the conditions mentioned above, we implemented GreenLink, SHAPER, and BlueHRT. Each experiment was repeated three times to get the average data of central nodes number shown in Figure 4.Figure 4
Number of central nodes.
(a)
15 ∗ 15 m, without connection number limit (b)
20 ∗ 20 m, without connection number limit (c)
25 ∗ 25 m, without connection number limit (d)
15 ∗ 15 m, limit of connection number is 7 (e)
20 ∗ 20 m, limit of connection number is 7 (f)
25 ∗ 25 m, limit of connection number is 7Figure 5
Nordic nRF51822 chipsets used in our experiments.According to the experiments, without limitation of connection number, GreenLink could achieve a high convergence degree scatternet; nearly every node within scope of communication connected to the same parent node. As shown in Figure4(a), in the experiment process of changing the total number of nodes from five to eighty, the number central nodes is almost equal to one. By contrast, the central nodes number of SHAPER and BlueHRT rises quickly with the nodes size increasing and reaches forty-five at most for SHAPER and forty-nine for BlueHRT, which is more than 50% of the scale of all nodes. That is because of random connection mechanism of SHAPER and the ring topology in the high density area of BlueHRT.In the 20∗20m area, the space expended about 1.8 times, node density decreased, and the central nodes number of GreenLink begins to rise slowly and is up to 4 times with changing the total number of nodes from five to eighty. However, the central nodes number is still only 1/8 of SHAPER’s and 1/9 of BlueHRTs.Then we set a limitation of connection number to seven. As shown in Figures4(d), 4(e), and 4(f), the number of the central nodes of SHAPER and BlueHRT hardly changes compared with all the group of experiments mentioned above. That is because one BLE node can hardly reach its maximum number of connections with random link selection with SHAPER and central nodes of BlueHRT is mainly related to node density and distribution location. On the other hand, the central nodes number of GreenLink has an obvious increase than the situation in experiments above because of the limitation of connection number. In the three different nodes density, the central nodes number of GreenLink rises from 1 to around 20 and is about 1/2 to 1/3 of SHAPER and BlueHRT.In conclusion, the reduction of central nodes number using GreenLink has an obvious difference in performance depending on whether there is a limitation of connection number or not. However, compared with traditional scatternet formation technology, there is a significant improvement for reducing central nodes number using GreenLink which can decrease about 70% central nodes in a scatternet.


## 3.2. Average Hop Count

In this group of experiments, we based it on the same settings as experiments above (connection number of node, nodes density, and node creating method). In three different size areas, we randomly created five to eighty nodes. And then we implemented GreenLink, BlueHRT, and SHAPER, each experiment repeated three times to get average count (using Floyd algorithm to calculate average hop count) shown in Figure6.Figure 6
Average hop count.
(a)
15 ∗ 15 m, without connection number limit (b)
20 ∗ 20 m, without connection number limit (c)
25 ∗ 25 m, without connection number limit (d)
15 ∗ 15 m, limit of connection number is 7 (e)
20 ∗ 20 m, limit of connection number is 7 (f)
25 ∗ 25 m, limit of connection number is 7As shown in Figure6(a), in the experiment process of changing the total number of nodes from five to eighty, the average hop count of GreenLink is almost equal to 2. Meanwhile, the average hop count of SHAPER reaches 9 because of the random connection mechanism. However the average hop count of BlueHRT is much less than SHAPER because of its ring topology in the high density area. Then we reduced the node density by expanding the experiment area. We find that the average hop count of GreenLink increases slowly and is up to 3. That means that the height of the spanning tree is about 2. While in the SHAPER spanning tree the average hop count increases to about 10, which is 3 times than GreenLink and 1.6 times than BlueHRT will increase more communication overhead and energy consumption.On the other hand, if we consider the limitation of connection number, the results show that the average hop count of SHAPER remains stable. But the average hop count of GreenLink has been significantly increased and the maximum value reached 5 with 66% growth rate. However, the maximum average hop count still is only 55% of SHAPER. That means that, with limitation of connection number, GreenLink can reduce about half of system communication overhead by comparing with the traditional formation. This not only decreases energy consumption, but also has a remarkable improvement on communication efficiency.In summary, the average hop count of GreenLink has increased obviously with limitation of connection number. However, compared with the traditional scatternet formation algorithm, GreenLink can significantly reduce the average hop count, which is important to the system energy consumption and communication overhead.


## 3.3. System Energy Consumption

In this experiment, we chose twelve Bluetooth 4.1 chipsets of Nordic nRF51822 and tested the energy consumption on real situation. We placed and connected these twelve chipsets as Figure7(a). Because nRF51822’s upper bound on connection number is three (nRF51822 chipset could connect with two child nodes and one parent node at same time), the real convergence degree is unable to reach the level of that in simulation environment. Meanwhile, we recorded all topological structures, the number of central nodes, and the number of peripheral nodes in different situations. Then we counted the number of central nodes and peripheral nodes. Combining the data in experiments above, we estimated the energy consumption of GreenLink and SHAPER in different situations, as shown in Figures 7(c) and 7(f).Figure 7
System energy consumption experiment.
(a)
SHAPER formation (b)
SHAPER topology (c)
Not limit connected node number (d)
GreenLink formation (e)
GreenLink topology (f)
Limit connected node numberBecause the working voltage of chipset was stable and consistent, we displayed the working current of nodes to represent the system energy consumption. The results showed that, in the situation of certain location and connection for each chipset, the formation of SHAPER, which is shown in Figure7(b), has up to nine central nodes, occupying 75% of the total nodes. While in the same situation, GreenLink has only six central nodes, which is shown in Figure 7(e). That means we have got a topology with minimum number of central nodes. According to the real working current for each chipset, the system working current of SHAPER and GreenLink are 67.512mA and 48.530mA. This result shows the working energy consumption of GreenLink is only 71.88% of that of SHAPER in the situation where there are few nodes and severe limitation on connection number.Meanwhile, by combining the data in the first two groups of experiments, we respectively counted the number of central nodes and peripheral nodes of GreenLink and SHAPER. By combining the average energy consumption of central node and peripheral node measured in Section II, we calculated the energy consumption ratio of GreenLink and SHAPER, shown in Figures7(c) and 7(f). In situations with different node density, GreenLink will enhance the performance by increasing the total number of nodes. In the Experiment C, without limitation of connection number, in the worst situation where there are five nodes randomly distributed in the space of 25m∗ 25m, the energy consumption is 90% of SHAPER. In this situation, the low node density where every 125 square meters have only one node makes it difficult to converge well. While in the best situation, the energy consumption is 23% of SHAPER. Enough nodes and without limitation of connection node number are the key to converge well. In most situations, the average energy consumption of GreenLink is 35% of SHAPER. On the other hand, if we consider the limitation of connection number, the energy consumption of GreenLink is 45% of SHAPER in the best situation. And in most situations, the average energy consumption of GreenLink is 50% of SHAPER.In summary, GreenLink has a significant optimization effect on system energy consumption. Without limitation on the connection number, it can save 65% system energy of traditional formation technology and can save 50% system energy in the situations with limitation.


## 3.4. System Performance

The core idea of GreenLink is to reduce the system energy consumption by decreasing the number of central nodes in the network, which requires the remaining central nodes in the network to connect more peripheral nodes. Such network formation technology can directly influence the network as a whole. More traffic will converge on the minor peripheral nodes, analyzing and forwarding the data packet will make the central node more likely to block the performance through the network. Also, it will pose some problem on single node invalidation due to the increasing loss in battery life.In terms of the extra energy consumption of the central nodes due to the increase in number of links and traffic, it indicates a very tiny increase judging by the data from Tables2 and 3. It will not cause single node invalidation because of loss in capacity of the central nodes. On the other hand, we conducted the following experiment on Nordic nRF51822 and tested that whether there is a remarkable influence on the performance of BLE network due to the decrease in number of central nodes.The key point of this experiment is to form a BLE network with Nordic chipsets given the condition of two different topologies with the same number of peripheral nodes and different number of central nodes. In the experiment, we recorded the average packet loss percentage of the network on the basis of sending same amount of data packets with different transmitting velocity. Through this experiment, we can compute the level of impact caused by the decrease in number of central nodes.To begin with, the topology A which represents GreenLink is shown in Figure8(a). There is only one central node connecting four peripheral nodes. In the network, node 1 and node 3 will send the one thousand data packets to the other three nodes at the same time. We record its packet loss percentage with different transmitting velocity. The result is displayed in Figure 8(c). We can conclude that, under the circumstances when the transmitting velocity is relatively low, the overall packet loss percentage slowly increases as the velocity increases. As for the central nodes 5, the total sending velocity increases by 64 times from 0.065KB/s to 2.08KB/s with the packet loss percentage increasing by 3 times from 1.5% to 5.92%. The total transmitting velocity reaches 2.66KB/s, when the amount of inputting velocity exceeds the speed for analyzing and forwarding, the throughout rate arrives its limit, and plenty of data packets start to get lost. With the transmitting velocity increasing, the packet loss percentage increases rapidly and tends to reach 100%.Figure 8
Experiment of system performance.
(a)
Topology A (b)
Topology B (c)
Packet loss rateThe topology of SHAPER is shown in Figure8(b). Different from topology A, the number of its central nodes increases from one to three, leaving other settings the same. It has four peripheral nodes, the same as topology A does. Starting from peripheral nodes 1 and 3, each of the nodes will send one thousand data packets to the other three nodes. We obtained its packet loss percentage under the circumstances of different sending velocity. The result is shown in Figure 8(c). The tendency of SHAPER’s curve is similar to that of topology A. Under the condition of low sending velocity, packet loss percentage remains stable and slowly increases. When the velocity reaches 3.08 KB/s, in which the amount of inputting velocity exceeds the speed for analyzing and forwarding, the throughout rate arrives its limit and plenty of data packets start to get lost. With the transmitting velocity increasing, the packet loss percentage increases rapidly and tends to reach 100%.After comparing the two curves, we conclude that topology A which represents GreenLink is not as good as topology B in network performance because it has less central nodes. The maximum throughout rate of topology A reaches 2.66KB/s and, for topology B, the number reaches 3.08KB/s. The throughout rate of topology B is 15.79% greater than that of topology A because of the traffic distribution of the additional two nodes. Concerning the moment when reaching maximum throughout rate, the packet loss percentage of topology B is only 59% of that of topology A.According to our experiment, we find out that the decrease in number of central nodes actually affects the performance of the network for GreenLink. However, in terms of Nordic nRF51822, under the condition of connection between the central and peripheral nodes, the maximum speed for uplink and downlink is only 2.66KB/s, so its transmitting capacity is limited. On the other hand, BLE devices are currently deployed on the hardware which is poor in computing capability. Those devices only require to transmission status and instruction information which is only as larger as several bytes. Therefore, compare with the transmitting capability, standby time and energy consumption of the BLE devices should be paid more attentions. We believe that topology A representing the GreenLink will meet more demands in the real life application.


## 4. Discussion

In order to reduce the complexity of forming network and reduce the network’s energy consumption, each node in GreenLink attempts to connect other nodes for a limited number of times. At the same time, the BLE nodes do not know the global information. That results in a few cases that form more than one tree. In these cases, each root node cannot find any node in other trees, but some nonroot nodes can. However, these nonroot nodes have linked with parent node and cannot connect to new parent node. In the end, GreenLink cannot find a scatternet which can link all BLE nodes.To know the probability of the unsatisfactory cases appeared, we design an experiment based on our simulation environment. We generate 500 groups of nodes in different node densities and record the times of the unsatisfactory cases which GreenLink cannot form a scatternet cover all nodes in. The experiment results are shown in Figure9.Figure 9
Average error rate of GreenLink.There are two strategies to solve this problem. One is to use the nodes which can link two sink nodes as an edge node, called Slave/Slave node which can be a relay node between two trees. However, Slave/Slave BLE nodes are difficult to achieve on BLE chips for the limitations of BLE protocol. The other one is to change the nodes’ state in scatternet tree when two nodes in different trees find each other. This mechanism needs each node to record an ID of the tree, having to update all nodes’ tree ID when two trees link together. These things will always change the topology of network and lead to high energy consumption. As shown in Figure9, the probability that GreenLink cannot form a scatternet link all nodes tend to zero when there are more than one BLE node per 10m2. The node density is always larger than one node per 10m2 in actual scenario, especially in smart home scenario. So, it is not worth using a high energy consumption mechanism for rare events.


## 5. Related Work

With the rapid development and wide use of BLE devices, Bluetooth, as the short distance communication technology, has attracted more attention. For example, the researches about communication between smart toys by Bluetooth devices [6], the application of bluetooth technology in smart home [7] and indoor localization by Bluetooth devices [8]. However, any Bluetooth connection before version 4.0 lies within a piconet of up to eight nodes, and the ability of any two Bluetooth nodes can communicate with each other needs a scatternet formation technology.Scatternet is a group of piconets which combined via bridge nodes. Research on scatternet formation has been studied and careful surveys of the results exist [9] before Bluetootch version4.0. Generally speaking, most algorithms can be classified as mesh-based or tree-structure. A mesh allows multiple path between nodes [2, 10–12], which will increase not only the robustness of system, but also the complexity and energy consumption. A tree-structure scatternet formation will be more appropriate for BLE devices in energy sensitive application scenarios, such as TSF [13], Bluetrees [3], SHAPER [4], and BTCP [14]. Take TSF as an example; TSF is a simple and effective way to format a tree-structure scatternet. Trees combined via their root nodes only using TSF, and it is assumed that each node is in the communication range of each other. Bluetrees is also based on that assumption and initiated a series of algorithms that used the same approach or slightly modified [15, 16]. However, for a BLE system, this class of devices can only communicate with each other at a short range due to power and battery constraints. Later, scatternet formation algorithms focus on more realistic multihop networks in which all Bluetooth nodes are not required to be within communication range of each other. Most multihop protocols include a neighbor discovery phase to have better control over the scatternet topology [17, 18].SHAPER [4] is a distributed scatternet formation technology which can span a tree-structure topology compatible with a limited communication range. And Methfessel et al. introduced a modification of SHAPER that overcomes some practical issues in the implementation of SHAPER [19]. Sharafeddine S et al. propose a method a new scatternet formation protocol called BlueHRT (Bluetooth Hybrid Ring Tree) [20]. BlueHRT creates a hybrid ring tree topology which is with ring based piconets in the dense area and tree based piconets in the surrounding lightly loaded areas.Unfortunately previous work on Bluetooth scatternet formation is not applicable to BLE version 4.1. There are many changes in BLE version 4.1. For example, the procedures for formatting a traditional piconet are totally different from forming a BLE piconet, and there is no limitation on maximum number of slaves to a piconet master in BLE version 4.1. In 2017, Bluetooth Special Interest Group proposed Bluetootch Mesh which is a new bluetooth networking technology and is based on Bluetooth Core v4.0 or higher version [21]. Bluetooth mesh network is based on a flooding communication model which means the package in the mesh network can be forwarded by multiple relay nodes. On the one hand, flooding communication model may be helpful for improving network transmission bandwidth and robustness. On the other hand, the BLE devices are very sensitive to energy efficiency because of power and battery constraints, such as wearable devices and other IOT devices. Therefore the energy efficiency can be an essential issue in scatternet formation technology of BLE 4.1 or higher version.Energy consumption and transmission delay are always hot research topic in bluetooth and ad hoc networking technologies [17, 22–27].Pamuk and Karasan earlier proposed a distributed tree-based energy efficient scatternet formation algorithm: SF-DeviL [17], which increases the scatternet lifetime by shortening communication links and assigning more energy-capable devices to be masters. However, it does not control the network diameter and incurs a high formation delay. Y. Zhou and M. Medidi proposed an energy-aware scatternet formation algorithm: EMTS [23]; EMTS balances devices energy consumption by assigning roles to devices that suit their workload and energy resources and efficiently form the scatternets with short links and small network diameter to reduce energy consumption.Xihua Dong et al. analyse the delay in wireless Ad-Hoc net-works and try to make a reliable delay tradeoff [28]. Because most of the BLE devices have a tiny battery capacity, how to reduce energy consumption has become the bottleneck of development of smart wearable devices. Yunfei Shang et al. focus on how to reduce energy consumption in Wi-Fi environment [29]. Silvia Boiardi et al. try to manage energy consumption in wireless networks [30], Ferran Adelantado et al. try to reduce sensing overhead by user selecting [31], Ali Dabirmoghaddam et al. try to show how spatial correlation in data can be exploited to reduce energy consumption in a wireless sensor network [32], Brandon Heller et al. proposed a spanning tree named Elastic Tree to try to reduce energy consumption [33], and Jia Liu et al. have analysed the energy of neighbor discovery in Bluetooth Low Energy Networks [34]. However, there still needs to be a scatternet formation focusing on reducing system energy consumption.


## 6. Conclusion

The rapid development of wearable devices provides a good foundation and many usage scenarios for BLE and its scatternet formation technology. However, energy efficiency is the essential issue which needs to be significantly improved for the existing scatternet formation technology before they can be used. In this paper, we propose a novel BLE scatternet formation technology which focuses on energy efficiency called GreenLink which is the first one that can be deployed in the BLE version 4.1 or higher version devices.GreenLink reduces the amount of central nodes in a scatternet to ensure excellent energy efficiency because of the main source of system energy consumption comes from central nodes. For another aspect, by reducing the number of central nodes, average path length of any two nodes in the networks will be reduced, so that the reduction of system transmitting overhead will cause the lower energy consumption. We implemented the prototype GreenLink on the Nordic nRF51822 chips. According to the experiment, we compared GreenLink and SHAPER from the following aspects: the number of central nodes, the average hop count, networking speed, and the energy efficiency of the system. The experimental results show that GreenLink reduces about 70% number of central nodes and is 50% of SHAPER’s system energy consumption.



---

*Source: 1836198-2018-11-19.xml*