Mickael Elodie Morin ⇤ § ¶

Roberto Guizzetti

Andrzej Duda

Singer Cyclic Difference Sets for an Energy-Efficient Joining Scheme

Keywords: Cyclic Difference Set, Internet of Things, Joining Protocol, Network Discovery, 802.15.4e TSCH

This paper considers the problem of joining a network of constrained IoT devices. We propose to take advantage of Singer Cyclic Difference Sets (S-CDS) for a joining scheme that results in low duty cycles and apply the proposed scheme to the joining problem in 802.15.4e TSCH networks. S-CDS distributes the active periods of nodes over time so that a joining node does not suffer from long scanning periods in contrast to other schemes. We compare S-CDS through simulation with other state-of-the-art schemes adapted to TSCH networks. The comparisons show that S-CDS achieves a better trade-off between energy consumption and joining delay than the best joining schemes while being particularly suitable for devices with strong energy constraints such as energy harvesting nodes.

I. INTRODUCTION

Internet of Things (IoT) networks face new challenges such as energy efficiency, mobility management, and scalability. Although crucial, the joining phase in which a node enters an existing network and starts to operate according to the established configuration of the network, was often neglected. This phase only becomes important when people start to deploy networks in real-world use cases.

To save energy, IoT nodes usually operate at low duty cycles: they go to sleep most of the time and only wake up at some instants to communicate. For efficient communication, nodes are synchronized (e.g., beacon-enabled 802.15.4 or 802.15.4e TSCH [1]) and intermittently send beacons (short frames with network parameters) to enable other nodes to join the network. Such an operation makes the discovery of the network particularly difficult because the joining node does not know the channel of a beacon nor the instant at which other nodes will wake up. The situation is even more complex in the case of energy harvesting nodes that obtain energy from the environment and only rely on a small capacity battery. Such devices do not have a fixed initial amount of energy for operation, so they cannot stay awaken during long periods scanning for beacons-they need to distribute the scanning periods over time and interleave them with the periods of energy harvesting.

The objective of a joining scheme is to minimize the scan duration to consume the minimal amount of energy during this phase and join the network as fast as possible. An intuitive approach is to let the network nodes periodically send beacons and a joining node continuously scan a chosen channel until it receives a beacon (e.g., in a beacon-enabled 802.15.4 network [1]). The work by Qiu et al. [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF] formalized this asymmetric approach. As the joining node does not know whether it is in the communicating range of a node that sends beacons, we must take into account the scenario in which a joining node will not receive any beacons because the network nodes are too far away or they have moved. To design an energy-efficient scheme, we must focus not only on the average joining energy consumption but also on the worst case scenario in which no advertising node is in the communicating range of the joining node. For instance, a joining scheme when a node just switches its radio on to continuously scan for beacons is not feasible for an energy harvesting node: a duty cycle approach for both the joining and the advertising nodes is also required.

There is extensive literature with theoretical work on symmetric neighbor discovery in the context of ad hoc, mobile, and sensor networks assuming a time-slotted discovery model. In this model, time is divided into fixedwidth slots and the roles of the nodes are symmetrical: they need to discover each other without prior synchronization information in bounded time. In each slot, a node can go to sleep or actively scan for a neighbor by transmitting a beacon at the beginning and the end of the slot, and listening to (scanning for) beacons sent by a neighbor [START_REF] Dutta | Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[END_REF]. In this model, the nodes successfully discover each other when two active slots in the wake up/scan schedule temporally overlap.

Meng et al. [START_REF] Meng | On Designing Neighbor Discovery Protocols: a Code-Based Approach[END_REF] proposed an approach based on Cyclic Difference Sets (CDS) [START_REF] Baumert | Cyclic Difference Sets[END_REF]. They showed that the proposed scheme outperforms Searchlight, a former best performing symmetric discovery scheme [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF]. However, the optimal difference codes only exist for a few values of the duty cycle in practice and are currently not realizable except for some special configurations [START_REF] Kindt | Griassdi: Mutually Assisted Slotless Neighbor Discovery[END_REF].

In this work, we focus on the joining problem for nodes that cannot stay active for long periods of time, i.e., nodes that need to use their radio according to a low duty cycle pattern, not only during the operational phase, but also during the joining phase. For this purpose, we extend the approach based on CDS [START_REF] Meng | On Designing Neighbor Discovery Protocols: a Code-Based Approach[END_REF] by taking advantage of Singer CDS [START_REF] Singer | A Theorem in Finite Projective Geometry and Some Applications to Number Theory[END_REF] and we apply our scheme for the joining problem in 802.15.4e TSCH networks. We evaluate the proposed scheme with a simulation based comparison with other protocols adapted to TSCH networks: Searchlight [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF], B-Nihao, and a duty cycle version of B-Nihao [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF]. The comparison shows that for low duty cycles, the proposed scheme consumes less energy than Searchlight for similar joining latency. Moreover, it results in shorter joining latency than B-Nihao for similar energy consumption. II. BACKGROUND ON NEIGHBOR DISCOVERY Pozza et al. presented a global survey of proposed neighbor discovery protocols [START_REF] Pozza | Neighbor Discovery for Opportunistic Networking in Internet of Things Scenarios: a Survey[END_REF]. In their taxonomy, mobility agnostic, asynchronous, temporal overlapping neighbor discovery protocols fall into two categories: probabilistic and deterministic protocols. In probabilistic methods, nodes listen, transmit, or sleep with different probabilities, which leads to unpredictable rendezvous delays and long tails of the joining delay distribution [START_REF] Mcglynn | Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[END_REF]. Deterministic protocols provide bounds on delay based on the Chinese Remainder Theorem (DISCO, U-Connect) [START_REF] Dutta | Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[END_REF], [START_REF] Kandhalu | U-Connect: a Low-Latency Energy-Efficient Asynchronous Neighbor Discovery Protocol[END_REF], quorum-based overlaps (Quorum, Searchlight, Hello) [START_REF] Luk | Two New Quorum Based Algorithms for Distributed Mutual Exclusion[END_REF], [START_REF] Tseng | Power-Saving Protocols for IEEE 802.11-Based Multi-Hop Ad Hoc Networks[END_REF], [START_REF] Jiang | Quorum-Based Asynchronous Power-Saving Protocols for IEEE 802.11 Ad Hoc Networks[END_REF], [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF], [START_REF] Sun | Hello: a Generic Flexible Protocol for Neighbor Discovery[END_REF], or combinatorial techniques with CDS [START_REF] Zheng | Optimal Block Design for Asynchronous Wake-Up Schedules and Its Applications in Multihop Wireless Networks[END_REF], [START_REF] Meng | On Designing Neighbor Discovery Protocols: a Code-Based Approach[END_REF]. In this paper, we focus on the lowest consuming protocols of the literature: Searchlight [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF] and B-Nihao [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF].

To characterize the duty cycle of the considered joining schemes, we define the Slot Duty Cycle (SDC) that corresponds to the proportion of active slots (in reception Rx or in transmission Tx) during a frame and the Duty Cycle (DC), the proportion of the time the node radio is active during a frame. SDC may be different from DC, if the radio is not active during a whole slot. We use the Rx and Tx time as the metrics of energy consumption-we assume that the radio energy consumption varies linearly with the time the radio stays in these modes, the slope only being different for different hardware platforms.

A. Searchlight-S

The striped version of Searchlight (Searchlight-S) [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF] is an energy-efficient, well-proven, and fully deterministic quorum-based protocol. In this variant, a node only wakes up twice in a frame of t consecutive slots, so SDC experienced by the network and the joining node is 2 t . We can choose frame size t to obtain a given target duty cycle both for the network and the joining node. Two active slots are distributed in the first half of a frame as follows:

• Anchor slots (A): the first slot of the frame is always an active slot. • Probe slots (P): the second active slot changes place each frame iteration to "search for" the anchor slot of the other node. In systematic probing, Probe slot P is initialized as the slot just after Anchor slot A, i.e., the second slot of the frame. It then selects the next slot for each frame repetition. Hence, the probing slots will be in the third slot of the frame at the second repetition, the forth one at the third repetition, and so on.

To handle non-alignment of slots, Searchlight uses the Disco solution consisting of sending beacons not once per slot, but at the beginning and the end of a slot. Bakht et al. [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF] showed that, as nodes transmit two beacons per slot and select their probing slots in a consecutive way, Searchlight can skip one probing slot out of two without impacting performance. Hence, in the striped version of Searchlight (Searchlight-S), the probing slots are only selected as one out of two slots in the frame. To cover the case of perfect slot alignment, Bakht et al. proposed to slightly increase the slot size while in activity and compensate with a reduction of the next inactive slot. Fig. 1 illustrates the principle of Searchlight-S. In this example, the Searchlight pattern is repeated after two frames and active slots are slightly larger than other slots. The following slots are reduced to compensate this increase.

Network Schedule

Node Schedule

R T T T T T T T T T T T T (a) Simplified version of Nihao (S-Nihao).

Network Schedule

SDC = 1/t Node Schedule R R R R R R T T T t n (

B. B-Nihao

Nihao [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF] adopts a different model with respect to timeslotted protocols by defining dedicated receive and transmit slots. In a transmit slot, a node sends a short beacon at the beginning of the slot so that the node listening in a receive slot can get the beacon. In the S-Nihao variant, a node transmits beacons in each slot with the joining delay and Rx time of only one slot in the worst case (see Fig. 2a).

In its extended version called B-Nihao, nodes send a beacon after t slots and the joining node listen during t slots. Fig. 2b presents the main concept of B-Nihao.

III. S-CDS JOINING SCHEME

Our proposal is inspired by the work of Meng et al. [START_REF] Meng | On Designing Neighbor Discovery Protocols: a Code-Based Approach[END_REF]. They showed that a discovery scheme based on perfect Cyclic Difference Sets (CDS) consumes a small amount of energy with bounded delay. However, the generation of perfect CDS is difficult and only a small number of sequences are known: the lowest duty cycle we could find was for a sequence generated from an optimal Golomb Ruler with a 5% duty cycle. We propose to extend the CDS approach to handle low duty cycles (up to 0.3%) with the use of Singer Cyclic Difference Sets, CDS based on Singer cycles [START_REF] Singer | A Theorem in Finite Projective Geometry and Some Applications to Number Theory[END_REF].

A. Background on Cyclic Difference Sets

Cyclic Difference Sets (CDS) [START_REF] Baumert | Cyclic Difference Sets[END_REF] are defined as follows:

Definition 1. A v, k, -difference set D = {d 1 , d 2 , ..., d k } is a collection of k residues modulo v such that for any residue ij 6 ⌘ 0 (mod v), the congruence d i d j ⌘ ij (mod v) has exactly pairs (d i , d j ) with d i and d j in D. In other words, D = {d 1 , d 2 , ..., d
k } is a set of k positive numbers (less than v), with the property that all the difference ij mod n (for i 6 = j) are different. Definition 2. Perfect CDS is a Cyclic Difference Set for which = 1.

To apply CDS to the neighbor discovery problem, let us assume that the network sends beacons at the slots defined by a CDS sequence D = {d 1 , d 2 , ..., d k } and the joining node only listen at the slots that follow the same CDS sequence D. In our joining scheme, we exploit the shift property of perfect CDS:

• Every number from 0 up to v 1 occurs in exactly k shifts • Two different shifts of CDS have = 1 element in common.
Hence, CDS guarantee that for any offset at which the joining node starts the scanning (↵), there will be an overlap of an active slot of the network and a listening slot of the joining node.

B. Neighbor Discovery Example

Fig. 3 shows an example of neighbor discovery with a perfect 7,3,1-CDS sequence: {0, 1, 3} mod 7 [START_REF] Baumert | Cyclic Difference Sets[END_REF]. We assume that time is slotted and consider the network following a periodic schedule of a frame repeating in time. The size of the frame is set to CDS parameter v (7 in this case) and the active slots are selected from the sequence: slots 0, 1, and 3 are active while the other slots are in sleep mode. The listening schedule of the joining node is the same. Figure 3 shows different offsets ↵ of the joining node corresponding to possible instants at which the node wakes up and starts scanning. We also present the joining delay and the total time the node consumes energy when receiving (Rx time) until the node succeeds. Note that for legibility of the figure, offsets are full slot values (we deal with non-aligned slots later on).

R R R R R R R R R R R R T 1 T T T T T = 2 = 3 = 5 0 1 3 4 5 6 2 R R R 0 1 3 4 5 6 2 R R R 0 1 3 4 5 6 2 R R R 1
The example shows the main advantage of a CDS sequence: it gives the worst case delay bound (CDS size v) and allows the network and the joining node to distribute active (advertising or scanning) and inactive (radio switched off) slots to save energy. As all joining schemes, S-CDS presents a trade-off between energy consumption and low joining delay: more sleeping slots means lower energy consumption and longer delay.

C. Singer Cyclic Difference Sets

Singer Cyclic Difference Sets (S-CDS) are CDS based on Singer cycles [START_REF] Singer | A Theorem in Finite Projective Geometry and Some Applications to Number Theory[END_REF]. They are defined as follows.

Definition 3. For all prime power q, a Singer difference set exists. Let G = GF(q n+2 ) ⇤ /GF(q) ⇤ , where GF (q) is the Galois Field of order q, and GF(q) ⇤ is the multiplicative group of non-zero element. The set D = {x 2 G | Tr q n+2 /q (x) = 0} is a Singer v, k,difference set with the following parameters:

v = q N +1 1 q 1 , k = q N 1 q 1 , = q N 1 1 q 1
, where Tr

q n+2
/q : GF(q n+2 ) ! GF(q) is the trace function: Tr q n+2 /q (x) = x + x q + • • • + x q n+1 , and N = 2n. We propose to use S-CDS with parameter N = 2 and q relatively large to achieve low duty cycles, hence low energy

Searchlight-S S-CDS = {0,1,3,9} [13]

Network Node

B-Nihao

Short SL-S LongSL-S As mentioned in the introduction, a joining scheme based on CDS intrinsically fits networks with a time-slotted duty cycle schedule like TSCH [1]. TSCH organizes the network operation as a time-frequency map in which the time is structured in timeslots. TSCH nodes enable discovery of the network by other nodes with advertisement of Enhanced Beacons (EB). EBs provide the necessary information to actually join the network (such as Absolute Slot Number, timeslot template, hopping sequence, slot allocation in the slotframe, etc.). The joining scheme currently defined for TSCH networks [START_REF] Vilajosana | Minimal IPv6 over the TSCH Mode of IEEE 802[END_REF] proposes a non duty cycle operation for the joining node-when a node scans for a beacon, it will remain active until it receives EB, which may drain a large amount of energy.

DC-Nihao

SDC = = ~ 0,33 6 2 n SDC j Long Nihao T T T R R R R Short Nihao Network Node SDC = ~ 0,33 3 1 n SDC = 1 j T T T R R R Short DC-N Long DC-N Network Node T T T R R R R T T T T T R R R A P 2 A R+ 2T A P 1 2T 2T 2T 2T A P 2 A A P 1 R+ 2T 2T 2T 2T 2T SDC = = ~ 0,29 7
We propose to schedule the transmission of EBs on one well-known frequency channel dedicated to network discovery with active slots defined by S-CDS: the joining node uses the active slots in the S-CDS sequence to scan for beacons during a full TSCH slot.

E. Slot Non-Alignment

A joining node may wake up at any instant, so its slot may be not aligned in time with the slots used by the network. Prior work on neighbor discovery protocols handles slot nonalignment by sending a beacon at the beginning and the end of each active slots [START_REF] Dutta | Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[END_REF], [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF]. However, Qiu et al. showed that there is no need for two beacons: eliminating the beacon at the end of an active slot will not affect the discovery [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF].

Another indirect cause of slot non-alignment may be the clock drift experienced by nodes due to hardware imperfection. In our context, the imprecision of hardware clocks is not relevant since the joining node waking up is fully asynchronous, hence the initial offset may take any values with the same probability. We assume that the clock drift experienced during scanning is negligible because the joining delays we consider are of the order of tens of seconds. Besides, if needed, the node can wake up a little bit earlier than the next scheduled slot: the duration of the required guard interval directly depends on the time spent in sleep state and the hardware clock precision [START_REF] Morin | Comparison of the Device Lifetime in Wireless Networks for the Internet of Things[END_REF].

IV. EVALUATION

We evaluate the performance of the proposed joining scheme with a Python simulator that mimics the joining procedure of a node trying to join an operational TSCH network at random offset ↵ of the network schedule. The simulator computes the join delay and the time spent in reception (Rx time) of the joining node for all possible initial offsets between the network and node schedule.

For a given initial offset, the parameters influencing energy consumption and the joining delay are the following:

• joining strategy,

• strategy for sending beacons, • DC j , the radio Duty Cycle of the joining node, • DC n , the radio Duty Cycle of the node sending beacons (network Duty Cycle).

• SDC j (respectively SDC n ), the Slot Duty Cycle of the joining node (the network Slot Duty Cycle, respectively). This section gives the details of the strategies for sending beacons and joining with which we compare the proposed scheme. They are all adapted to operate in TSCH networks. The adaptation consists first of differentiating the role of a transmitter and a receiver for each strategy. During their active slots, nodes of the network transmit EB according to a TSCH transmission schedule. The joining node turns its radio on at the beginning of a slot and scans for the entire slot duration fixed to 10 ms. Slots in Searchlight-S are slightly longer than in other protocols due to handling slot non-alignment. Hence, we slightly increase the Searchlight receiving slot size. Moreover, while all other schemes only transmit one EB per slot, which strictly follows the TSCH timeslot template, we have modified the transmitting slot template for Searchlight-S so that a node will send two consecutive beacons.

Fig. 4 presents the schemes we use for comparisons for a target network slot duty cycle SDC n of 31% (a value just for understanding the principle), which corresponds to the {0, 1, 3, 9} mod 13 S-CDS sequence [START_REF] Gordon | La Jolla Difference Set Repository[END_REF]. To set all schemes on an equal basis for comparisons, we fix network slot duty cycle SDC n to the same value for all considered schemes. Note that the advertiser radio is not in Tx mode during the whole TSCH slot [1], leading to a difference between SDC n and DC n . From the joining node point of view, considering the radio duty cycle DC j or the slot duty cycle SDC j will not change the performance of most of the studied protocols since the joining node stays in Rx mode during the whole slot. Only Searchlight increases the slot size in Rx mode, so it will exhibit some difference between SDC j and DC j . Moreover, for some schemes, it is not possible to achieve the same value of SDC n : for instance, the Searchlight schedules have the form of SDC n = n : a smaller one (denoted by short) and a larger one (denoted by long) (see Fig. 4).

In B-Nihao, the joining node continuously scans for beacons, which is not suitable for most devices. Hence, we define another variant of B-Nihao denoted by DC-Nihao in which the joining node limits its scan to t consecutive slots and it distributes them over t repetitions of the schedule of size t, which results in the same duty cycle for the network and the joining node.

V. EVALUATION RESULTS

We start with the results for a network slot duty cycle set to SDC n = 1.6%, an arbitrary low value, and then present the comparisons for varying SDC n . A. Low Duty Cycle (SDC n = 1.6%) Fig. 5 Compared to the B-Nihao scheme (Short-Nihao and Long-Nihao), S-CDS achieves similar energy consumption. However, with respect to the joining delay, B-Nihao is significantly faster because the joining node in this scheme operates as an always-on device, which guarantees fast discovery, but may be impossible for battery-powered or energy harvesting nodes.

We can also see that for a similar joining delay, Searchlight consumes more energy than the proposed scheme, both for the average and worst cases. Furthermore, compared to the duty cycled version of Nihao, our scheme consumes a similar amount of energy, however, it achieves a slightly shorter delay, once again both for the average and worst cases. To summarize, our proposal achieves either lower energy consumption or shorter joining delay compared to other schemes for a low value of SDC Nihao correspond in fact to the same protocol, so they appear as one curve.

We can verify in Fig. 8 that the duty cycle of the joining node, imposed by a given advertising strategy, linearly varies with the network slot duty cycle for all schemes except for the scheme based on always-on scanning (B-Nihao) that results in the 100% duty cycle of the joining node. Searchlight has a slightly higher value of joining node radio duty cycle DC j due to an increased size of the listening slots.

Figs. 10 and 11 present the performance of the considered schemes for varying SDC n down to 1%. We can see that our proposal results in low energy consumption and short joining delay for really low duty cycles targeted in the Internet of Things (recall that 1% corresponds to an actual radio duty cycle of DC j ⇠ 0.5%). We can even achieve a value of SDC n close to 0.3% for S-CDS with parameters v = 86143 and k = 294, something really good for energy harvesting platforms.

Figs. 10 and 11 also confirm the previous results: the lower the duty cycle, the greater the gain of our proposal.

VI. CONCLUSION

In this paper, we have proposed to take advantage of Singer CDS for a joining scheme that results in low duty cycles. It distributes the active periods of nodes over time so that a joining node does not suffer from long scanning periods, in contrast to other schemes.

We have compared S-CDS through simulation with other state-of-the-art schemes adapted to TSCH networks: Searchlight [START_REF] Bakht | Searchlight: Won't You Be My Neighbor?[END_REF], B-Nihao, and a duty cycle version of B-Nihao [START_REF] Qiu | Talk More Listen Less: Energy-Efficient Neighbor Discovery in Wireless Sensor Networks[END_REF]. The comparison shows that S-CDS performs similarly to Searchlight in terms of the joining delay, while it consumes less energy with a reduced channel occupancy. Moreover, S-CDS achieves similar low energy consumption to the duty cycle version of B-Nihao and reduces the average joining delay. Thus, S-CDS stands as a suitable alternative to B-Nihao for devices with strong energy constraints such as energy harvesting nodes.

In the future work, we plan to implement and evaluate the S-CDS scheme on an experimental testbed and extend it to a multi-channel context to exploit TSCH frequency hopping capability.

  Cycle (SDC) = 2/t

Figure 1 :

 1 Figure 1: Searchlight-S principle. Anchor slots (A), Probe slots (P).

  b) Principle of B-Nihao for the target network slot duty cycle SDC of 1/t.

Figure 2 :

 2 Figure 2: Nihao principles. T stands for Transmitting, R for Receiving.

Figure 3 :

 3 Figure 3: Example for the perfect 7,3,1-CDS: {0,1,3}.

Figure 5 :

 5 Figure 5: Network radio duty cycle DC n (%): avg/min/max.

Figure 6 :Figure 7 :

 67 Figure 6: Joining delay (s): avg/min/max.

  Fig 4 also presents DC-Nihao: the joining node experiences the same slot duty cycle as the network, i.e., SDC j = SDC n , similarly to Searchlight and S-CDS.

n 6 Figure 10 :Figure 11 :

 61011 Figure 10: Joining delay of the considered schemes for varying network slot duty cycle SDC n .

  presents DC n , the network duty cycle corresponding to the proportion of the Tx time of the advertising network node.All values are similar except for Searchlight since the

		100
		80
	j (%)	60
	DC	40
		20
		0	0			10		20	30	40	50
								SDC	n (%)
	Figure 8: Joining node duty cycle DC	j vs. network slot duty
	cycle SDC	n .
	DC-N			B-Nihao		Searchlight	S-CDS
			Figure 9: Legend for Figs. 8, 10, and 11
	the SDC	n value of 1.6 divided by the radio Tx activity
	during a slot. Hence, we can find the expected value with
	the expression:
					DC	n = SDC	n ⇥	4.256 10	⇠ 0.68%.
	Note that this expression cannot be applied to Searchlight,
	since a node transmits two beacons in a slot, which gives
	the value of DC Figs. 6 and 7 present the performance of the considered n ⇠ 1.36.
	schemes for given SDC	n = 1.6%: the joining delay and the
	Rx time for a joining node.
								DC	n and SDC	n parameters are tightly linked for most
								schemes: the actual radio duty cycle DC	n is equivalent to


Damien Clergeaud
email: damien.clergeaud@inria.fr

Joan Sol Roo
email: joan-sol.roo@inria.fr

Martin Hachet
email: martin.hachet@inria.fr

Pascal Gui
email: pascal.guion@inria.fr

Towards Seamless Interaction between Physical and Virtual Locations for Asymmetric Collaboration

Keywords: Human-centered computing →Collaborative and social computing devices, Mixed / augmented reality, Virtual reality, Mixed Reality, Virtual Reality, Spatial Augmented Reality, Tangible User Interfaces, Asymmetric Collaboration, Head Mounted Display

Virtual Reality allows rapid prototyping and simulation of physical artefacts, which would be di cult and expensive to perform otherwise. On the other hand, when the design process is complex and involves multiple stakeholders, decisions are taken in meetings hosted in the physical world. In the case of aerospace industrial designs, the process is accelerated by having asymmetric collaboration between the two locations: experts discuss the possibilities in a meeting room while a technician immersed in VR tests the selected alternatives. According to experts, the current approach is not without limitations, and in this work, we present prototypes designed to tackle them. e described artefacts were created to address the main issues: awareness of the remote location, remote interaction and manipulation, and navigation between locations. First feedback from experts regarding the prototypes is also presented. e resulting design considerations can be used in other asymmetric collaborative scenarios.

e collaboration between a physical meeting room and a digital mock-up is supported thanks to di erent artefacts that provide users di erent degrees of immersion into the remote scene.

INTRODUCTION

In the industrial context, Virtual Reality (VR) is more and more used to support the design and iteration of products (CAD reviews, ergonomic study, assembly task design, among many others). Compared to physical prototypes, virtual environments enable engineers to test solutions faster, safer, and cheaper. Moreover, in some domains such as in the case of the aerospace industry, all the products are designed digitally with CAD so ware, which facilitates the use of VR. On the other hand, the design of complex artefacts involve multiple iterations based on decisions discussed by multiple stakeholders, which still require physical meetings.

e need of both physical meetings and VR prototyping leads to asymmetric collaboration. Indeed, the combination of both physical and virtual spaces could not be replaced by co-locating all the participants: immersing all the users in a virtual environment would break the meeting dynamics, while keeping the operators in the meeting room would greatly reduce the experimentation possibilities. As a result, collaborators with di erent roles at di erent locations must e ectively communicate in order to successfully achieve their objectives and sometimes have to move between virtual and physical spaces.

e question regarding asymmetric collaboration was brought to us by engineers from Airbus Group, a mayor aerospace manufactoring company. ey use VR to design assembly tasks directly with the nal operator immersed in the digital mockup, while experts supervise and guide the process from a meeting room. In order to follow the operator's work, experts can observe him or her through a monitor located at the meeting room, while an audio channel supports the communication between the two locations. For instance, experts could design a procedure to mount a particular system in the launcher while the operator is following the procedure to complete its design.

e engineers from three di erent branches of Airbus Group agreed on limitations of the current approach for asymmetric collaboration.

eir main concerns orbit around the fact that the viewpoint and the audio channel do not support awareness and communication properly. First, it is not uncommon that the experts forget the presence of the operator, since they work in parallel. Second, they struggle to provide instructions for precise or complex tasks. Finally, there are instances where being temporarily present at the remote location (in either direction) could ease the understanding between participants.

e purpose of this work is to provide tools that address the limitations of the current approaches for asymmetric collaboration, in order to ease the communication between these remote locations.

is involves i) supporting awareness between spaces, ii) tools that support remote operations, and iii) ways to visit the remote location. To do so, we choose to focus on the creation of rough-e-Lens technique (TTL) artefacts for both the physical and virtual locations.

e contributions of the current work are (Figure 1): 1) the conception and prototyping of tangible Mixed Reality lenses -and their virtual counterparts -for asymmetric collaboration, 2) the description of the system that supports these artefacts, and 3) preliminary feedback from future end users of the aerospace industry.

RELATED WORK

is work is at the intersection between 1) TTL for Virtual Reality, 2) linking physical and digital information, and 3) tele-presence technologies. is section brie y explore these research areas.

rough-e-Lens techniques (TTL) allow connecting spaces together. More formally, TTL enable users to simultaneously explore a virtual environment from two or more di erent viewpoints as described by [START_REF] Stanislav | Application and taxonomy of throughthe-lens techniques[END_REF]. If the second viewpoint is linked to the location to another immersed user, it provides a new channel for communication, as proposed by Kunert et al. with Photoportals [Kunert et al. 2014]. Photoportals are a mix between viewports and portals with a collaborative purpose, enabling users to create at (2D) or volumetric (3D) viewports to observe a remote location or to directly teleport themselves through it. It can also be used to retrieve remote objects, reducing the perceived distance between locations.

Instead of bringing the user inside the virtual space, it is possible to merge virtual and physical environments, notably through the use of projection [START_REF] Bimber | Modern approaches to augmented reality[END_REF]].

e O ce of the Future [START_REF] Raskar | e o ce of the future: A uni ed approach to image-based modeling and spatially immersive displays[END_REF]] envisioned to turn everyday spaces into CAVEs, which was then implemented using Spatial Augmented Reality (SAR) [START_REF] Jones | RoomAlive: magical experiences enabled by scalable, adaptive projector-camera units[END_REF]. is technique enables the creation of interactive augmented objects and tools. Even when SAR has limited display capabilities, they can be complemented using seethrough devices [START_REF] Benko | Fovear: Combining an optically see-through near-eye display with projector-based spatial augmented reality[END_REF][START_REF] Billinghurst | e magicbook-moving seamlessly between reality and virtuality[END_REF]. Another complementary way of bridging the distance between physical and digital spaces are Tangible User Interfaces (TUIs) [START_REF] Kenneth P Fishkin | A taxonomy for and analysis of tangible interfaces[END_REF], which provide physical handles to digital information. TUIs can be used in combination with screens (as with the classical example from Hinckley et al. [START_REF] Hinckley | A threedimensional user interface for neurosurgical visualization[END_REF]), in VR spaces (as with Specimen Box [START_REF] David | Specimen Box: A tangible interaction technique for world-xed virtual reality displays[END_REF]), or in combination with SAR (physical-virtual tools from Marner et al. [START_REF] Michael R Marner | Physical-virtual tools for spatial augmented reality user interfaces[END_REF], among many others). As a result, users can experience embodied interaction with digital content.

anks to the advances in sensing technologies, remote physical elements and locations can be digitalized [START_REF] Orts-Escolano | Holoportation: Virtual 3D Teleportation in Real-time[END_REF], extending the reach of the previous tools from purely digital content to any digitalized content. In this line of work, researchers are exploring ways to combine physical and digital. Examples include the digital navigation of the physical environment [START_REF] Komiyama | JackIn Space: Designing a Seamless Transition Between First and ird Person View for E ective Telepresence Collaborations[END_REF], asymmetric views of a digital scene [START_REF] Ibayashi | Dollhouse VR: a multi-view, multi-user collaborative design workspace with VR technology[END_REF] or combination of both [Roo and Hachet 2017a,b].

Close in spirit to this work is the interactive tangible window [START_REF] Angelini | Testing the tangible interactive window with older adults[END_REF]], which combines TTL, physical supports and telepresence. It was designed to ease the use of video-call applications for eldery adults. Users can then interact with remote locations, making the distance disappear thanks to the interface, while the interaction is framed into the physical environment.

To summarise, much e ort have been done to combine physical and digital, locally and remotely. We propose to extend this line of research by supporting the asymmetrical collaboration between physical and digital spaces, using both traditional VR and tangible metaphors, as described in the next section.

PROPOSED METHOD

In order to facilitate the asymmetric collaboration between physical and virtual locations, we propose to support three core features (Figure 2): 1) awareness through overview of the remote scene and collaborators; 2) the ability to remotely interact and manipulate elements; and 3) the capability to navigate between locations.

With these objectives in mind, we created artefacts that support the required features, using either SAR or VR. SAR and TUIs were used in the instances where immersion would break the dynamics of the local interaction. For the virtual locations, the interaction supports both tangible and purely virtual artefacts; these alternatives were created in order to enable more immersion or to free the

Awareness through Scaled Representations

In order to enable the communication between the two locations, it is rst necessary to have an overall understanding of the whole space and the location of each collaborator. For this reason, we decided to use World-In-Miniature [START_REF] Stoakley | Virtual Reality on a WIM: Interactive Worlds in Miniature[END_REF] as the starting point for interaction and communication. WIMs provide an overview of the context of the remote collaborators, while also supporting coarse interaction through pointing. Collaborators are displayed using avatars (rigged 3D scans [START_REF] Feng | Avatar Reshaping and Automatic Rigging Using a Deformable Model[END_REF]).

We implemented independent scaled down mock-ups for physical and virtual locations. e physical counterpart is supported by a physical mock-up (which is possible to 3D print thanks to the already available CAD information) with spatial augmentation generated via projection. Spatially augmented mock-ups work as ambient displays [START_REF] Wisneski | Ambient displays: Turning architectural space into an interface between people and digital information[END_REF]], its always-available subtle information makes them ideal to keep the users aware of the remote activity without being too distracting. In VR, the WIM displays the remote table and its surroundings, immersed users can hold a tangible prop to observe the remote place, and leave the prop on the workbench nearby. Alternatively, immersed users can interact with a virtual WIM (i.e., without a physical support).

When building physical mock-ups, both limitations and opportunities arise given the intrinsic physical properties. In the case of the launcher mock-up, two complementary views are necessary: an overview of the whole launcher and a detailed overview of the working piece. is was reproduced in our case with two separated mock-ups (Figure 3-le ): the rst one showing the location of the active section, while the second one shows combined inside-out and top-down views of the active room.

Interaction through Windows

Windows provide lenses to other spaces from given points of view, enabling interaction through them, as with traditional desktop screens. e main advantage of windows and their relative small size is the possibility of using several of them simultaneously.

We support two types of windows: interactive paper and portalrings. e former provides a see-through view of the scene, allowing to display mid air information at the meeting room location much like a see-through tablet, as provided by [ANONYMOUS-Paper]. Portal-rings are hollow frames that display the remote location, and enable interaction through them. Users can pass their hands to interact with the other side, and move elements between locations (Figure 3-center). Windows then provide the possibility to observe and interact with the other side, allowing a be er communication between locations.

Navigation through Doors

Doors are similar to windows, but besides providing a viewpoint of the remote location, they also enable to go there. Doors and teleportation are fairly common in VR, in particular to deal with limited physical spaces. In our context, we place a virtual door at a physical wall of the meeting room thanks to projection (Figure 3right). Regarding the navigation, the user immersed in VR does not need additional tools, as portals are a commonly used technique. For the users at the meeting room, the door is displayed on a wall using projection while the navigation is performed in VR, by wearing an HMD. Alternatively, the door could be located on a nearby space with CAVE capabilities, thus the process of walking to the door could provide a seamless transition into a dynamic VR space.

Once users transited to the remote location, they can directly interact with its virtual version. Displaying tele-presence collaborators in VR is done by showing their avatar, while in the meeting room is necessary to use an additional display.

SYSTEM IMPLEMENTATION

e prototype was implemented as an extension of [Roo and Hachet 2017a]. It is comprised of peer applications connected using UDP and OSC (real-time control protocol built over UDP). In each location, the hardware comprised of Optitrack Flex cameras, HTC vive, and optionally projectors. Both applications are identical, except by the hardware con guration; this design decision supports the creation of a topology of locations interconnected through artefacts, yet the artefact con guration and networking require further consideration. e audio communication was not explored for the current version of the system.

FEEDBACK FROM PARTNERS

A er the design and implementation of the prototype, we performed a demo session with the three engineers that brought the use case to us. e engineers were presented with the features of the system one by one, following the structure of this paper, from the meeting room side (since the VR interaction is closer to their expertise); one of the researchers was immersed inside the launcher mock-up from a nearby room.

e physical WIM was perceived as a good way to be aware of the remote location, placing the operator literally at the center of the table. e use of 3D printing created mixed emotions, and the conclusion is that their utilisation will depend of the use case (e.g., good for training since it is reused, not good for daily meetings).

e manipulation of the WIM while immersed was enjoyed yet rapidly discarded as impractical given its weight, preferring the use of the pure virtual WIM.

Regarding the portal-ring, the engineers found the possibility of taking objects from the other location of great use, and the gesture of bringing the object through the portal was intuitive. On the other hand, holding the ring was once again seen as unpractical, and they preferred the virtual version. e use of paper-windows was rapidly understood and they envisioned this the easiest to adopt through the use of tracked tablets. is was particularly appreciated when interacting with the WIM in particular, and more generally with all the digital objects, like the ones taken through the portal-ring.

e door was the most appreciated artefact, since it allows the operator to come into the meeting room, while the navigation into the other direction was not consider novel. When presented with the door, they envisioned how to improve their current work ow using it. Concretely, operators follow strict step-by-step protocols to prevent mistakes, so they need to keep the virtual scene uncluttered; being able to do back and forths to the meeting room enables them to focus on one task at a time, while the experts can coordinate the whole process. In their context, the use of the door to move elements between locations was be er suited than portal-rings.

Regarding the technologies involved, the engineers mentioned limitations on both. e VR helmet was perceived as cumbersome to utilise and equip. ey considered the extension of the system to support a lighter augmented reality helmet such as Hololens, while they also were aware of the loss of resolution and FOV implied. Regarding SAR, on one hand they liked the un-instrumented interaction, yet the use of at augmented surfaces was limited, and they would prefer richer rendering. An interesting conclusion they reached is that not all experts will use the same modalities, and the limitations of one technology can be mitigated with the other.

CONCLUSION

is work was inspired by the current limitations in asymmetric collaboration expressed by industrial engineers. Based on the literature, we created artefact prototypes to improve the awareness, communication and interaction between locations. Finally, we presented these prototypes to engineers in order to get feedback.

From the proposed solutions, the use of windows and doors where the two preferred features. Windows were considered to complement the current approach, while also being easy to adopt. Regarding the doors, they envisioned how they could improve the existing work ows. Interestingly, the tangible physical TTLs were instantly understood, yet quickly discarded for practical reasons. We consider this does not suggest that tangibles should be avoided when designing prototypes, quite the opposite. eir use in early stages can lead to a be er understanding of the interaction metaphors, to then be replaced with purely virtual widgets.

We consider that the proposed interaction techniques and artefacts can be extended to other contexts, and are not limited to SAR-VR collaboration. Indeed, the presented interactions could be used between any two locations, each of them either physical (digitalized) or virtual. Our conclusion is that, instead of trying to provide a single space that supports all the interactions, it is preferable to have several spaces with speci c aims, even when these locations are only virtually separated.

  Figure 1:e collaboration between a physical meeting room and a digital mock-up is supported thanks to di erent artefacts that provide users di erent degrees of immersion into the remote scene.

Figure 2 :

 2 Figure 2: e artefacts bridge the distance between the local and remote locations, enabling progressive immersion and interaction on the other side, up to the point of going there.

Figure 3 :

 3 Figure 3: Pictures and virtual views of the artefacts from the meeting room.

ACKNOWLEDGMENTS

is work was made possible thanks to Airbus Group, and the ISAR project (ANR-14-CE24-0013).