Modeling the connectivity of Data-Channel-based Bluetooth Low Energy mesh networks

1089-7798 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LCOMM.2018.2864994, IEEE Communications Letters IEEE COMMUNICATIONS LETTERS, VOL. XX, NO. YY, MONTH 2018 1 Modeling the Connectivity of Data-Channel-Based Bluetooth Low Energy Mesh Networks Seyed Mahdi Darroudi, Carles Gomez Abstract—Bluetooth Low Energy (BLE) has become one of the most popular low-power wireless technologies. While BLE was originally designed for star topology networks only, recent developments have focused on enabling mesh network topology support for BLE. An emerging category of BLE mesh network initiatives is based on routing data units over BLE data channels. This paper investigates fundamental connectivity parameters of Data-Channel-based BLE Mesh Networks (DC-BMNs), such as the probability of no isolation of a node and network Kconnectivity. We provide an analytical model for both parameters, which is validated by means of extensive simulations. Index Terms—Bluetooth Low Energy mesh network, connectivity, isolated node, K-connected network. I. INTRODUCTION IN recent years, Bluetooth Low Energy (BLE) has gained high momentum as a major low-power wireless technology. BLE was first specified in Bluetooth 4.0, whereby BLE networks follow the star topology [1]. However, this approach suffers significant range limitations, which may become a market disadvantage for BLE technology. For example, home automation solutions typically support mesh topologies [2]. In order to overcome this problem, many BLE mesh network solutions have been proposed [3]. A subset of these are based on flooding over BLE advertising channels [4], [5]. Nevertheless, more elaborate solutions route data units via link connections over BLE data channels [6], [7]. This second type of BLE mesh networks, which we refer to as Data-Channel-based BLE Mesh Networks (DC-BMNs), leverages the flexibility introduced by Bluetooth 4.1, which allows any BLE node to participate in multiple simultaneous link connections [8]. Remarkably, the IETF 6Lo working group is standardizing solutions for IPv6 over DC-BMNs [9]. While BLE mesh networks are emerging, their characteristics have only been explored to a very limited extent. For the first time to our best knowledge, this paper provides an analytical model and a study of two crucial connectivity properties of DC-BMNs: the probability of a node being not isolated, and network K-connectivity [10]. The model, which is validated by simulation, relates the aforementioned connectivity properties with the scenario area, the number of nodes, their coverage area, and the number of timeslots (i.e. a fundamental DC-BMN parameter, denoted NSlot). The main novelty of the model lies in capturing the impact of NSlot on This work was supported in part by the ERDF and the Spanish Government through project TEC2016–79988–P, AEI/FEDER, UE. S.M Darroudi and C. Gomez are with the Dept. of Network Engineering, Universitat Polit` ecnica de Catalunya (e-mail: sm.darroudi, car- [email protected]) the two considered connectivity properties (see Section III). In fact, the NSlot setting controls a crucial trade-off between link capacity and connectivity in DC-BMNs. NSlot can thus be tuned for the specific features and requirements of a given DC-BMN. Therefore, the model will be a useful tool for the planning and evaluation of DC-BMNs. II. DATA CHANNEL-BASED BLE MESH NETWORKS BLE defines a complete protocol architecture [11]. Only the lowest two BLE protocol layers, that is, the Physical Layer, and the Link Layer, are relevant for the scope of this paper. The Physical Layer offers 40 Radio Frequency (RF) channels in the 2.4 GHz band. These comprise 3 advertising channels and 37 data channels. The former are used for broadcasting purposes, whereas the latter allow bidirectional communication between two devices that have established a Link Layer connection. In Bluetooth 4.0, BLE networks follow the star topology. In this paradigm, a device in the master role (a master) participates in several parallel Link Layer connections with devices in the slave role (slaves). The master establishes a Time Division Multiple Access (TDMA) schedule, with a TDMA interval called connInterval. A slave is not allowed to be connected to more than one master at the same time. However, in Bluetooth 4.1 and subsequent Bluetooth specifications, a device can run multiple Link Layer instances simultaneously, regardless of its Link Layer role in each one of them. Therefore, a slave may be connected to several masters simultaneously, or a device can be a slave in a subset of connections and a master in the rest. These features allow the formation of extended BLE network topologies, such as the mesh topology. In this paper, we focus on DC-BMNs, where data units are routed over Link Layer connections. Given the TDMA basis of BLE Link Layer connections, in DC-BMNs every node has a timeslot for communication with each one of its connected neighbors. The number of connected neighbors per node ranges between 1 and a maximum value that we denote by NSlot. Note that NSlot is also the maximum number of slots used in each TDMA interval, connInterval. Fig. 1 depicts an example DC-BMN, and a TDMA schedule for that network, for NSlot = 5. To allow the formation of a multihop topology, NSlot needs to be at least 2. On the other hand, NSlot is upper bounded by the maximum number of slots that fit in a connInterval period. Assuming a slot duration of 676 µs, which comprises one request/response exchange, the NSlot upper bound is 11 and 5917 for connInterval of 7.5 ms and 4000 ms, respectively [11]. The setting of NSlot 1089-7798 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LCOMM.2018.2864994, IEEE Communications Letters IEEE COMMUNICATIONS LETTERS, VOL. XX, NO. YY, MONTH 2018 2 Fig. 1. A DC-BMN topology and a possible TDMA schedule. M or S denote the master or slave role of a node in the corresponding link, respectively. Fig. 2. DC-BMN link capacity, for a maximum BLE capacity of 236.7 kbit/s [11]. Link capacity for NSlot = 1 is not illustrated since NSlot >1in DC-BMNs. is critical for performance. While the amount of resources for communication with each specific neighbor is inversely proportional to NSlot (see Fig. 2), this parameter defines the number of connected neighbors a node can have, and thus endto-end connectivity increases with NSlot (see Section IV). In order to enable network-wide consistent operation as shown in Fig. 1, a framework offering network formation, network maintenance, and time synchronization is needed [12]. Different framework approaches are possible. For example, one node may act as network root node, which is the first node to establish links with its neighbors. The root determines the timeslots to use with its neighbors, and acts as synchronization reference for them. The neighbors follow the same procedure with their own neighbors, and so on. A number of timeslots need to be reserved for advertising and joining, while link maintenance uses common BLE mechanisms. Similar approaches exist in the literature for DC-BMNs [3], [7], or for other technologies, such as the IEEE 802.15.4 Time-Slotted Channel Hopping (TSCH) mode [13]. III. CONNECTIVITY ANALYSIS Connectivity is a fundamental property of any wireless mesh network. In this section, we provide an analytical model for two important connectivity-related parameters of DC-BMNs. The first one is the probability that a node can establish a link with at least one neighbor, and thus become non-isolated (i.e. probability of no isolation, denoted by PNI ). This parameter is crucial since an isolated node does not contribute to the network and cannot communicate with any other node. Note that two physical neighbors (i.e. nodes that are placed within the coverage range of each other) will only be able to establish a link if both of them have sufficient available timeslots. The second target parameter is the probability that a network is Kconnected, that is, the probability that any node in the network can communicate with any other node through Kmutually independent paths. This probability is denoted by PK−con. In other words, a mesh network is K-connected if any node can reach any other node even if any group of K-1 nodes are dropped from the network [14]. This property expresses robustness of a mesh network in the presence of node or link failures, which may be due to battery depletion, device malfunctioning, interference, etc. In order to determine PNI and PK−con, we assume that nodes follow a uniformly random spatial distribution over a two-dimensional area. The node spatial distribution assumed captures the characteristics of many real scenarios (e.g. smart homes), where nodes are not deployed under a predetermined, regular pattern. For more structured scenarios (e.g. grid topologies), we recommend using ad-hoc developed models. We use the following input parameters for our model: the area where nodes are distributed (denoted A), the total number of nodes in the network (denoted N), the coverage area of a node (denoted a), and NSlot. For the analysis, we assume that all network nodes are homogeneously configured with the same value for NSlot,connInterval, and timeslot duration. The next two subsections provide the analytical models for calculating PNI and PK−con, respectively. A. Probability of no isolation In order to determine PNI , we first calculate the probability that a node is placed in the coverage range of another node, denoted q, which can be obtained as q=a/A. Let dphy be the number of physical neighbors of a node. PNI can be determined as the probability that a node can connect with at least one of its physical neighbors (i.e. the node and at least one of its physical neighbors have an available timeslot for communication). PNI can be expressed as: PNI = N−1 X j=1 P(dphy =j)·P(conn|dphy =j)(1) where P(dphy =j)denotes the probability of a node having j physical neighbors, and P(conn|dphy =j)is the probability that the node is not isolated when the node has jphysical neighbors. These terms are calculated through (2) and (3). In the latter, nconn and niso denote the number of combinations in which a node with jphysical neighbors is connected, and isolated, respectively, and are obtained through (4) and (5). P(dphy =j) = N−1 j·qj·(1 −q)N−1−j(2) P(conn|dphy =j) = nconn nconn +niso (3) nconn = NSlot X h=1 j h·P(conn|dphy = 1)h(4) niso = (1 −P(conn|dphy = 1))j(5) P(conn|dphy = 1), that is, the probability of a node xbeing connected to its only physical neighbor y, can be computed 1089-7798 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LCOMM.2018.2864994, IEEE Communications Letters IEEE COMMUNICATIONS LETTERS, VOL. XX, NO. YY, MONTH 2018 3 by adding two different terms, Uand V(see (6)), because the calculation has to be done differently when yhas less than NSlot physical neighbors (see (7)) from when it has at least NSlot physical neighbors (see (8)), respectively. In the first case, there exist available timeslots for establishing Link Layer connections between node yand all its own physical neighbors. However, in the second case, ycan only establish Link Layer connections with up to NSlot of its physical neighbors. We assume that all neighbors have the same priority of becoming connected with a node. Then, P(conn|dphy = 1) can be obtained by using (6)-(9). P(conn|dphy = 1) = U+V(6) U= NSlot−1 X i=1 N−2 i·qj·(1 −q)N−2−i(7) V= N−2 X i=NSlot β(i)·N−2 i·qj·(1 −q)N−2−i(8) In (8), parameter β(i)denotes the probability that xcan establish a connection with y. We next describe how parameter β(i) is obtained. Assume that the number of physical neighbors of yis at least NSlot, and yhas NSlot free timeslots. There may be up to NSlot different opportunities for xto establish a connection with y. Each time a physical neighbor of yconnects to y, it reserves one of y’s free timeslots. However, other timeslots remain free, and xhas other chances to connect to y, except when NSlot nodes have connected with y. Let β(i)r denote the probability of establishing a connection between x and ywhen yhas rconnected neighbors, and thus NSlot −r timeslots are available for connecting with y. Then, β(i)can be approximated by using (9), where β(i)0= 0. Finally, PNI can be obtained by plugging (2)-(9) into (1). β(i) = NSlot X r=1 (1 −β(i)r−1)·(NSlot −r−1) (i−r)(9) B. Probability of K-connected network This section provides the analytical model for calculating the probability that a network is K-connected. Let ddenote the degree of a node, i.e. the number of simultaneous connections a node has with its corresponding neighbors (note that for a given node, d≥dphy). Let dmin be the minimum node degree among the nodes in the network. Based on a property of geometric random graphs [15], if the graph has a high number of nodes, the probability that a network is K-connected, PK−con, can be obtained by using (10). An assumption in (10) is absence of a limit on the number of neighbors for a node, whereas in DC-BMNs, a node may have a maximum of NSlot connected neighbors. However, the resulting model is accurate for practical NSlot values, i.e. the range of NSlot values that enable an almost 1-connected DC-BMN (see Section IV). PK−con =P(dmin ≥K)(10) Note that dmin ≥Krequires all nodes to have at least Kneighbors. On the other hand, the maximum number of connected neighbors a node can have is NSlot. Therefore, (10) can be developed as shown in (11). The term P(d=i)in (11) can be obtained through (12) and is further expanded in (13). P(dmin ≥K) = P(d≥K)N= NSlot X i=k P(d=i)!N (11) P(d=i) = N−1 X j=i P(dphy =j)·P(d=i|dphy =j)(12) where P(dphy =j)denotes the probability of a node having jphysical neighbors, which can be obtained as per (2), and P(d=i|dphy =j)is the probability that the node has i connected neighbors out of jphysical neighbors. Accordingly, the calculation of P(d=i)is carried out in (13), where P(d= 1) can be approximated by P(conn|dphy = 1), and it can be computed by using (6)-(9). P(d=i) = N−1 X j=iN−1 j·qj·(1 −q)N−1−j· j i·P(d= 1)i·(1 −P(d= 1))j−i (13) IV. EVALUATION In this section we evaluate, and validate by simulation, the analytical models presented in Section III. We use Matlab to simulate uniformly random node distributions, and obtain PNI and PK−con from them. Our simulation code is publicly available [16]. In the simulation, N= 100 nodes are distributed randomly in a square area of A=40000 m2. In order to address the border effect problem, we use the toroidal distance [10]. The simulation is executed for different values of NSlot and average node degree (NDeg). NDeg is the expected number of physical neighbors of a node, which is obtained as NDeg =q·N(thus, NDeg >0). For each specific value of NSlot and NDeg, 1000 different node distributions are generated. In each distribution, 100 sets of connections between neighboring nodes are randomly established. Thus, 100000 individual simulations have been run for each combination of NSlot and NDeg values. A. Probability of no isolation Fig. 3 plots PNI analytical and simulation results for NSlot = 2 and NSlot = 10, and for NDeg between 1 and 15. As shown in the figure, the analytical model is accurate. Differences between analytical and simulation results are due to the assumption that the neighbors of a node are independent. The differences tend to decrease as NSlot increases, since connectivity opportunities then also increase. Note that PNI depends on (6), which is obtained as U+V. Term Vuses β(i), which is calculated as an approximation in (9). As NSlot increases, overall influence of Vin (6) decreases, therefore accuracy of the model improves. As expected, PNI increases with NSlot and NDeg (with stronger impact of the latter). Greater values for both parameters lead to a greater amount of connectivity opportunities between a node and its possible neighbors. A node is almost surely connected to at least one neighbor for NSlot =10 and NDeg ≥6. However, a low NSlot 1089-7798 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LCOMM.2018.2864994, IEEE Communications Letters IEEE COMMUNICATIONS LETTERS, VOL. XX, NO. YY, MONTH 2018 4 Fig. 3. Probability of no isolation for different values of NDeg and NSlot Fig. 4. Probability of K-connectivity for NSlot = 10 setting does not allow to reach near-one PNI for the range of NDeg values considered. Results for NSlot greater than 10 have not been depicted since further PNI increase is negligible for such NSlot values. B. Probability of K-connected network Figs. 4 and 5 illustrate analytical and simulation Kconnectivity results, for NDeg between 1 and 15, and for NSlot values of 10 and 15. As expected, K-connectivity increases with NSlot, and NDeg. Achieving an almost-1connected network requires NDeg ≥10 (and thus, NSlot ≥10). NDeg ≥10 leads to an asymptotic 1-connectivity increase, while significant benefits in terms of 2or 3-connectivity are achieved. Fig. 6 depicts the K-connectivity model error, defined as the difference between simulation and analytical results. As shown in Fig. 6, the model is accurate for the range of scenarios considered, with a maximum error of 0.03. The main reasons for a non-zero error are two approximations made in the model for the sake of analytical tractability: i) calculating P(d=i|dphy =j)in (13) by assuming that the connected neighbors of a node are independent, and ii) the approximation of P(d= 1) by P(conn|dphy = 1) for (13). The model error absolute value decreases for low and high NDeg values, whereby connectivity opportunities are scarce and abundant, respectively, which reduces the impact of the approximations. The developed analytical model allows to plan or evaluate a DC-BMN. If three of the four input parameters of the model (i.e. A,N,a,NSlot) are known, it is possible to determine the fourth one for a given connectivity target. For example, assume a smart home with A= 100 m2,a= 60 m2, and NSlot = 10. In order to achieve 95% 1-, 2or 3-connectivity, NDeg needs to be at least 8, 10 or 14, respectively (Fig. 4). Thus, the number of nodes N needed for the deployment is at least 14, 17 or 24, respectively. For the same settings, N=12 yields a 1-, 2or 3-connectivity of 86%, 45% or 4%, respectively. Fig. 5. Probability of K-connectivity for NSlot = 15 Fig. 6. K-connectivity model error as a function of NDeg V. CONCLUSION We have presented and validated an analytical model that predicts the probability of no isolation and the K-connectivity of DC-BMNs. Our model uses the scenario area, number of nodes, nodes’ coverage range and NSlot as inputs. The model will be a useful tool for planning and evaluating DC-BMNs. REFERENCES [1] BluetoothSIG, “Bluetooth core specification, version 4.0,” Jun 2010. [2] C. Gomez and J. Paradells, “Wireless home automation networks: a survey of architectures and technologies,” IEEE Communications Magazine, vol. 48, Jun 2010. [3] S.-M. Darroudi and C. Gomez, “Bluetooth Low Energy mesh networks: A survey,” Sensors, vol. 17, p. 1467, Jul 2017. [4] H.-S. Kim et all, “BLEmesh: A wireless mesh network protocol for bluetooth low energy devices,” in FiCloud, 3rd, (Rome), 2015. [5] A. Gogic et all, “Performance analysis of Bluetooth Low Energy mesh routing algorithm in case of disaster prediction,” in ICWCMCN, 18th, (Vienna), 2015. [6] Z. Guo et all, “An on-demand scatternet formation and multi-hop routing protocol for BLE-based wireless sensor networks,” in WCNC, (USA), 2015. [7] K. Mikhaylov and J. Tervonen, “Multihop data transfer service for Bluetooth Low Energy,” in ITST, 13th, (Tampre), 2013. [8] BluetoothSIG, “Bluetooth core specification, version 4.1,” Dec 2013. [9] C. Gomez et all, “IPv6 over BLUETOOTH(R) Low Energy mesh networks (work in progress),” Mar 2018. [10] C. Bettstetter, “On the minimum node degree and connectivity of a wireless multihop network,” in MobiHoc, (Lausanne), Jun 2002. [11] C. Gomez et all, “Overview and evaluation of Bluetooth Low Energy: An emerging low-power wireless technology,” Sensors, vol. 12, p. 11734, Aug 2012. [12] Y. Murillo et all, “Bluetooth now or low energy: Should BLE mesh become a flooding or connection oriented network?,” in PIMRC, 18th, (Canada), Oct 2017. [13] M.-R. Palattella et all, “On optimal scheduling in duty-cycled industrial iot applications using ieee802.15.4e tsch,” IEEE Sensors Journal, vol. 13, p. 3655, 2013. [14] Q. Ling and Z. Tian, “Minimum node degree and k-connectivity of a wireless multihop network in bounded area,” in Globecom, 7th, (Washington), Nov 2007. [15] M. D. Penrose, “On k-connectivity for a geometric random graph,” Random Structures & Algorithms, vol. 15, Sep 1999. [16] S.-M. Darroudi and C. Gomez, “DC-BMN simulation code,” Available online: https://sites.google.com/view/blemesh/home, Jul 2018.