Accurate Analysis on Bluetooth Low Energy Neighbor Discovery

Ting-Chao Hou¹, Kuo-Chang Huang²

¹Department of Communications Engineering, National Chung Cheng University, Chiayi.
²Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi.

DOI: 10.4236/jcc.2020.812020                

Abstract

The basic concept of Bluetooth Low Energy (BLE) is short packet transmission and transient connection. It can quickly establish a connection, send data, and quickly disconnect, so that neighbor discovery is frequent and becomes an important issue. In the neighbor discovery which includes advertising and scanning, the BLE specification defines several important parameters. The parameters on the advertiser side include advertising interval, advertising duration, etc. On the scanner side, there are scan interval, scan window, etc. How to configure these parameters for quick neighbor discovery has been troublesome for BLE implementers. Prior analyses on BLE discovery process also showed some disagreements or made some incorrect assumptions. In this paper, we use rigorous probability-theory based derivations to obtain different kinds of successful discovery probabilities. We clarify disagreements in prior works and also provide insights on how to configure parameters for maximizing discovery probability. In particular, we prove that the discovery probabilities on each of the three channels are correlated. We also find that, when the advertising duration is set close to some multiples of the scan interval, an ill-fated synchronization problem will occur. To have a high discovery probability, both scan window and scan interval should be set at a large value, though it might not be good for energy saving.

Keywords

Bluetooth Low Energy, Advertising Interval, Advertising Duration, Advertising Event, Scan Interval, Scan Window, Neighbor Discovery, Ill-Fated Synchronization

1. Introduction

It has been nearly 30 years since the Bluetooth short range wireless communication technology was proposed in the early 1990s. Over the years, Bluetooth technology has progressed from solving the cabling issue between the host computer and its peripheral devices to being widely used in various communication applications for personal hand-held devices. Because Bluetooth has been used mostly in battery-powered devices, the Bluetooth SIG (Special Interest Group) issued the Bluetooth 4.0 specification in 2010 for low power operation of Bluetooth [1]. It has been generally referred to as BLE (Bluetooth Low Energy).

Many BLE applications are run between battery-powered portable devices. Before any kind of connections can be set up, a pair of BLE devices need to go through the neighbor discover process to know the existence of each other. BLE specifications allocate three (37, 38, 39) out of the 40 total channels for discovery. One device does the advertising on the three channels alternately and the other device does the scanning also on the three channels alternately. Since the two devices are not synchronous, they need to be in the matching roles (one advertising and the other scanning) and at the right time and the right place (on the same channel) for the discovery to be successful. If one round of advertising does not result in successful discovery, a random delay is introduced before the next round so that a different advertising/scanning matching is tried. This is different from the infrastructure-mode WiFi (Wireless Fidelity), where an always-on access point (AP) exists and serves as a reference point for other WiFi stations to scan and connect to. Several advertising/scanning parameters (e.g., advertising interval, advertising duration, scan interval, scan window) are involved in the BLE discovery process. BLE specifications do not mandate each parameter’s value but rather provide a range of possible values for each parameter so that different applications can choose their appropriate ones. However, this also causes headaches for BLE implementers as the dimension of parameter values is too large to handle. Many rely on trial and error. It is desirable to have some parameter-setting guidance so that an efficient BLE neighbor discovery process can be realized and the power consumption is minimized.

There have been quite a few studies on analyzing the performance of the BLE discovery process. The performance metrics include successful discovery probability, discovery latency, and power consumption. In [2] [3], a 1:1 (one advertiser and one scanner) scenario is considered. The discovery latency is analyzed but its accuracy deteriorates when the advertising interval is larger than the scan window in the discontinuous scanning scenario. In [4], the n:1 (n advertisers and one scanner) scenario is considered. The authors use the classical Aloha model to derive the discovery latency. An enhanced mechanism is also proposed enabling BLE scanner to learn the network condition and adjust parameters accordingly. However, the analysis is still limited to the continuous scanning scenario. In [5] [6], more general m:n scenarios are considered. The successful discovery probabilities on each of the three channels are first derived and then the discovery latency is calculated. The derived successful discovery probabilities on each of the three channels are different. The authors also assume that successful discovery on the three channels within an advertising event are independent probability events. These are somewhat against the intuition. In [7], a wait-slot scheme is proposed for the neighbor discovery process in the n:1 scenario so that the collisions of response packets can be reduced. In the analysis, the probabilities of successful advertising on each of the three channels are shown to be identical. In [8], the authors propose a method to determine an optimal value for the BLE advertising interval to minimize the time in which all surrounding BLE advertisers are discovered by a scanner. The analysis is limited to the continuous scanning scenario. In [9], an energy model of BLE is presented. It accounts for all BLE parameters and all operating modes. To be able to calculate the energy consumption in the discovery process, the discovery latency needs to be calculated first, which an algorithm based on Gaussian approximation for sum of random delays in the advertising events is used. The latency result is compared to that in [3] and significant discrepancy is obvious. Sudden latency jumps at some parameter settings are observed but no satisfactory explanations are given. In [10], different device discovery schemes in BLE networks are surveyed with their advantages and limitations discussed.

From the above literature survey, we identified several issues worthy of more careful investigation. First, there is disagreement on the successful discovery probabilities on individual channels within an advertising event (to be more thoroughly explained in the next section). Second, individual channel discoveries are assumed to occur independently. Third, there are some abrupt changes in discovery probability and discovery latency at certain parameter settings, which none of prior works can explain. There is still not much insight shed on proper setting of discovery parameters. In this paper, we address all the above and claim the following contributions:

1) We give a rigorous proof that the successful discovery probabilities on three individual channels within an advertising event are the same.

2) We show that successful discovery on an individual channel is dependent on the discovery result on the prior channel within the same advertising event.

3) We find the successful discovery probability for an advertising event (which includes discoveries on three individual channels) and show what discovery related parameter settings are to avoid. The rest of this paper is organized as follows: In Section 2, we give a short introduction on the BLE discovery operation. Section 3 first reviews certain prior analyses to get a feel about how they might go wrong, and then we use rigorous probability-theory based derivations to obtain different kinds of successful discovery probabilities. Section 4 shows verification of the analysis by simulations. Section 5 is the conclusion.

2. BLE Discovery

BLE minimizes the device power consumption by allowing devices to go into the sleep state. When devices attempt to communicate with each other, they wake up to discover each other. Three channels (channels 37, 38, and 39) are allocated for the discovery purpose. Consider the scenario of two BLE devices. One device enters the advertising state and periodically sends advertising PDUs (protocol data units; or simply called packets) on the three advertising channels. The other device enters the scanning state or the initiating state. It also takes turn scanning on the three advertising channels. There are 4 types of packets that the advertiser may send to start the discovery: ADV_SCAN_IND, ADV_DIRECT_IND, ADV_NONCONN_IND, andADV_IND. ADV_SCAN_IND is for scanning only. A device entering the scanning state (a scanner) can respond to it with a SCAN_REQ packet to request further information. The advertiser will then reply with a SCAN_RSP packet. ADV_DIRECT_IND is for fast connection setup. A device entering the initiating state (an initiator) can respond with CONNECT_REQ to quickly set up a connection with the advertiser. ADV_NONCONN_IND is for one-way advertising only. Subsequent scan or connect request is not allowed. ADV_IND is the general-purpose advertising packet. Scanner/initiator can reply with a scan/connect request. The discovery process between an advertiser and a scanner via ADV_SCAN_IND/ADV_IND - SCAN_REQ-SCAN_RSP exchange is the most lengthy one and is usually used as the example scenario for BLE discovery analysis. Our analysis in later sections also assumes this type of packet exchange. It can be easily modified to adapt to other types of advertising packet exchanges.

Figure 1 illustrates the timing sequence of advertising and scanning. An advertiser sends three identical ADV_IND packets sequentially over channels ch37, ch38, and ch39. This is called an advertising event (advEvent, in short). There is a fixed time gap between consecutive ADV_IND packets to allow for send/receive of corresponding SCAN_REQ and SCAN_RSP packets. We call it advertising duration (advDuration), specified to be no larger than 10 ms. Two adjacent advEvents are separated by a fixed advertising interval (advInterval) and a random advertising delay. advInterval can be chosen to be from 20 ms to 10.24 s, with increment in 0.625 ms. The random advertising delay is to decouple the possible correlation between advEvents from the same advertiser or from different advertisers. Without it, advertising/scanning channel mismatch or packet collisions may repeat over and over again. Random advertising delay is chosen uniformly from [0, 10 ms].

Figure 1. Advertising and scanning processes on three advertising channels.

A scanner listens on channels ch37, ch38, ch39 alternately for advertising packets. It switches scanning channels at every scan interval (scanInterval). In each scanInterval, it listens only for a duration of the scan window (scanWindow). The idle time in the scanInterval can save energy and reduce reply competitions among multiple scanners, if any. When an advertiser advertises and a scanner scans on the same channel, and the advertising packet is successfully received by the scanner, the scanner will reply with a SCAN_REQ. The advertiser then replies with a SCAN_RSP to complete the discovery process.

For later analysis, we need a reference to the duration of a complete discovery process. We use the ADV_IND - SCAN_REQ - SCAN_RSP exchange as an example. The maximum lengths of ADV_IND, SCAN_REQ,SCAN_RSP packets are 47, 22, 47 bytes, respectively. At the 1Mbps channel rate, their transmission times are 376, 176, 376 us, respectively. There is also a 150 us IFS (inter-frame space) between packet transmissions. Therefore, a complete discovery process for this example takes 0.376 + 0.150 + 0.176 + 0.150 + 0.376 = 1.228 ms.

3. Analyses on Successful Discovery

To facilitate comparisons with [5], we adopt most of the mathematical symbols used there. They are listed in Table 1. Our analysis is applicable to the one advertiser and one scanner (1:1) scenario only.

3.1. Review of Prior Works

Figure 2 shows the time sequence of a BLE device $A_1$ as an advertiser, and another BLE device $S_1$ being a scanner. In this example, ${\tau }_{SI}>{\tau }_{SW}$ (discontinuous scanning), and ${\tau }_{SI}>{\tau }_{WA}$. We notice that the arrival time of the first Ch37 ADV_IND packet falls within the Ch37 scanning window of device $S_1$, but the second Ch37 ADV_IND packet arrives when device $S_1$ is in the power-saving state. To simplify the discussion, we temporarily assume ${\tau }_{SW}={\tau }_{SI}$ (continuous scanning). Under the assumption, device $S_1$ is always doing scanning and never enters the power-saving state. ADV_IND packets always arrive at one of the three scanning windows (Figure 3).

Table 1. Symbols used in this paper for BLE discovery analysis.

Figure 2. Advertising and scanning in a discontinuous scanning scenario.

Figure 3. Advertising and scanning in a continuous scanning scenario ( ${\tau }_{SI}>{\tau }_{WA}$ ).

This is the scenario considered in Section 4.1.1 of [5]: 1:1 Network (one advertiser and one scanner. In [5], four events are defined. Among them, two are relevant to the successful discovery in a 1:1 Network.

$E_1$ : $S_1$ is synchronous with $A_1$, meaning a channel x (x = 37, 38, or 39) ADV_IND packet arrives when the scanner is also scanning channel x.

$E_4$ : $S_1$ has enough time to reply to ADV_IND before the current scan window ends.

In a 1:1 Network, the necessary and sufficient condition of a successful discovery is $E_1\cap E_4$. In continuous scanning, $\mathrm{Pr}\left[E_1\right]={\tau }_{SW}/3{\tau }_{SI}=1/3$ since we assume ${\tau }_{SW}={\tau }_{SI}$. For $E_4$ to occur, the remaining time in the scan window when the ADV_IND first arrives at the scanner must be greater than $T_S$, the time required for the ADV_IND packet to be successfully received by $S_1$ and the subsequent SCAN_REQ and SCAN_RSP exchanges between $A_1$ and $S_1$ to be completed. Let $t_0$ be the arrival time of channel 37 ADV_IND packet. Hence, $\mathrm{Pr}\left[E_4\right]=\mathrm{Pr}\left[{\tau }_{SW}-t_0>T_S\right]=\mathrm{Pr}\left[t_0<{\tau }_{SW}-T_S\right]=\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$. Therefore, the probability that a channel 37 discovery is successful is

${\alpha }_{\text{1}}=\mathrm{Pr}\left[E_1\cap E_4\right]=\mathrm{Pr}\left[E_1\right]\mathrm{Pr}\left[E_4\right]=1/3\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$ (1)

(because $E_1$ and $E_4$ are independent events), which is identical to Equation (1) in [5] and Equation (3) in [6].

Using the same argument that $E_1\cap E_4$ is what makes a successful discovery, the probability that the second (on channel 38) ADV_IND results in a successfully discovery is ${\alpha }_{\text{2}}=\mathrm{Pr}\left[E_1\cap E_4\right]=1/3\mathrm{Pr}\left[{\tau }_{SW}-t_0-{\tau }_{WA}>T_S\right]=1/3\mathrm{Pr}\left[t_0<{\tau }_{SW}-{\tau }_{WA}-T_S\right]$, or

${\alpha }_{\text{2}}=\left({\tau }_{SW}-{\tau }_{WA}-T_S\right)/3{\tau }_{SI}$, (2)

which is Equation (2) in [5] and Equation (4) in [6]. Similarly, the probability that the third (on channel 39) ADV_IND results in a successfully discovery is

$\begin{array}{c}{\alpha }_{\text{3}}=\mathrm{Pr}\left[E_1\cap E_4\right]=1/3\mathrm{Pr}\left[{\tau }_{SW}-t_0-2{\tau }_{WA}>T_S\right]\\ =1/3\mathrm{Pr}\left[t_0<{\tau }_{SW}-2{\tau }_{WA}-T_S\right]=\left({\tau }_{SW}-2{\tau }_{WA}-T_S\right)/3{\tau }_{SI}\end{array}$.

In the above discussion, we assume ${\tau }_{SI}>{\tau }_{WA}$. On the other hand, if we consider ${\tau }_{SI}<{\tau }_{WA}$, Figure 4 shows a possible scenario. ${\alpha }_{\text{1}}$ remains unchanged as $1/3\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$, but ${\alpha }_{\text{2}}=1/3\mathrm{Pr}\left[t_0+{\tau }_{WA}<{\tau }_{SI}+{\tau }_{SW}-T_S\right]=1/3\mathrm{Pr}\left[t_0<{\tau }_{SI}+{\tau }_{SW}-{\tau }_{WA}-T_S\right]$, or

${\alpha }_{\text{2}}=\left({\tau }_{SI}+{\tau }_{SW}-{\tau }_{WA}-T_S\right)/3{\tau }_{SI}$, (3)

which matches Equation (2) in [5] and Equation (4) in [6]. It however is different from Equation (2) above. In other words, [5] [6] showed that ${\alpha }_{\text{2}}$ and ${\alpha }_{\text{3}}$ not only are different from ${\alpha }_{\text{1}}$, but are also dependent on the relation between ${\tau }_{SI}$ and ${\tau }_{WA}$. On the other hand, [7] claimed that ${\alpha }_{\text{1}}$, ${\alpha }_{\text{2}}$, ${\alpha }_{\text{3}}$ are equal.

It is necessary to have some explanations as to why the single-channel successful discovery probability is dependent on the relation between ${\tau }_{SI}$ and ${\tau }_{WA}$, and also why there is disagreement between [7] and [5] [6]. There must be something wrong somewhere in the derivation of the successful discovery probabilities. We next show that successful discovery probabilities are independent of the relation between ${\tau }_{SI}$ and ${\tau }_{WA}$, and in fact the three probabilities ${\alpha }_{\text{1}}$, ${\alpha }_{\text{2}}$, ${\alpha }_{\text{3}}$ are equal.

Figure 4. Advertising and scanning in a continuous scanning scenario ( ${\tau }_{SI}<{\tau }_{WA}$ ).

3.2. Probability of a Successful Single-Channel Discovery

We first use a simple argument to explain why successful single-channel discovery probabilities ${\alpha }_{\text{1}}$, ${\alpha }_{\text{2}}$, ${\alpha }_{\text{3}}$ are equal. The conditions that the advertiser $A_1$ ’s Ch37 ADV_IND results in a successful discovery by the scanner $S_1$ are: 1) $A_1$ ’s Ch37 ADV_IND is successfully received by $S_1$ and 2) the subsequent exchange of SCAN_REQ and SCAN_RSP are also successful. We call the two conditions an event $E_{ch37}$ occurs. $E_{ch37}$ occurs when the arrival time ( $t_0$ ) of Ch37 ADV_IND falls within the Ch37 scan window but at least $T_S$ time before the scan window ends. Since the scan interval is periodically repeating at three times of the scan interval ( ${\tau }_{SI}$ ), it suffices to consider a scan cycle ${\tau }_{SC}\left(=3{\tau }_{SI}\right)$, which $t_0$ might fall within. After a successful reception of the ADV_IND, the subsequent exchange of SCAN_REQ and SCAN_RSP will always be successful because there are no other devices to interfere with their transmission/reception. Therefore the probability that $A_1$ ’s Ch37 ADV_IND results in a successful discovery by $S_1$, ${\alpha }_1=\left({\tau }_{SW}-T_S\right)/{\tau }_{SC}=\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}$. The argument and the result are no different from [5] [6] [7]. For ADV_IND event on Ch38, by considering that the arrival time of Ch38 ADV_IND at $S_1$ is also randomly distributed within ${\tau }_{SC}$, the probability that $A_1$ ’s Ch38 ADV_IND results in a successful discovery by $S_1$ is ${\alpha }_2=\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}$. Similarly for Ch39, ${\alpha }_3=\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}$. Though ${\alpha }_1={\alpha }_2={\alpha }_3$, their corresponding events are not independent.

What is wrong in the derivation of ${\alpha }_{\text{2}}$ and ${\alpha }_{\text{3}}$ in [5] [6] is that they assume the prior Ch37 ADV_IND arrival time ( $t_0$ ) is either in the $S_1$ ’s Ch38 (Ch39) scanning window (e.g., the second Ch38 ADV_IND in Figure 3), or in the $S_1$ ’s Ch37 scanning window (e.g., the first Ch38 ADV_IND in Figure 4). These are probabilities under certain implied conditions. In fact, $t_0$ can be in any scanning windows or even in the power-saving window for a successful Ch38 (or Ch39) discovery.

3.3. Dependency between Adjacent Successful Discoveries

In this section, we first show that there is a dependency between adjacent successful discovery events. We then prove with rigorous probability derivations that successful single-channel discovery probabilities are equal. Previously we define $E_{ch37}$ as the event that a Ch37 discovery succeeds. Similarly, let $E_{ch38}$, $E_{ch39}$ be the event that a Ch38, Ch39 discovery succeeds, respectively. Here $E_{ch37}$, $E_{ch38}$, $E_{ch39}$ are restricted to be the three successful discovery events (in the context of probability) in the same advertising event (advEvent). We now discuss the dependency of $E_{ch38}$ on $E_{ch37}$. We do not apply any restriction to the relationship among ${\tau }_{WA},{\tau }_{SW},{\tau }_{SI}$, except that ${\tau }_{SW}\le {\tau }_{SI}$, by system design. Without loss of generality, let time 0 be the start time of $S_1$ ’s Ch37 scanning window which event $E_{ch37}$ occurs. $t_0$ falls within (0, ${\tau }_{SW}-T_S$ ). That is,

$0<t_0<{\tau }_{SW}-T_S$ (4)

Then event $E_{ch38}$ occurs if $t_0+{\tau }_{WA}$ falls within any one of the ( $i{\tau }_{SC}+{\tau }_{SI}$, $i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S$ ), $i=0,1,2,3,\cdots$, or

$i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}<t_0<i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}$ (5)

The term $i{\tau }_{SC}$ accounts for the multiple candidate Ch38 scanning windows after the first Ch37 scanning window. For example, consider i = 0. Figure 5 shows a scenario where intervals specified by (4) and (5) overlap. Figure 5 is a case with ${\tau }_{WA}>{\tau }_{SI}$. The blue solid interval is due to (4) and the red dashed interval is due to (5) with i = 0. We note that the two intervals specified by (4) and (5) are of equal length. When ${\tau }_{WA}={\tau }_{SI}$, the two intervals completely overlap. When ${\tau }_{WA}<{\tau }_{SI}$, the red dashed interval shifted to the right and its left edge is greater than 0. For i> 0, overlapping intervals also exist for larger values of ${\tau }_{WA}$.

Given Equation (4) (event $E_{ch37}$ occurs), Equation (5) may hold (i.e., event $E_{ch38}$ occurs) only when the two intervals specified by (4) and (5) overlap, or in other words, if (4)’s upper bound is greater (5)’s lower bound (expressed in Equation (6)) AND (5)’s upper bound is greater than (4)’s lower bound (expressed in Equation (7)).

${\tau }_{SW}-T_S>i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}$,or ${\tau }_{WA}>i{\tau }_{SC}+{\tau }_{SI}-\left({\tau }_{SW}-T_S\right)$ (6)

$i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}>0$, or ${\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}+\left({\tau }_{SW}-T_S\right)$ (7)

In the BLE specification, ${\tau }_{WA}\le 10\text{ms}$, and the maximum possible $T_S=1.228\text{ms}$. For the complete discovery procedure (ADV_IND, SCAN_REQ, and SCAN_RSP successfully finish their transmission and reception) to have a chance to succeed, both ${\tau }_{SW}$ and ${\tau }_{WA}$ must be greater than $T_S$. That is, ${\tau }_{SW}-T_S>0$ and ${\tau }_{WA}-T_S>0$. Define the effective scan window ${\tau }_{S{W}^{\prime }}={\tau }_{SW}-T_S$. Then (6) and (7) can be combined into

$i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ (8)

Equation (8) specifies the possible intervals for ${\tau }_{WA}$ such that event $E_{ch38}$ may

Figure 5. Illustration of overlapping intervals for valid $t_0$ due to (4) and (5).

occur. We first consider i = 0. ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$. There are two distinct cases.

1) ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}\le {\tau }_{WA}\le {\tau }_{SI}$ : The intersection of the intervals specified by (4) and (5) is $\left({\tau }_{SI}-{\tau }_{WA},{\tau }_{SW}-T_S\right)$.

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left({\tau }_{SW}-T_S-{\tau }_{SI}+{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

2) ${\tau }_{SI}<{\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ : The intersection of the intervals specified by (4) and (5) is $\left(0,{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)$.

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left({\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

We next consider i = 1. That is, $E_{ch38}$ may occur in the next scan cycle. ${\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$.

3) ${\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}$ : The intersection of the intervals specified by (4) and (5) is $\left({\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA},{\tau }_{SW}-T_S\right)$.

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left({\tau }_{SW}-T_S-{\tau }_{SC}-{\tau }_{SI}+{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

1) ${\tau }_{SC}+{\tau }_{SI}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}+\left({\tau }_{SW}-T_S\right)$ : The intersection of the intervals specified by (4) and (5) is $\left(0,{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)$.

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left({\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

Continue on. We consider $i=\text{2},\text{3},\text{4},\cdots$. That is, $E_{ch38}$ may occur in the third, fourth, fifth, … scan cycle. Following the same approach as above, it should not be too difficult to verify that there is a general formula for the conditional probability $\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]$.

2) $i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}$ :

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left({\tau }_{SW}-T_S-i{\tau }_{SC}-{\tau }_{SI}+{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

3) $i{\tau }_{SC}+{\tau }_{SI}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ :

$\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]=\left(i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

Figure 6 shows the conditional probability $\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]$ as a function of ${\tau }_{WA}$. Note that in the BLE specification, ${\tau }_{WA}\le 10\text{ms}$, and ${\tau }_{SI}\ge {\tau }_{SW}>T_S=1.228\text{ms}$. Since the successful discovery probability for a single channel is proportional to ${\tau }_{SW}-T_S$, a reasonable ${\tau }_{SW}$ value should be greater than 1.5 ms. Therefore in reality $i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}$ is greater than 10 ms if i> 2. Hence the probability of $E_{ch38}$ occurring in the third scan cycle and after is negligible.

Next, we consider the case that $E_{ch37}$ does not occur, specified by $\overline{E_{ch37}}$. $t_0$ falls within ( ${\tau }_{SW}-T_S$, $3{\tau }_{SI}$ ). Then $E_{38}$ occurs if $t_0+{\tau }_{WA}$ falls within any one of the intervals ( $i{\tau }_{SC}+{\tau }_{SI}$, $i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S$ ), $i=0,1,2,3,\cdots$, or

${\tau }_{SW}-T_S<t_0<3{\tau }_{SI}$ (9)

$i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}<t_0<i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}$ (10)

The condition that the two intervals specified by (9) and (10) overlap is

$\left(i-1\right){\tau }_{SC}+{\tau }_{SI}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}\text{,}i=0,1,2,3,\cdots$ (11)

The condition that the two intervals specified by (9) and (10) overlap is

$\left(i-1\right){\tau }_{SC}+{\tau }_{SI}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}\text{,}i=0,1,2,3,\cdots$ (11)

We first consideri = 0. Equation (11) becomes $-2{\tau }_{SI}<{\tau }_{WA}<{\tau }_{SI}$. But ${\tau }_{WA}$ is always positive. We then consider two distinct cases.

1) $0\le {\tau }_{WA}\le {\tau }_{SI}-{\tau }_{S{W}^{\prime }}$ : The intersection of the intervals specified by (9) and (10) is $\left({\tau }_{SI}-{\tau }_{WA},{\tau }_{SI}-{\tau }_{WA}+{\tau }_{SW}-T_S\right)$.

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{SW}-T_S\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

2) ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}\le {\tau }_{SI}$ : The intersection of the intervals specified by (9) and (10) is $\left({\tau }_{SW}-T_S,{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)$.

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{SI}-{\tau }_{WA}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

We next consider i = 1. Equation (11) becomes ${\tau }_{SI}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}$. We consider three cases.

1) ${\tau }_{SI}<{\tau }_{WA}<{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ : The intersection of the intervals specified by (9) and (10) is $\left({\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA},{\tau }_{SC}\right)$.

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{WA}-{\tau }_{SI}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

2) ${\tau }_{SI}+{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}$ : The intersection of the intervals specified by (9) and (10) is $\left({\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA},{\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}+{\tau }_{SW}-T_S\right)$.

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{SW}-T_S\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

3) ${\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}$ : The intersection of the intervals specified by (9) and (10) is $\left({\tau }_{SW}-T_S,{\tau }_{SC}+{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)$.

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

Continue on. We consider $i=\text{2},\text{3},\text{4},\cdots$. Following the same approach as above, the general formula for the conditional probability $\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]$ is:

1) $\left(i-1\right){\tau }_{SC}+{\tau }_{SI}<{\tau }_{WA}<\left(i-1\right){\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{WA}-{\tau }_{SI}-\left(i-1\right){\tau }_{SC}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

2) $\left(i-1\right){\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}$ :

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left({\tau }_{SW}-T_S\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

3) $i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}$ :

$\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]=\left(i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{WA}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

Figure 7 shows the conditional probability $\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]$ as a function of ${\tau }_{WA}$. We observe that it is to some degree complementary with $\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]$ in Figure 6.

We now verify that the unconditional ch38 discovery probability $\mathrm{Pr}\left[E_{ch38}\right]$ is the same as the unconditional ch37 discovery probability $\mathrm{Pr}\left[E_{ch37}\right]$, regardless of the value of ${\tau }_{WA}$. Due to the periodicity of $\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]$ and $\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]$, shown in Figure 6 and Figure 7, we need only to consider three cases.

Figure 6. Successful channel 38 discovery probability given that channel 37 discovery is successful.

Figure 7. Successful channel 38 discovery probability given that channel 37 discovery fails.

1) ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}\le {\tau }_{WA}\le {\tau }_{SI}$ :

$\begin{array}{c}\mathrm{Pr}\left[E_{ch38}\right]=\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]\cdot \mathrm{Pr}\left[\overline{E_{ch37}}\right]\\ =\left({\tau }_{SW}-T_S-{\tau }_{SI}+{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)\cdot \left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\\ +\left({\tau }_{SI}-{\tau }_{WA}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)\cdot \left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)/3{\tau }_{SI}\\ =\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\end{array}$

2) ${\tau }_{SI}<{\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ :

$\begin{array}{c}\mathrm{Pr}\left[E_{ch38}\right]=\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]\cdot \mathrm{Pr}\left[\overline{E_{ch37}}\right]\\ =\left({\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)\cdot \left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\\ +\left({\tau }_{WA}-{\tau }_{SI}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)\cdot \left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)/3{\tau }_{SI}\\ =\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\end{array}$

3) ${\tau }_{SI}+{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}$ :

$\begin{array}{c}\mathrm{Pr}\left[E_{ch38}\right]=\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]\cdot \mathrm{Pr}\left[\overline{E_{ch37}}\right]\\ =0\cdot \left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\\ +\left({\tau }_{SW}-T_S\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)\cdot \left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)/3{\tau }_{SI}\\ =\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\end{array}$

In Figure 6, we see that $\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]$ is not equal to $\mathrm{Pr}\left[E_{ch38}\right]$, except for few values of ${\tau }_{WA}$. It clearly shows that event $E_{ch38}$ and event $E_{ch37}$ cannot be treated as independent events.

As to the joint behavior of ch37 and ch38 discoveries, we expect both to complement each other for maximum discovery probability. It is the probability of $E_{ch37}\cup E_{ch38}$.

$\begin{array}{c}\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\right]=\mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}\cap \overline{E_{ch37}}\right]\\ =\mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}|\overline{E_{ch37}}\right]\cdot \mathrm{Pr}\left[\overline{E_{ch37}}\right]\end{array}$

Figure 8 plots $\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\right]$ as a function of ${\tau }_{WA}$. It shows that ${\tau }_{WA}$ should be chosen to be not in $\left(i{\tau }_{SC}-{\tau }_{S{W}^{\prime }},i{\tau }_{SC}+{\tau }_{S{W}^{\prime }}\right),i=0,1,2,3,\cdots$ for maximum discovery probability regarding the combined ch37 and ch38 discovery. In these situations, $E_{ch37}$ and $E_{ch38}$ are disjoint events. If ch37 discover succeeds, ch38 discovery will not, and vice versa. It achieves the maximum possible successful discovery probability for two successive discovery events.

3.4. Dependency between Non-Adjacent Successful Discoveries

We now discuss the dependency of $E_{ch39}$ on $E_{ch37}$. Event $E_{ch37}$ occurs when $t_0$ falls within (0, ${\tau }_{SW}-T_S$ ), previously specified in Equation (4). Then event $E_{ch39}$ occurs if $t_0+2{\tau }_{WA}$ falls within any one of the ( $i{\tau }_{SC}+2{\tau }_{SI}$, $i{\tau }_{SC}+2{\tau }_{SI}+{\tau }_{SW}-T_S$ ), $i=0,1,2,3,\cdots$, or

$i{\tau }_{SC}+2{\tau }_{SI}-2{\tau }_{WA}<t_0<i{\tau }_{SC}+2{\tau }_{SI}+{\tau }_{SW}-T_S-2{\tau }_{WA},i=0,1,2,3,\cdots$ (12)

Figure 8. Probability that at least one of the two channel discoveries is successful.

Similar to the derivation in Section 3.3, given Equation (4) (event $E_{ch37}$ occurs), Equation (12) may hold (i.e., event $E_{ch39}$ occurs) only when the two intervals specified by (4) and (12) overlap, or in other words, if (4)’s upper bound is greater (12)’s lower bound (expressed in Equation (13)) and (12)’s upper bound is greater than (4)’s lower bound (expressed in Equation (14)).

${\tau }_{S{W}^{\prime }}>i{\tau }_{SC}+2{\tau }_{SI}-2{\tau }_{WA}$ or ${\tau }_{WA}>i{\tau }_{SC}/2+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2$ (13)

$i{\tau }_{SC}+2{\tau }_{SI}+{\tau }_{S{W}^{\prime }}-2{\tau }_{WA}>0$ or ${\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2$ (14)

which can be combined into

$i{\tau }_{SC}/2+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2<{\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2,i=0,1,2,3,\cdots$ (15)

Due to the space limitation we directly give the general formulas for the conditional probability $\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]$. The derivations follow the same approach as in Section 3.3,

1) $i{\tau }_{SC}/2+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2<{\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}$ :

$\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]=\left({\tau }_{SW}-T_S-i{\tau }_{SC}-2{\tau }_{SI}+2{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

2) $i{\tau }_{SC}/2+{\tau }_{SI}<{\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2$ :

$\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]=\left(i{\tau }_{SC}+2{\tau }_{SI}+{\tau }_{SW}-T_S-2{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S\right)$.

The general formulas for the conditional probability $\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]$ are:

1) $\left(i{\tau }_{SC}-{\tau }_{SI}\right)/2<{\tau }_{WA}<\left(i{\tau }_{SC}-{\tau }_{SI}\right)/2+{\tau }_{S{W}^{\prime }}/2$, $i=1,2,3,\cdots$

$\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]=\left(2{\tau }_{WA}+{\tau }_{SI}-i{\tau }_{SC}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

2) $\left(i{\tau }_{SC}-{\tau }_{SI}\right)/2+{\tau }_{S{W}^{\prime }}/2<{\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2$, $i=0,1,2,3,\cdots$

$\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]=\left({\tau }_{SW}-T_S\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

3) $i{\tau }_{SC}/2+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2<{\tau }_{WA}<i{\tau }_{SC}/2+{\tau }_{SI}$, $i=0,1,2,3,\cdots$

$\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]=\left(i{\tau }_{SC}+2{\tau }_{SI}-2{\tau }_{WA}\right)/\left(3{\tau }_{SI}-{\tau }_{SW}+T_S\right)$.

Figure 9 shows the conditional probabilities $\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]$ and

Figure 9. Successful channel 39 discovery probability given that channel 37 discovery succeeds/fails.

$\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]$ as a function of ${\tau }_{WA}$. They show repeating pattern at the cycle of $1.5{\tau }_{SI}$. Readers can also verify that the unconditional ch39 discovery probability $\mathrm{Pr}\left[E_{ch39}\right]$ is the same as the unconditional ch37 discovery probability $\mathrm{Pr}\left[E_{ch37}\right]$, regardless of the value of ${\tau }_{WA}$.

$\begin{array}{c}\mathrm{Pr}\left[E_{ch39}\right]=\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch39}|\overline{E_{ch37}}\right]\cdot \mathrm{Pr}\left[\overline{E_{ch37}}\right]\\ =\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}\end{array}$

3.5. Probability of at Least one Successful Single-Channel Discovery in an Advertising Interval

That the three consecutive ADV_IND packets in an advEvent are transmitted on different channels is to maximize the probability of discovery and therefore speed up the discovery process. This is equivalent to maximizing the probability of a union event $E_{ch37}\cup E_{ch38}\cup E_{ch39}$, representing that at least one single-channel discovery succeeds in an advEvent. We call it a successful advEvent discovery.

$\begin{array}{l}\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]\\ =\mathrm{Pr}\left[E_{ch37}\right]+\mathrm{Pr}\left[E_{ch38}\right]+\mathrm{Pr}\left[E_{ch39}\right]-\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\right]\\ -\mathrm{Pr}\left[E_{ch37}\cap E_{ch39}\right]-\mathrm{Pr}\left[E_{ch38}\cap E_{ch39}\right]+\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\cap E_{ch39}\right]\end{array}$

We have known that $\mathrm{Pr}\left[E_{ch37}\right]=\mathrm{Pr}\left[E_{ch38}\right]=\mathrm{Pr}\left[E_{ch39}\right]=\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}$. $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\right]=\mathrm{Pr}\left[E_{ch38}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]$, and is plotted in Figure 7. $\mathrm{Pr}\left[E_{ch38}\cap E_{ch39}\right]$ can be derived similar to $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\right]$. $\mathrm{Pr}\left[E_{ch37}\cap E_{ch39}\right]=\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]\cdot \mathrm{Pr}\left[E_{ch37}\right]$ is also known because we have derived $\mathrm{Pr}\left[E_{ch39}|E_{ch37}\right]$. What is unknown is $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\cap E_{ch39}\right]$.

$E_{ch37}\cap E_{ch38}\cap E_{ch39}$ occurs when Equation (4), Equation (5), and Equation (12) hold. From earlier discussion in Section 3.3, $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\right]$ is non-zero when

$i{\tau }_{SC}+{\tau }_{SI}-{\tau }_{S{W}^{\prime }}<{\tau }_{WA}<i{\tau }_{SC}+{\tau }_{SI}+{\tau }_{S{W}^{\prime }}$, $i=0,1,2,3,\cdots$

Taking i = 0 for example, we discuss two situations: ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}\le {\tau }_{WA}\le {\tau }_{SI}$ and ${\tau }_{SI}<{\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}$.

1) ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}\le {\tau }_{WA}\le {\tau }_{SI}$ : The intersection of the intervals specified by (4) and (5) is $\left({\tau }_{SI}-{\tau }_{WA},{\tau }_{SW}-T_S\right)$. For Equation (12) to also hold ( $E_{ch39}$ occurs), $t_0$ must be in $\left(2{\tau }_{SI}-2{\tau }_{WA},2{\tau }_{SI}-2{\tau }_{WA}+{\tau }_{S{W}^{\prime }}\right)$. The intersection of these two intervals is $\left(2{\tau }_{SI}-2{\tau }_{WA},{\tau }_{SW}-T_S\right)$ and ${\tau }_{WA}$ is further restricted to be ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2\le {\tau }_{WA}\le {\tau }_{SI}$. Therefore, we have $\mathrm{Pr}\left[E_{ch39}|E_{ch37}\cap E_{ch38}\right]=\left({\tau }_{SW}-T_S-2{\tau }_{SI}+2{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S-{\tau }_{SI}+{\tau }_{WA}\right)$, for ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2\le {\tau }_{WA}\le {\tau }_{SI}$. Previously, we have found that

$\mathrm{Pr}\left[E_{ch38}\cap E_{ch37}\right]=\left({\tau }_{SW}-T_S-{\tau }_{SI}+{\tau }_{WA}\right)/3{\tau }_{SI}$.

Therefore $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\cap E_{ch39}\right]=\left({\tau }_{SW}-T_S-2{\tau }_{SI}+2{\tau }_{WA}\right)/3{\tau }_{SI}$, for ${\tau }_{SI}-{\tau }_{S{W}^{\prime }}/2\le {\tau }_{WA}\le {\tau }_{SI}$.

2) ${\tau }_{SI}<{\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}$ : The intersection of the intervals specified by (4) and (5) is $\left(0,{\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)$. For Equation (12) to also hold, $t_0$ must be in $\left(2{\tau }_{SI}-2{\tau }_{WA},2{\tau }_{SI}-2{\tau }_{WA}+{\tau }_{SW}-T_S\right)$. The intersection of these two intervals is $\left(0,2{\tau }_{SI}-2{\tau }_{WA}+{\tau }_{SW}-T_S\right)$ and ${\tau }_{WA}$ is further restricted to be ${\tau }_{SI}\le {\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2$. Therefore, we have $\mathrm{Pr}\left[E_{ch39}|E_{ch37}\cap E_{ch38}\right]=\left({\tau }_{SW}-T_S-2{\tau }_{SI}+2{\tau }_{WA}\right)/\left({\tau }_{SW}-T_S-{\tau }_{SI}+{\tau }_{WA}\right)$, for ${\tau }_{SI}\le {\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2$. Previously, we have found that

$\mathrm{Pr}\left[E_{ch38}\cap E_{ch37}\right]=\left({\tau }_{SI}+{\tau }_{SW}-T_S-{\tau }_{WA}\right)/3{\tau }_{SI}$.

Therefore $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\cap E_{ch39}\right]=\left({\tau }_{SW}-T_S+2{\tau }_{SI}-2{\tau }_{WA}\right)/3{\tau }_{SI}$, for ${\tau }_{SI}\le {\tau }_{WA}\le {\tau }_{SI}+{\tau }_{S{W}^{\prime }}/2$.

Using similar technique we can find other $\mathrm{Pr}\left[E_{ch37}\cap E_{ch38}\cap E_{ch39}\right]$ with $i=1,2,3,\cdots$. With them calculated, we can finally obtain $\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]$ as

1) $\left|{\tau }_{WA}-{\tau }_{SI}-i{\tau }_{SC}\right|\le {\tau }_{SW}-T_S$, $i=0,1,2,3,\cdots$

$\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]=\left({\tau }_{SW}-T_S+2\left|{\tau }_{SI}+i{\tau }_{SC}-{\tau }_{WA}\right|\right)/3{\tau }_{SI}$.

2) $\left|{\tau }_{WA}-{\tau }_{SI}-i{\tau }_{SC}/2\right|\le \left({\tau }_{SW}-T_S\right)/2$, $i=0,1,2,3,\cdots$

$\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]=\left(2{\tau }_{SW}-2T_S+2{\tau }_{SI}+i{\tau }_{SC}-2{\tau }_{WA}\right)/3{\tau }_{SI}$.

3) otherwise,

$\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]=\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$

This is the main result of this paper. Figure 10 plots $\mathrm{Pr}\left[E_{ch37}\cup E_{ch38}\cup E_{ch39}\right]$, the probability of a successful advEvent discovery, as a function of ${\tau }_{WA}$. When ${\tau }_{WA}$ coincides with ${\tau }_{SI}+i{\tau }_{SC}$, the probability of a successful advEvent discovery is minimized. This is the ill-fated synchronization between advertising and scanning. At best, only one of the three single-channel discoveries is successful. When ${\tau }_{WA}$ coincides with ${\tau }_{SI}+\left(2i+1\right){\tau }_{SC}/2$, the probability of a successful advEvent discovery can be doubled from the minimum value. Two out of the three single-channel discoveries may be successful. When ${\tau }_{WA}$ is at a suitable distance away from the above two sets of “saddle points”, the probability of a

Figure 10. Probability that at least one of the three channel discoveries is successful.

successful advEvent discovery is maximized at $\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$, which is three times of the minimum value. In this case, the three single-channel discoveries are disjoint events. They complement one another to make the discovery most fruitful.

Figure 11 is a 3D plot of the probability of a successful advEvent discovery vs. advertising duration ${\tau }_{WA}$ and scan interval ${\tau }_{SI}$. The scan window ${\tau }_{SW}$ is set to be equal to the scan interval (continuous scanning). The surface plot shows three sets of saddle points. They correspond to ${\tau }_{WA}={\tau }_{SI}$, $2.5{\tau }_{SI}$, and $4{\tau }_{SI}$, respectively. This result is in good agreement with that in Figure 10.

4. Verification and Discussions

We wrote a python simulation program to verify the accuracy of the discovery probability analysis. In each simulation run with certain specified ${\tau }_{WA}$, ${\tau }_{SI}$, ${\tau }_{SW}$ values, 100,000 advEvents were generated. Successful discoveries on channels 37, 38, 39 were individually recorded. This allowed us to obtain successful single-channel discovery probabilities $\mathrm{Pr}\left[E_{ch37}\right]$, $\mathrm{Pr}\left[E_{ch38}\right]$, and $\mathrm{Pr}\left[E_{ch39}\right]$. They were found to be nearly identical and very close to $\left({\tau }_{SW}-T_S\right)/3{\tau }_{SI}$ (within the simulation accuracy tolerance) for all parameter values chosen. Successful discoveries from the advEvent point of view were also recorded. This allowed us to obtain successful advEvent discovery probabilities. They are compared with analytical results and one example is shown in Figure 12, where ${\tau }_{WA}$ is set to 10 ms and ${\tau }_{SI}$ ranges from 2.5 ms to 50 ms. Simulation results (with

Figure 11. 3D plot of probability of a successful advEvent discovery (continuous scanning mode, scanning window is the same as scanning interval).

(a)(b)

Figure 12. Probability of a successful advEvent discovery (advDuration ${\tau }_{WA}=10\text{ms}$ ) by (a) analysis (scan window resolution 0.625 ms) (b) simulation (scan window resolutin 1.25 ms).

scan window resolution 1.25 ms) and analytical results (with scan window resolution 0.625 ms) match well both visually and actually (the difference has a mean value of 0.3 percent and standard deviation 0.48 percent). Again, the saddle points in Figure 12 are around ${\tau }_{SI}=10\text{ms}$ . This is also what the analysis predicted that ${\tau }_{WA}={\tau }_{SI},4{\tau }_{SI},7{\tau }_{SI},\cdots$ are where the successful discovery probability is minimized. That the simulation agrees well with analysis is expected because in the analysis we did not make any simplifying assumptions.

In Section 4, we show that the maximum successful advEvent discovery probability is $\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$. Since $T_S$ is a fixed value and scan window ${\tau }_{SW}$ is bounded by scan interval ${\tau }_{SI}$, $\left({\tau }_{SW}-T_S\right)/{\tau }_{SI}$ is maximized when ${\tau }_{SW}$ is equal to ${\tau }_{SI}$ and both as large as possible. This agrees with what we observed in Figure 12 that the successful advEvent discovery probability is the highest when ${\tau }_{SW}={\tau }_{SI}=50\text{ms}$. Since ${\tau }_{WA}$ is limited to be within 10 ms, any value of ${\tau }_{SI}$ greater than 20 ms has no danger of causing the ill-fated advertising/scanning synchronization (i.e., ${\tau }_{WA}={\tau }_{SI},4{\tau }_{SI},7{\tau }_{SI},\cdots$ ). This, however, is from the discovery probability point of view. If we also consider energy saving, scan window ${\tau }_{SW}$ should not be too long. A balance between quick discovery and energy saving needs to be considered in determining the optimal parameter values.

5. Conclusion

BLE has been in use for many years. However, how to configure its parameters for quick neighbor discovery has been troublesome for many implementers. We use rigorous probability derivations to clarify disagreements in prior works and also provide insights on how to configure parameters for maximizing discovery probability. To be specific, we show that the probabilities of successful discoveries on each of the three discovery channels are equal. But those three discovery events are dependent events. In addition, we show that there are several parameter settings that will cause low discovery probability. In particular, if the advertising duration ${\tau }_{WA}$ is set to equal to some multiples of scan interval ( ${\tau }_{SI},4{\tau }_{SI},7{\tau }_{SI},\cdots$ ), which we call ill-fated advertising/scanning synchronization, the discovery process will be the least efficient. For maximum discovery probability, the length of the scan window should be large, which leads to large scan interval too. However, this is not necessarily good for energy saving. Currently, our analysis applies to the 1:1 (one advertiser and one scanner) scenario. Future works are to extend it to multiple advertisers or multiple scanners. This study can also serve as a base for discovery latency and energy consumption analysis.

Acknowledgements

This work was supported by grants from MOST (Most 108-2221-E-194-009-MY2, MOST 108-2218-E-194-007), Taiwan.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bluetooth SIG. (2010) Bluetooth Core Specification Version 4.0, July 2010.
[2]	Liu, J., Chen, C.F. and Ma, Y. (2012) Modeling and Performance Analysis of Device Discovery in Bluetooth Low Energy Networks. 2012 IEEE Global Communications Conference (Globecom), Anaheim, 3-7 December 2012, 1538-1543.
[3]	Liu, J., Chen, C.F. and Ma, Y. (2012) Modeling Neighbor Discovery in Bluetooth Low Energy Networks. IEEE Communications Letters, 16, 1439-1441. https://doi.org/10.1109/LCOMM.2012.073112.120877
[4]	Liu, J., Chen, C.F., Ma, Y. and Xu, Y. (2013) Adaptive Device Discovery in Bluetooth Low Energy Networks. 2013 IEEE 77th Vehicular Technology Conference (VTC Spring), Dresden, 2-5 June 2013, 1-5. https://doi.org/10.1109/VTCSpring.2013.6691855
[5]	Cho, K., Park, W., Hong, M., Park, G., Cho, W., Seo, J. and Han, K. (2015) Analysis of Latency Performance of Bluetooth Low Energy (BLE) Networks. Sensors, 2015, 15, 59-78. https://doi.org/10.3390/s150100059
[6]	Cho, K., Park, G., Cho, W., Seo, J. and Han, K. (2016) Performance Analysis of Device Discovery of Bluetooth Low Energy (BLE) Networks. Computer Communications, 81, 72-85. https://doi.org/10.1016/j.comcom.2015.10.008
[7]	Yang, T. and Tseng, H. (2017) Two-Way Communication with Wait-slot Scheme for Neighbor Discovery Process in Dense Bluetooth Low Energy Networks. 2017 13th International Conference on Network and Service Management (CNSM), Tokyo, 26-30 November 2017, 1-7. https://doi.org/10.23919/CNSM.2017.8255997
[8]	Shan, G. and Roh, B. (2018) Advertisement Interval to Minimize Discovery Time of Whole BLE Advertisers. IEEE Access, 6, 17817-17825. https://doi.org/10.1109/ACCESS.2018.2817343
[9]	Kindt, P.H., Yunge, D., Diemer, R. and Chakraborty, S. (2020) Energy Modeling for the Bluetooth Low Energy Protocol. ACM Transactions on Embedded Computing Systems, 19, Article No. 13. https://doi.org/10.1145/3379339
[10]	Seo, J. and Han, K. (2020) A Survey of Enhanced Device Discovery Schemes in Bluetooth Low Energy Networks. IETE Technical Review. https://doi.org/10.1080/02564602.2020.1742806