Yann Busnel
email: yann.busnel@irisa.fr

Marin Bertier
email: marin.bertier@irisa.fr

Anne-Marie Kermarrec
email: marie.kermarrec@inria.fr

SOLIST or How To Look For a Needle in a Haystack? A Lightweight Multi-Overlay Structure for Wireless Sensor Networks

In this paper, we consider sensor database systems. Sensors are attached to objects and queries on the objects are operated at the sensor network level. Although queries to such a system might be extremely complex, ensuring efficiently basic functionalities such as broadcast or anycast without any central element is not trivial. In this paper, we provide a suite of *-cast (anycast, k-cast, broadcast) functionalities in a fully decentralized manner. More specifically, we present the design and evaluation of SOLIST, a multi-layer structure for sensors, largely inspired from structured peer-to-peer systems providing such functionalities. The main goal of SOLIST is to limit the overall energy consumption. A type is associated to each sensor, and the *-cast functionalities are implemented at a type granularity regardless of the number of types and their distribution within the network. A typical use of such a system is sensor-based stock management. We evaluate SOLIST through simulations and show that SOLIST achieves a reasonable tradeoff between performance and energy consumption.

I. INTRODUCTION

Looking for a specific information in a large-scale network with no underlying structure is as difficult as searching a needle in a haystack without any metal detector. The most natural way to explore the network is flooding. Yet, this is not desirable in wireless sensor networks (WSN) for which energy saving is a first-class concern. WSNs are composed of a large number of small entities, with much less capabilities than common computers. Due to their tiny size, these entities, equipped with a wireless communication facility and called sensors in the following, possess slim resources in terms of memory, CPU, etc. [START_REF] Akyildiz | A Survey on Sensor Networks[END_REF], [START_REF] Rentala | Survey on sensor networks[END_REF].

As opposed to general-purpose large-scale distributed systems, WSN are deployed and configured usually to fulfil a specific application needs. Example of such applications are monitoring, stock management, data aggregation, etc. Yet some basic functionalities are common to a large number of those applications. We consider applications in which sensors are associated to a specific type. A typical example is stock management. Each sensor belongs to a given type, which can dynamically change with respect to application needs or execution. At the heart of data management, we have identified a set of communication primitives that can be seen as basic building blocks for those applications. We call the *-cast suite, this set of functionalities, which consists in: anycast, broadcast and k-cast queries that aim at reaching respectively one, all or k entities of a given type (where k is a given parameter of the k-cast primitive). To illustrate our purpose, consider a stock management application, where each sensor represents a physical item of a given type. Sending a message to all the sensors of a given type or querying the system to know whether there still exists an instance of a given type, are standard operations. The aforementioned *-cast suite would provide the means to implement easily such operations.

In this paper, we present the design and evaluation of SOLIST (Self-Organized Large-scale and lightweight Information-based Sensor Technology), a structured overlay network for WSN providing an efficient *-cast suite. Based on a simple common interface, SOLIST provides a generic infrastructure, relying on a lightweight multi-layer structure, while ensuring low energy consumption. Sensors are clustered according to their type into specific layers. In this paper, due to space constrains, we only present the anycast operation. Note that this operation can be used to provide an entry point to a specific type layer and therefore implement in those layers the k-cast and the broadcast [START_REF] Busnel | A Lightweight Multi-Overlay Structure for Wireless Sensor Networks[END_REF].

The rest of the paper is organized as follows. In Section II, we briefly introduce the generic interface. The SOLIST design is presented in Section III. In order to evaluate SOLIST, we conducted simulations in worst-case scenarios and compared it against traditional approaches. We present the experimentation results in Section IV. Finally, Section V briefly surveys the related works before concluding in Section VI.

II. THE *-CAST SUITE

As mentioned before, a large majority of distributed applications relies on a few basic functionalities. More specifically, in WSNs, accessing application nodes according to their type is a common task in many applications. SOLIST relies on a group-based structure to provide a basic set of functionalities, identified as *-cast in the sequel. Nodes may be assigned to a given type. This type may be static (representing the shape of the sensor in case of heterogeneous network for instance) or dynamic (related to the level of energy available, the sensed data, etc.). Note that some nodes may not be directly assigned to a specific type, and thus contribute only to the global connectivity of the network. SOLIST ensures that every nodes of the same type are dynamically clustered Node i sends its request for layer 1 to the nearest entry point: ep 1(2) together. Our system allows to find efficiently a node from a given type, and to navigate easily between all nodes sharing the same type. SOLIST can be adapted to any application by adapting the matching between types and nodes. SOLIST provides the following set of core functionalities, common to many applications: Anycast [ANYCAST(type)] This service aims at reaching one node, if any, of a specific type. For example, this functionality may be used to discover if one instance of a given type exists in a system, and to localize it. k-cast [KCAST(type, k)] This service aims at reaching k nodes, which belong to a specific type, should they exist. This function returns TRUE if they are at least k nodes of the specific type, FALSE otherwise. Moreover, this operation provides a direct access to those k instances, although we could consider attaching more information into reply messages. For instance, in stock management applications, it is useful to know if entities of a specific type are available in sufficient quantity. In fire monitoring applications, such applications trigger an alert if say 10 sensors have sensed a temperature greater than 40 degrees, or a hygrometry value lower than 2 %vol. Furthermore, firemen may also be want to be informed of the average value of a random sample of nodes sharing the same type. k-cast might be used to perform these tasks. Broadcast [BROADCAST(type)] This service aims at reaching all nodes belonging to a specific type. Using this functionality, SOLIST may reach all nodes belonging to a a specific type of nodes, this last service can be viewed as a multicast one. Such a functionality may be used either to disseminate information to every nodes of a given type, as in a publish-subscribe systems for example. It can also obviously be used to enumerate the number of nodes of a given type.

III. SOLIST CORE

A. A multi-layer structure

In order to provide the *-cast suite, SOLIST is built upon a multi-logical layer structure, clustering the network according to nodes' type. This allows navigating between nodes sharing the same type and provides an efficient localization based on entry-points (cf. Section III-C). Each node belongs to the common basic layer, used essentially to ensure the global con-nectivity of the network. To this end, each sensor is aware of its own virtual coordinate in a relative Cartesian space. Messages in the basic layer are routed using a lightweight geographic routing protocol. This enables to reach any destination based only on its virtual coordinates.

The multi-layer structure provides a logical clustering of the network. On top of this ground layer, SOLIST implements a specific lightweight overlay per group. For instance, in Figure 1, n nodes are spread between three different types. For each type corresponds a specific overlay (i.e. the triangle one, the circle one and the square one) on top of the ground layer. Communications between two nodes of a specific overlay are implemented using the ground layer.

B. LIGH-t-LAYER structure

Each of the aforementioned logical layers has the same framework, based on rectangle-shape space division. In this respect, WSNs are similar to peer-to-peer (P2P) overlays [START_REF] Busnel | GCP: Gossip-based Code Propagation for Large-scale Mobile WSNs[END_REF] (in term of properties and functionalities). Thus, the proposed structure is largely inspired from a classical P2P Distributed Hash Table (DHT), namely CAN [START_REF] Ratnasamy | A scalable content-addressable network[END_REF]. A previous work on evaluation of P2P structured overlays for multicast [START_REF] Castro | An Evaluation of Scalable Applicationlevel Multicast Built Using P2P Overlays[END_REF] shows that CAN provides an ideal structure for our targeted functionalities in a WSN. In a nutshell, CAN splits the space into logical responsibility areas, evenly spread between nodes in the system. To maintain this structure, each node owns a virtual neighborhood, corresponding to the representatives of its own zone's adjacent areas. We slightly modify this skeleton to match the WSN setting. The main particularity of this context is that communication and energy constraints have to be considered in priority. We denote this revised structure by LIGH-t-LAYER in the following, where t corresponds to the type t shared by the nodes in this layer. Note that in our system, each node maintains the same virtual coordinates for any overlay it belongs to and the responsibility areas are only used for k-casting and broadcasting efficiently in a group.

Let us introduced how this network is gradually built. Initially, the first joining node of a given type t becomes responsible of the whole LIGH-t-LAYER area. When another node joins the network, it contacts the representative of the area responsible of its coordinates. This area is split between In order to illustrate a LIGH-t-LAYER structure evolution, Figure 3 presents different events from the start. First, node A joins the network and becomes responsible of the whole logical area. Figure 3.a shows the state of the layer after B's integration: it initially contacts A, which splits its own area in two and then, returns the coordinates of (i) the B's area and (ii) the created frontier between them. Later, at C's arrival, B splits its own area and stamps the new frontier by a strictly greater identifier as shown in Figure 3.b. Finally, Figure 3.c presents the layer structure state incorporating 9 nodes, labelled from A to I. In that case, we observe that the largest frontier stamp is equal to 5.

The bottom part of Figure 3 presents how to keep a consistent structure in case of a node departure (cf. Figure 3.d) or a failure (cf. Figure 3.e). Departures and failures are handled the same way in LIGH-t-LAYERs. When a node chooses to leave the overlay, it sends its view t to the representatives across the last created frontier. These last are potentially several, as across the tag-4 frontier in Figure 3.c for instance. Thus, these nodes get the responsibility of an extended area, update their view t according potential new neighbors, stretch out their frontiers and finally, send updated information to the concerning neighbors. For instance, node C, in Figure 3.d, has to leave the layer. C sends its view t to node I across its tag-3 frontier (here, for node C, 3 is the highest frontier stamp). Then, I becomes the representative of the merged area: C's union I's one. Finally, I updates its view t according to the new extended frontier with B's area, and sends the new coordinate to B.

In parallel, in case of failure, as presented in Figure 3.e, node F is removed from SOLIST without warning. F can obviously not send its own view t to any neighbor, as in the leaving procedure. Also, we integrate a supervision mechanism in our structure. Each node, which belongs to an overlay, periodically check upon one or two of its neighbors to prevent failures. This supervision links are represented by bold arrays in Figure 3. Thereby, node D, which is the F 's supervisor, sends a collectView request to learn a posteriori the F 's view t . This request is routed all around the past F 's area and finally, comes back to D. Using this information, D falls trivially into a classical leaving procedure: it contacts all nodes across the deleted frontier (here, node H besides itself) and merges the corresponding F 's sub-area with its own one. Figure 3.f presents the state of this LIGH-t-LAYER structure once those actions have been performed.

However, in order to take advantage of this overlay structure, we require an efficient and robust way of reaching a specific LIGH-t-LAYER from anywhere in the network. This is the goal of the following subsection.

C. Linking the world: Entry points

A challenging issue remains to reach a specific LIGH-t-LAYER from any node, without any other information than the type t identifier. To this end, we map a logical namespace on top of the ground layer, inspired by recent works [START_REF] Ratnasamy | Data-Centric Storage in Sensornets[END_REF]. In addition, we use two mutual hash functions in order that each node shares a set of common coordinates in this namespace, computed using these functions. The aim of these hash functions is to uniformly spread these coordinates in the space, based on the number of types. In the following, we denote these coordinates as entry points.

Let t correspond to the type identifier of the searched LIGHt-LAYER. Let f x : N → [0; 1[ and f y : N → [0; 1[ be two hash functions and wsX, wsY the respectively horizontally and vertically size of the relative Cartesian space. Entry point coordinates corresponding to this layer (denoted by ep t ) are computed as follows:

ep t = (x, y) where x = f x (t) × wsX y = f y (t) × wsY (1)
As f x and f y are shared by all nodes, entry point coordinates in the network are unique for a given type t. However, as an entry point is represented by its uniformly random generated coordinates, there might not be any node at this specific location. Therefore, we consider no distinction between a point in the virtual space and the nearest node of this point. Both are called entry point in the sequel. This nearest node of ep t has to be acquainted with at least one node of type t (and so, to be aware of the existence of the corresponding LIGH-t-LAYER). If this LIGH-t-LAYER exists, it is able to reply with the identifier and the coordinates of a node belonging to this layer. In the following, this node replied by an entry point is denoted a contact node.

In order to balance the load of the nearest node to an entry point and to avoid that some requests have to traverse the whole network to reach an entry point, the namespace is divided according to a m×n grid, on x and y coordinates. Then, the namespace is mapped onto each division, which are called cells in the following. When a node wants to access a specific layer, it sends its request to the nearest entry point of the given type. For instance, Figure 2 presents a m × n = 3 × 2 cell topology with 5 identified types. For each cell, 5 entry points (et 1 to et 5 ) have the same relative position. Here, node i sends a request to access the layer associated to type 1. i is aware of all the 6 entry point location (dash and solid arrows) and sends its request to the nearest one (here, ep 1(2) linked by a solid arrow). Let d(•, •) : (R×R) 2 → R the Euclidian distance between two points in the virtual space and csX, csY the cell size respectively horizontally and vertically. To find the nearest entry point, node i has to compute the Equation 2 calculus. Let the two sets Γ

x,t = {(k x + f x (t)) × csX|k x ∈ [0..m -1]} and Γ y,t = {(k y + f y (t)) × csY |k y ∈ [0..n -1]} ep t = (x, y) st. d(i, (x, y)) = min x ′ ∈ Γx,t y ′ ∈ Γy,t d(i, (x ′ , y ′ )) (2)
Last but not least, considering this searching layer mechanism, in order to update the entry points' knowledge, when a node joins a specific LIGH-t-LAYER, it sends its arrival information to the nearest type t entry point. Therefore, this node is always informed of the nearest node belonging to the given LIGH-t-LAYER layer. Thus, it can send information up-to-date about a close node when a "search layer request arrives". Likewise, in case of failure or departure, entry points are informed too in order to update as well their contact node links. As entry points choose locally their nearest contact node, the leaving/faulty node is not aware of the entry point referenced. So, all entry points have to be informed of each change in the network. This is precisely this mechanism, which is used to reply to anycast requests.

IV. EVALUATIONS a) Simulation environment:

We evaluate SOLIST with SeNSim, a discret event simulator developed by the ASAP/IRISA project team [START_REF] Sensim | [END_REF]. SeNSim allows analysing SOLIST under different topologies, and with different failure and stimulus scenarios.

We consider a 1,000 sensor network, sensors are spread uniformly in a square area of 96×96 meters. The transmission range of a sensor is 0,7 meter. The repartition of sensors into 10 types is static (10 nodes of type 1, 30 of type 2, 50 of type 3, . . ., 190 of type 10),

In each evaluation, if not specified otherwise, each node joins the network, launches a broadcast and a k-cast1 , and finally leaves the network. Arrival and departure dates are randomly generated, as well as the requested type for broadcast and k-cast. The k value is picked at random between 1 and 200, in order to get some true and false replies.

b) Routing protocol: SOLIST structures the network to localize a given sensor type in the network. From SOLIST, a sensor obtains the coordinate of the request destination. To be able to reach the destination, we use a light GPSR geographic routing protocol [START_REF] Karp | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[END_REF]. We don't use the computation of planar graph required by the original algorithm because this computation requires non-negligible energy consumption and we want to focus the energy consumption measurements on SOLIST only. Therefore, we only use the greedy routing protocol with the right-hand rules in case of void density on a route. c) Algorithms comparison: We compare the *-cast algorithms build on SOLIST against two existing protocols: (1) anycast against the simple but naive Random Walk mechanism to find one node of a specific type in an unstructured network and (2) Flooding for broadcast. Using (1), the node sends a request to one of its direct neighbors (i.e. in WSN context, one of the nodes in its transmission range). If this node belongs to the requested type, it sends to the initiator its position. Otherwise, it randomly chooses a node among its neighborhood (except the previous sender), and sends the request to it, and so on. After a predefined number of hops, if no node is found, the last request receiver replies a NOT_FOUND message to the initiator.

d) SOLIST's anycast: We evaluate the SOLIST's anycast mechanism along two metrics:

• the distance between a node and the anycast destination;

• the distance between a node and its closer entry point. Figure 4 presents the average distance between the anycast query initiator and the contact node with the requested type for several numbers of cells configuration. For comparison, we also represent the average distance between the initiator and the destination and the distance obtained with Random Walk.

The contact node provided by SOLIST is the closest node known by the entry point contacted by the initiator. Consequently the lower the cell size, the nearer the contact node. A side effect can be observed for huge number of cells, where the SOLIST anycast plot slightly grows up. Effectively, when a node joins a layer, it informs the nearest corresponding entry point. So, as the cells size decreases, some entry point may be nearer to the new node, without being aware of its arrival (we avoid broadcasting all entry points at each arrival to reduce energy consumption).

Figure 5 presents a cumulative distribution function (CDF) of this distance for a 5×5 cells configuration in SOLIST against an average random walk approach. In these simulations, more than 95 % of nodes with SOLIST have a distance less than 13.5 meters, while only 80 % fulfil this criterion when the random walk approach is used. Furthermore, the tail of SOLIST plot shows that all nodes have a distance less than 62.5 meters while the random walk mechanism results in a maximum distance of 89, which is about the size of the simulation environment.

e) Entry point distribution: Another interesting metric to evaluate the SOLIST anycast mechanism is the distance between a node and the nearest entry point. Figure 6 presents the average value of this distance and the standard deviation according to the number of cells. The distance is represented as in previous figures with the Euclidian one, and also with the number of hops needed to reach the entry point. As predicted, the greater the number of cells, the smaller the cells size and the nearer the entry point. An interesting point is that from minimum 6 cells, the average number of hops is lower than 3 hops. In consequence, energy consumption spends to reach a contact node is low. Figure 7 presents a CDF of these two distances for a 5 × 5 configuration in SOLIST. 90 % of nodes can reach the nearest entry points in at most 1.5 hops 2 , and 98.5 % by at most 2.5 hops. In this experiment, each cell has a 20 × 20 square meters size. No nodes are at a distance to an entry point of more than √ 2×20 meters (the diameter size of a cell) as predicted, but some are at a distance between √ 2 × 20 and

√ 2×20 2
: these nodes are the ones, which are located on the border of the network. They have fewer choices for entry points than nodes located in the centre of the network.

f) SOLIST energy consumption: In order to evaluate and compare SOLIST, we have run several simulations with the same network behavior (as join date, leave date, failure date, number of events, etc.) Each simulation lasts 10,000 discrete times. Each node joins the network once and leaves or fails before the end of the simulation. Each node sends one broadcast and one k-cast request. As each join or *cast request needs one anycast mechanism, these workloads consists in 3,000 anycast, 1,000 broadcast, 1,000 k-cast 1 . Moreover, join, leave and maintenance consumption have to be taken into account. To imitate real energy consumption, we use the power characteristics described in Table 8, proposed 2 these results are given for a round trip message divided by 2 in order to take into account the non-symmetric route from a node to another with GPSR.

in [START_REF] Mainwaring | Wireless Sensor Networks for Habitat Monitoring[END_REF] from MICA nodes measurement. We consider that each node has a full battery of 2,200 mAh at the beginning of the simulation.

Figure 9 presents for several cells configuration in SOLIST, the average total energy consumption at the end of the simulation against the one generated using random walks and flooding. This demonstrates the efficiency of SOLIST in saving energy for the whole network. The consumption in SOLIST is slightly increased according to the number of cells, due to the consumption needed for maintenance as we see below.

Figure 10 presents for several cells configurations in SOLIST and random walk, the average anycast energy consumption and Figure 12 and 13 present the end simulation energy snapshot respectively for SOLIST and Random Walk. The first one shows the interest of SOLIST by using at least 3 cells in this network topology. As tiny cells do not answer every time with the nearest contact point, the anycast mechanism increases slightly according to the cell size. Although, SOLIST anycast energy consumption required is no more than 35 % compare to the random walk mechanism. The two other figures present some compactness of higher consumption points. For SOLIST's anycast, these points correspond to the location of the 80 entry points in the system. We can easily infer the 8 cells from this figure. Contrarily, using the random walk mechanism, the point of higher consumption corresponds to the node with the highest density in the topology. This is due to the fact that requests have a higher probability to stay in this high-density neighborhood (random walks have a low probability of visiting low-density neighborhood). SOLIST is always lower than the ones observed using random walks.

Finally, average structure maintenance energy requirement is presented in Figure 11 according to number of cells in SOLIST. As join operations and reorganizations in case of failure are only a local task, the associated energy consumption remains low, strictly lower than 0.25 % of the total amount of energy available for each one. Leaving operations require more energy when the number of cells is growing. This observation is a consequence of the linear expansion of leaving messages to inform each entry points. For instance, in 10 × 10 cells configuration, as each node leaves or fails during the simulation, 100,000 leaving messages are generated among the network... The results show that SOLIST outperforms the considered alternatives with respect to energy consumption. For the topology considered for this evaluation (i.e. 1,000 nodes among 10 types), an 8 cells configuration is ideal to obtain the best tradeoff between efficiency and energy consumption.

V. RELATED WORKS

In this section, we present various works related to SOLIST. To the best of our knowledge, providing a common application-programming interface (API) for WSNs has not yet been proposed. Also, we are comparing the *-cast suite elements with previous works. These works address one of the several functionalities introduced in this paper. On one hand, we consider previous work on anycast in WSNs. For instance, in [START_REF] Thepvilojanapong | Hierarchy-based Anycast Routing Protocol for Wireless Sensor Networks[END_REF], authors propose an anycast routing protocols based on hierarchical tree. These works used a base station in order to build the routing tree. Although this is relevant in some contexts, SOLIST doesn't required any particular node and allow each node to consult information about the network. On the other hand, we consider works on multicast in WSNs. This can obviously be compared to a broadcast for a specific type of sensors in SOLIST. Several works have been proposed recently: an interesting result is presented in [START_REF] Wieselthier | Energy-efficient broadcast and multicast trees in wireless networks[END_REF]. This paper proposes a broadcast and a multicast mechanism for WSNs based on tree construction. A tree-based structure has to be built for each multicast group by deleting useless links from the broadcast tree. This system has been evaluated only on a small network. Moreover, the system does not consider node failure or departures. Another approach for multicasting in WSNs [START_REF] Chandra | Anonymous Gossip: Improving Multicast Reliability in Ad-Hoc Networks[END_REF] considers only reliability for any suitable multicast protocol, by lost message recovering and a last one [START_REF] Huang | Spatiotemporal multicast in sensor networks[END_REF] considers multicast on mobile sensors, which is not our context. The nearest contribution has been proposed recently in [START_REF] Flury | Routing, Anycast, and Multicast for Mesh and Sensor Networks[END_REF]. Authors proposed a routing protocol for anycast and multicast in WSNs. They present a theoretical analysis of their scheme, based on dominance net construction. This paper presents interesting results but relies on a different model. Moreover, dynamic multicast group management requires the construction of a minimum spanning tree for every group modification. Finally, no simulation or experimentation has been done to illustrate the theoretical results. So, comparison is hard, as we do not provide such theoretical results.

Finally, we must cite a relevant approach to deal with information in a WSNs. TinyDB [START_REF] Madden | TinyDB: an acquisitional query processing system for sensor networks[END_REF] is based on information acquisition directly on the network as us, but viewing the network as a physical database. Consequently, they propose a query language based on extension of SQL. As SOLIST, TinyDB is generic and represents an all-in-one solution for WSN application. TinyDB is application dependant according to query optimization and execution.

VI. CONCLUSION

In this paper, we propose an effective all-in-one solution for the *-cast suite (i.e. anycast, k-cast and multicast) in static WSNs. This contribution, called SOLIST, is a generic lightweight system architecture for large-scale WSNs. SOLIST is composed of a finite set of overlays (LIGH-t-LAYER) providing a common interface, with a type-based clustering. Associated with the proposed searching layer mechanism, SOLIST provides an efficient *-cast implementation in term of energy saving and reliability. We evaluate by simulation each functionality provided by SOLIST and we compare it against two other standard algorithms (flooding an random walk). Results demonstrate that SOLIST outperforms these algorithms in term of energy saving and therefore provides a good tradeoff between functionality and energy consumption.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Projection into layers

Fig. 3 .

 3 Fig. 3. Evolution of a LIGH-t-LAYER structure following different kinds of event

Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .

 4567 Fig. 4. Average distance of the contact node known by an anycast request.

Fig. 9 .Fig. 10 .Fig. 11 .Fig. 12 .Fig. 13 .

 910111213 Fig. 9. Average total energy consumption.

the algorithms of the *-cast suite. are presented in[START_REF] Busnel | A Lightweight Multi-Overlay Structure for Wireless Sensor Networks[END_REF]


Yann Busnel

Leonardo Querzoni

Roberto Baldoni

Marin Bertier

Anne-Marie Kermarrec

On the Deterministic Tracking of Moving Objects with a Binary Sensor Network

This paper studies the problem of associating deterministically a track revealed by a binary sensor network with the trajectory of a unique moving anonymous object, namely the Multiple Object Tracking and Identification (MOTI) problem. In our model, the network is represented by a sparse connected graph where each vertex represents a binary sensor and there is an edge between two sensors if an object can pass from a sensed region to another without activating any other remaining sensor. The difficulty of MOTI lies in the fact that trajectories of two or more objects can be so close (track merging) that the corresponding tracks on the sensor network can no longer be distinguished, thus confusing the deterministic association between an object trajectory and a track. The paper presents several results. We first show that MOTI cannot be solved on a general graph of ideal binary sensors even by an omniscient external observer if all the objects can freely move on the graph. Then, we describe some restrictions that can be imposed a priori either on the graph, on the object movements or both, to make MOTI problem always solvable. We also discuss the consequences of our results and present some related open problems.

Introduction

Context "Tracking the movements of anonymous objects and associating each object trajectory with an unique identifier" is a basic problem in many applicative contexts such as surveillance [START_REF] Oh | Tracking on a graph[END_REF], rescue, traffic monitoring [START_REF] Bloisi | A distributed vision system for boat traffic monitoring in the venice grand canal[END_REF], pursuit evasion games, etc. Tracking objects with a sensor network is a challenging task. Potential inaccuracy of sensors (e.g. [START_REF] Aslam | Tracking a moving object with a binary sensor network[END_REF]) and the complexity of the localization subsystem computability (e.g. [START_REF] Aspnes | On the computational complexity of sensor network localization[END_REF]) significantly complicate tracking initiation, maintenance and termination of object trajectories leading to false detection and missing observations.

Even without considering false detections and missing observations, the problem of associating an unique identifier to a track corresponding to the trajectory of one object is difficult due to the potential merging of tracks. This may confuse this association if sensors do not have adequate capabilities [START_REF] Liu | Distributed group management for track initiation and maintenance in target localization applications[END_REF]. In other words, two tracks may be so close to each other at a certain time that they become indistinguishable, and then impossible to identify after splitting. Deciding, after a track merging, what is a relevant association among multiple hypothesis is usually achieved by looking at the behaviors of tracks before the merging happened [START_REF] Liu | Distributed group management for track initiation and maintenance in target localization applications[END_REF]. In the following, we refer to this one-to-one mapping between tracks and object trajectories as the Multiple Object Tracking and Identification (MOTI) problem.

We investigate MOTI by using a binary sensor network, which means that each sensor reports only a binary value indicating if an object is in its sensing region or not. The interest in focusing on such minimalist and simple devices is motivated by the fact that we want to study the essence of MOTI's solvability without looking at the powerfulness of sensors capabilities. As in [START_REF] Oh | Tracking on a graph[END_REF], in our model, the sensor network is represented by a sparse connected graph, namely the passage connectivity graph (PCG), where each vertex represents a binary sensor and there is an edge between two sensors u and v only if an object can pass from the sensing region of u to the one of v without activating any other remaining sensor.

Contribution In this paper, we show that it is impossible to solve the MOTI problem in a generic graph. To make the impossibility as strong as possible, this last is proved considering an omniscient observer that has complete knowledge of the state of the graph; moreover, we assume ideal conditions for object tracking such as perfect binary sensors (i.e. no false detections or missing observations), ideal coverage of the sensing areas (i.e. disjoint sensing regions), so that at each instant of time one object activates only one sensor and each sensor is activated by at most one object. We prove that the impossibility of solving MOTI is a structural problem that depends on the topology of the underlying passage connectivity graph. Then, we describe some restrictions that can be imposed a priori either on the graph, on the object movements, or on both, to make MOTI always solvable. More specifically, we show that if the passage connectivity graph is acyclic, MOTI can always be solved. Also, if the graph contains cycles with a length greater than ℓ, MOTI can be solved only if the maximum number of objects that can move concurrently is less than ℓ 2 .

Roadmap In Section 2, we discuss some related works. Section 3 introduces the system model. Section 4 defines the Multiple Object Tracking and Identification (MOTI) problem and shows that this problem is impossible to solve in a general setting. Section 5 gives two different characterizations of MOTI solvability, which are used in Section 6 to introduce some interesting classes of systems where the problem can always be solved. Finally, Section 7 concludes the paper.

Related Work

Tracking mobile objects through sensors is a problem with a large spectrum of applications [START_REF] Han | An algorithm for multiple object trajectory tracking[END_REF]. It is treated by the literature from various perspectives, but most of the works are concerned with the problem of correctly tracking one [START_REF] Aslam | Tracking a moving object with a binary sensor network[END_REF] or more [START_REF] Singh | Tracking multiple targets using binary proximity sensors[END_REF] objects in a network of binary sensors characterized by noise and false detections under various constraints (e.g. noise levels, power consumption [START_REF] Gui | Power conservation and quality of surveillance in target tracking sensor networks[END_REF], limited computational or network resources [START_REF] Liu | Distributed group management for track initiation and maintenance in target localization applications[END_REF], etc.). In our work, we take a more theoretical approach to the problem considering a setting characterized by a network of ideal sensors (no noise, no false detection, no limitation on communication) and show that, in the general case, it is impossible to correctly associate sensed tracks to moving objects. This result is a consequence of the possibility of track merging and splitting during the observation period [START_REF] Liu | Distributed group management for track initiation and maintenance in target localization applications[END_REF]: once two tracks have merged due to the excessive proximity of two objects, it is impossible to deterministically maintain the identity of the two objects once their tracks split again; To the best of our knowledge, this is the first work to thoroughly examine and discusse this issue as well as prove its strong impact on the general problem solvability.

Issues related to track merging and splitting are common to every setting where two or more objects can move freely. However, in order to provide the reader with proofs of our statements, in this paper, we limit the problem analysis to a specific environment where object movements are partially constrained, and that can be abstracted as a passage connectivity graph [START_REF] Oh | Tracking on a graph[END_REF]. Note that, despite the obvious limitations of this model, it still perfectly maps a lot of indoor applications like tracking the movements of people inside a building.

System Model

We consider a system composed of a set of generic objects moving in an environment where sensors can detect their presence. Such an environment can be modeled as a passage connectivity graph (PCG) G(V, E) where the set of vertices V represents binary sensors; it exists an edge e i,j ∈ E linking two vertices v i , v j ∈ V if and only if (iff ) it is possible for an object to move from the position where it is detected by the sensor v i to the one where it is detected by the sensor v j without activating, during the movement, any other sensor. We assume that, in the considered environment, movements are always possible in both directions. Therefore, the graph G is considered undirected. Moreover, we assume that there is always one single way to move from one position to another: only an edge can connect two distinct vertices in the graph. For each vertex v i , a special edge e i,i exists in E representing the possibility for an object to remain in the same position.

The set of moving objects {o 1 , . . . , o x } is denoted by O. Time is represented as a discrete and infinite sequence T = [t 0 , t 1 , . . .] of instants starting at t 0 . At every time instant, each object o occupies a position represented by a vertex v i ∈ V . The position of an object o at a specific time instant t is given by the function loc : T × O → V that returns the corresponding vertex v i . When an object, positioned on a vertex v i , decides to move to a new position, it can choose as its destination any vertex v j such that e i,j ∈ E; the set of possible destinations is returned by the function adj : G × V → P(V ). The movement of an object o at a specific time instant t is given by the function mov : T × O → E that returns the edge used for the movement e i,j where v i = loc t (o) and v j ∈ adj G (v i ).

We assume that, regardless of a node's position and movement, the two following conditions always hold in our system: ∀t ∈ T, ∀o i , o j ∈ O, (i) loc t (o i ) = loc t (o j ) (i.e. two objects cannot be located on the same vertex at the same time) and (ii) mov t (o i ) = mov t (o j ) (i.e. two objects cannot move on the same edge at the same time).

Each object o ∈ O moving in the system describes a trajectory. The trajectory described by object o between t i , t j ∈ T (with j > i) is defined as P ti,tj ,o = [v ti , . . . , v tj ] t t t t where

v t k = loc t k (o), k ∈ [i, j].
Given t i and t j , we define the global trajectory as the set containing all object trajectories. The global trajectory is denoted as P ti,tj = P ti,tj ,o o∈O , or simply P if the time interval is precisely defined by the context. A specific global trajectory P ti,tj is an element of P ti,tj , the set containing all possible global trajectories described by the objects in O on G during the period [t i , t j ].

System State

The state of the system at time t is described by the state of each sensor (object detected or not) at that time. This state is represented as a vector of boolean values, one for each vertex in G. In the following, we denote as S the set of all possible state vectors with respect to x objects in a PCG G. We obviously have

" |V | x « different state vectors.
Definition 1 (State Vector) A state vector at time t, denoted S t , is a vector of size |V | where:

∀v ∈ V, S t [v] = 1 if ∃ o ∈ O : loc t (o) = v 0 otherwise

The Observer

The system has an observer that is able to read, at any time t, the state vector S t . The aim of the observer is to identify objects and trace their trajectories over time. Given a state vector S t , the observer can use a function tag to assign a unique identifier o ∈ O to each vertex v such that S t [v] = 1 (and a predefined value ⊥ to all the other vertices), with the only constraint that no two vertices can share a same identifier (with the exception of ⊥). For instance, if

S t = [1, 0, 0, 1, 0, 1, 1, 0, 0] and O ⊂ N, we can have tag(S t ) = [3, ⊥, ⊥, 2, ⊥, 1, 4, ⊥, ⊥].
Each identifier represents an object identified by the observer.

For the sake of convenience, we introduce the function loc : T × O → V that returns the vertex v that was tagged by o ∈ O at time t ∈ T . Given an object identified by the observer, and its corresponding tag o, we can define the observed trajectory between two time instants t i , t j as

P ti,tj ,o = [v ti , . . . , v tj ] where v t k = loc t k (o), k ∈ [i, j]
. Effectively, we have to introduce the observed global trajectory P ti,tj = P ti,tj ,o o∈O , corresponding to the set of all observed trajectories perceived by the observer. Obviously, P ti,tj belongs to P ti,tj .

P ti,tj = P ti,tj (1)
That means that the set of observed trajectories is exactly the same than the real ones.

Given that trajectories (both real and observed) are a consequence of object locations, at a finer level of granularity we have:

MOTI is solved iff ∀o ∈ O, ∃o ∈ O, ∀t ∈ [t i , t j ] : loc t (o) = loc t (o)
The difficulty of this problem comes from the fact that there could be situations in which the observer can confuse trajectories of two or more objects.

An Impossibility result

MOTI is not solvable in the cases which are precisely defined by the following theorem:

Theorem 1 (MOTI Unsolvability) Given an interval of time [t i , t j ], a PCG G(V, E), a set O of x objects and a tag function, MOTI cannot be solved iff ∃P, P ′ ∈ P ti,tj : P = P ′ ∧ P = P ′ .

where P and P ′ are obtained by the observer using the function tag from real global trajectories P and P ′ .

Proof. Let us consider an interval of time [t i , t j ], a PCG G(V, E) with x objects.

-Assume that (1) ∃P, P ′ ∈ P ti,tj : P = P ′ ∧ P = P ′ and (2) MOTI can be solved.

Given that MOTI can be solved we have P = P and that P ′ = P ′ (cf. MOTI definition in section 4). But, we have P = P ′ and P = P ′ . Therefore, there is a contradiction. -Let prove now that if MOTI cannot be solved =⇒ ∃P, P ′ ∈ P ti,tj : P = P ′ ∧P = P ′ . Let prove the contrapositive (i.e. modus tollens) of this proposition. Consider ∀P, P ′ ∈ P ti,tj : P = P ′ =⇒ P = P ′ (P = P ′ ∨ P = P ′ ).

Let call map : P ti,tj → P ti,tj the function which associate the real trajectory to the observed one, according to the given tag function. Each bijective map function verifies the following expression: ∀P, P ′ ∈ P ti,tj : P = P ′ =⇒ map(P ) = map(P ′ ) =⇒ P = P ′ as map(•) corresponds to the observed trajectories. Let map be the identity function. We have: ∀P ∈ P ti,tj : P = map(P ) = P . Then, by definition of Section 4, MOTI can be solved. Thus, we have: MOTI cannot be solved =⇒ ∃P, P ′ ∈ P ti,tj : P = P ′ ∧ P = P ′ .

We then obtain the equivalence, i.e.

a
P = P ′ =⇒ P = P ′ .
Consequently, there is an impossibility to solve MOTI if, and only if, there exist at least two global trajectories which respect the condition of Theorem 1. Therefore, we can state that: Theorem 3 (MOTI Impossibility) Given the system model presented in Section 3, MOTI is impossible to solve.

Proof. Consider a 4 vertex PCG G with a 4 edge loop around its vertices, as shown in Figure 2.a. Consider two objects moving in this graph G and a time interval constituted by two consecutive time instants [t 0 , t 1 ] with t 1 = t 0 + 1. Consider the two global trajectories P, P ′ ∈ P t0,t1 , presented in Figure 2.b and 2.c. They are defined as:

       P = [A , B] [D , C] P ′ = [A , C] [D , B]
Obviously, we have P = P ′ . According to the system model and the observer capabilities, the information known by the observer for both case P and P ′ , is presented in Figure 2.d. We assume that t 0 is the initial time. Then, the observer does not have any other information available about the system than the two following state vectors (which are the same for both P and P ′ ): S t0 = 1, 0, 0, 1 and S t1 = 0, 1, 1, 0

As the relation tag is a function (a single output for a given input element), it exists a unique tagging for a state, according to the corresponding state vector and previous state available. Thus, assume that:

tag(S t0 ) = 1, ⊥, ⊥, 2 .
According to tag(S t0 ) and S t1 , only two values are possible for tag(S t1 ):

(1) tag(S t1 ) = ⊥, 1, 2, ⊥ or (2) tag(S t1 ) = ⊥, 2, 1, ⊥ .
For each of these cases, tag(S t1 ) is the same for the observation of P and P ′ . So, given a function tag, P = P ′ . Then, due to Theorem 1, MOTI cannot be solved.

⊓ ⊔

For better understanding of this result, let's take a closer look at each case. Case (1) In this case, the observed global trajectory computed by the observer is:

P = P ′ = [A , B] [D , C] .
Then, we have P = P = P ′ = P ′ and MOTI is not solvable. Case (2) By symmetry, in this case, the observed global trajectory computed by the observer is:

P = P ′ = [A , C] [D , B] .
Then, we have P ′ = P ′ = P = P and MOTI is not solvable.

So, it exists at least one case in which MOTI cannot be solved. Then, Theorem 3 is proved.

MOTI Solvability

Before delving into the details about how the system model can be constrained to make MOTI solvable, we need to introduce some other notations.

Safe and Unsafe Characteristics

Given an object o and the trajectory it describes on the graph as time passes by, we can identify its single movements.

Definition 2 (Movement) Let o ∈ O be an object moving in the system represented by G(V, E). For each time instant t ∈ T , we define its movement as m t,o = P t,t+1,o . The movement set is defined, for each time instant t, as the set of all movements done by objects; therefore, it represents how the system "evolves" just after time t.

If we now consider the system state at a specific time t, we can identify all the possible movements that objects are able to do. Each possible combination of these movements corresponds to a different movement set. All these movement sets are defined on the basis of the position of objects on the graph, i.e. given a state vector, we can define all the possible movements. From this point of view, movement sets are not necessarily tied to time, as they can be considered as the sets of possible movements that objects can do if, at a certain time, they are located on a specific subset of vertices. This idea leads us to the definition of the State Graph, which is a graph representing possible system states (in terms of state vectors) and possible movement sets linking them.

Definition 4 (State Graph) Let G(V, E) be the PCG representing the environment where x objects can move. The corresponding state graph is defined as SG(S, M), where S is the set of all the possible state vectors and M is the set of all the possible movement sets.

Figure 3 shows an instance of a state graph, depicted on the right side, when considering two moving objects and the 4 vertex graph introduced above, depicted on the left side. Now we can define which edges and which vertices of the state graph should be considered as unsafe with respect to the solvability of MOTI.

Definition 5 (Unsafe Movement) Consider a system represented by G(V, E) where objects belonging to O can move, and the corresponding state graph SG(S, M). Consider two states S, S ′ ∈ S such that it exists a movement set M ∈ M that links these two states (S

M -→ S ′ ). M is unsafe iff ∃M ′ ∈ M such that S M ′ --→ S ′ and M = M ′ .
We consider unsafe all movement sets linking two system states that are yet linked by some other movement sets. The idea behind this definition is that an observer can not distinguish which movement set has really occurred between all the unsafe movement sets linking the same system states (because the trajectories it observes are calculated only considering system states). The presence of unsafe movements in a state graph make MOTI problem impossible to solve. In the same way, we can define what an unsafe state is.

Definition 6 (Unsafe state) Consider a system represented by G(V, E) where objects belonging to O can move, and the corresponding state graph SG(S, M).

A state S ∈ S is unsafe iff ∃M ∈ M, ∃S ′ ∈ S such that S M -→ S ′ and M is unsafe.
Considering again the state graph depicted in Figure 3, states S 2 and S 3 are both unsafe because there are two distinct edges (two unsafe movement sets) linking them (bold arrows). All the other states (and so, all the other movement sets) are safe.

Characterizing MOTI Solvability

On the basis of these definitions, we revise Theorem 2 and propose two different definitions of MOTI solvability. In the first case, we assume that the global trajectory is known (e.g. when analyzing the behaviour of the system a posteriori).

Theorem 4 (P -solvability) Let SG(S, M) be the state graph defined over a PCG G(V, E) representing the system where objects in O can move. Consider a specific trajectory P ∈ P ti,tj : MOTI can be solved iff ∀t ∈ [t i , t j-1 ], M t is safe.

Proof. Consider a specific trajectory P ∈ P ti,tj .

-Assume that ∃t ∈ [t i , t j-1 ] such that M t is unsafe. Let call P * = P t,t+1 the subtrajectory of the considered P ti,tj such that M t = P * . Due to Definition 5, it exists at least one different unsafe movement M ′ in M between the two same system states S, S ′ such that M ′ = P ′ * . Obviously, P * = P ′ * but they share the same initial and final state vectors S t and S t+1 . Given that the relation tag available to the observer is a function, it exists a unique tagging for these states. Then, we have: ∃P * , P ′ * ∈ P t,t+1 : P * = P ′ * ∧ P * = P ′ * .

Therefore, due to Theorem 1, MOTI is unsolvable for P * and P ′ * . Therefore, given that P * is a sub-trajectory of P ti,tj , MOTI is unsolvable for P ti,tj .

-Assume here that ∀t ∈ [t i , t j-1 ], M t is safe. Then, we have:

∀t ∈ [t i , t j-1 ], ∄ M = M t such that S t M -→ S t+1 . Then, ∀t ∈ [t i , t j-1
], ∃!P ∈ P t,t+1 from S t to S t+1 and, as it is unique, this P is the sub-trajectory between time t and t + 1 of the considered P ti,tj . So, ∀P ′ ∈ P t,t+1 such that P = P ′ , the initial (or respectively the final) system state of P ′ is not equal to the initial (or respectively the final) system state of P . Then, consider a bijection function map as introduced in the proof of Theorem 1. We have: ∀P ′ ∈ P t,t+1 : P = P ′ =⇒ map(P ) = map(P ′ ). If map is the identity function, we have: ∀P ′ ∈ P t,t+1 : P = P ′ =⇒ P = P ′ . Therefore, due to Corollary 2, MOTI can be solved.

⊓ ⊔

Even though characterizing MOTI solvability with respect to a specific global trajectory is useful for all those systems where we want to decide at any point of time if MOTI is solvable or not, it is also possible to define a set of cases where MOTI is always solvable. This new characterization generalizes Theorem 4 with all possible trajectories that can occur in the system: Theorem 5 (P-solvability) Let SG(S, M) be the state graph defined over a PCG G(V, E) representing the system where objects in O can move. ∀P ∈ P ti,tj : MOTI can be solved iff ∀S ∈ S, S is safe.

Proof. Assume that ∀P ∈ P ti,tj MOTI can be solved. Then, ∀P ∈ P ti,tj , ∀t ∈ [t i , t j-1 ] : M t is safe (Theorem 4) and ∀P ∈ P ti,tj , ∀t ∈ [t i , t j-1 ] : S t is safe (Definition 6). Given that each system state can occur as an initial state of a trajectory, we have: ∀S ∈ S, ∃P ∈ P ti,tj : S ti = S.

Then, given that all system states are safe for all possible trajectories, we have that ∀S ∈ S, S is safe. Assume now that ∀S ∈ S, S is safe. Due to Definition 6, we have that ∀M ∈ M, M is safe. It follows that ∀P ∈ P ti,tj , ∀t ∈ [t i , t j-1 ], M is safe and, due to Theorem 4 speaks that ∀P ∈ P ti,tj , MOTI can be solved.

⊓ ⊔

A Sufficient Condition for Making MOTI P-solvable

In this section, we show how MOTI can be solved by constraining some characteristics of the system model. More specifically, we show how the problem becomes easily solvable if we assume that object movements are limited in some way.

As we previously explained, the state graph associated to a system may present one or more unsafe states that make MOTI unsolvable. One way to avoid the presence of unsafe states in the state graph, is to remove some of the unsafe movement sets such that the remaining movement sets are all safe. From a practical point of view, this means limiting object movements in the environment, modifying the environment itself or constraining their actions. Let think about a building where people can move from one room to another through doors, this can be realized simply by locking some doors. Therefore, that means deleting the corresponding edges between two vertices of PCG G and modifying accordingly the state graph.

Basically, the only cause of the MOTI non solvability in a system is the presence of cycles in the graph: when two or more objects move inside a cycle, it might be impossible to distinguish their trajectories based on the sole observation of the state vectors. This problem can be avoided by limiting the number of objects in O, which can move concurrently, to a specific k that strictly depends from some characteristics of the PCG G. In this case, we can guarantee that MOTI is solvable for all the possible trajectories P as long as at most k objects move concurrently at each time unit. The set of all these trajectories is a subset of P and will be denoted as P k .

Theorem 6 Let k ≤ |O| be the maximum number of objects that can move concurrently, ℓ > 1 be an integer and G(V, E) be a PCG which does not contain cycles of length 1 < l < ℓ. ∀P ∈ P k : Proof. We first prove that if k < ℓ 2 ⇒ ∀P ∈ P k , P does not contain any unsafe movement. The proof is done by induction on the number n < k of objects moving concurrently in the system at each step. In the following, given S and S ′ two state vectors, we refer to diff (S, S ′ ) to denote the number of vertices in G whose state changes between S and S ′ . Note that diff (S, S ′ ) is always an even number because for each object that moves, two vertices change their state in the state vector. Base step on n. Consider the State Graph construction algorithm reported in Appendix A. At the first iterative step of that algorithm, edges labelled with the movement of a single object are added to the edge-free state graph, linking all the possible couples of state vectors S, S ′ such that diff (S, S ′ ) = 2 and it exists an edge in G linking the two vertices that changed their state. For each of these couples (S, S ′ ), a single edge is added as only one object in the system can do the movement associated to the two vertices whose state changes between S and S ′ . Therefore, for a system where only one object at a time can move (i.e. n = 1), the resulting state graph does not contain any unsafe movements. Induction hypothesis. Assume that if n < k objects move concurrently, none of the possible trajectories P ∈ P n contains an unsafe movement. Induction step on n. Now, consider the case where n + 1 objects move concurrently. We want to show that, beside this change, no unsafe movement is added to SG. More specifically, we want to prove that ∀S, S ′ ∈ SG such that 2 ≤diff (S, S ′ ) ≤ 2(n + 1), if we can add an edge in SG between S and S ′ labelled with n + 1 concurrent movements, then there cannot exists another edge between them labelled with n + 1 or less movements.

MOTI is P -solvable iff ℓ 2 > k. v p G A G B p' 1 v 2 v n+1 v n+2
Let us first consider the case where diff (S, S ′ ) = 2. Assume that the two vertices changing their state between S and S ′ are labelled v 1 and v n+2 . An edge labelled with n + 1 movements can be added in SG between S and S ′ only if it the path p = v 1 , v 2 , . . . , v n+1 , v n+2 exists in G and ∀v ∈ {v 1 , . . . , v n+1 }, S[v] = 1. Now, we show that the only possible movement bringing the system from S to S ′ is the one where each object located in v i , with i ∈ [1, n + 1], moves to v i+1 . Assume, without loss of generality, that there is another possible movement that does not involve objects located on vertices v 2 , . . . , v n+1 . Figure 4 represents this case where the object located on v 1 must move to a different subgraph G A of G and an object located on subgraph G B must move to node v n+2 . If the only path connecting vertices in G A with vertices in G B is p (it does not exist a link p ′ as in Figure 4), then |{v ∈ G

A : S ′ [v] = 1}| > |{v ∈ G A : S[v] = 1}| (and respectively, |{v ∈ G B : S ′ [v] = 1}| < |{v ∈ G B : S[v] = 1}|). This imples that ∃v ∈ G A ∪ G B : S[v] = S ′ [v] ⇒diff (S, S ′ ) > 2,
which is impossible due to our initial hypothesis. On the contrary, if there is a path p ′ = p connecting G A to G B , then p is part of a cycle c ⊂ G. The length of c is, by assumption, at least ℓ. In order to have diff (S, S ′ ) = 2, in S, there must be an object located on all vertices in c but v n+2 and all the objects located on these vertices, with the exception of those located on v 2 , . . . , v n+1 , must be moved (otherwise diff (S, S ′ ) > 2). But this means that m (≥ ℓn) objects will move concurrently. Given that ℓ 2 > k ≥ n + 1, we have m > 2(n + 1)n > n + 1, i.e. every other edges connecting S to S ′ in SG must be labelled with more than n + 1 movements. Now, consider the case where diff (S, S ′ ) = 2(x + 1) with x ≤ n. In this case, there are n + 1 distinct objects moving on x + 1 distinct paths, each characterized by the presence of an object on each vertex but the last one (as p in Figure 4). The same reasoning shown for the previous case can be applied to every single path, considering that each of these paths contains strictly less than n + 1 objects. Now, we prove by contradiction that if ∀P ∈ P k , MOTI is P -solvable ⇒ ℓ 2 > k. Assume for the moment that k ≥ ℓ 2 . Consider the smallest cycle c in G constituted by vertices v 1 , . . . , v ℓ . Now consider, without loss of generality, a state vector S where ∀i ∈ {2

• k -1|k ∈ [1, ℓ 2 ]} : S[v i ] = 1 and ∀i ∈ {2 • k|k ∈ [1, ℓ 2 ]} : S[v i ] = 0. Consider also the state vector S ′ that is identical to S but where ∀i ∈ {2 • k -1|k ∈ [1, ℓ 2 ]} : S[v i ] = 0 and ∀i ∈ {2 • k|k ∈ [1, ℓ 2 ]} : S[v i ] = 1 (Note that, if ℓ is odd then S ′ [v ℓ
] remains unchanged and equals to 1). Then, the states of all vertices -but the last in case of ℓ odd -indexed from 1 to ℓ are inverted. Such two state vectors are certainly in SG because we are assuming that k ≥ ℓ 2 . Now consider the following movements

M = {[v i , v i+1 mod ℓ } i∈{2•k-1|k∈[1,⌊ ℓ 2 ⌋]} and M ′ = {[v i , v i-1 mod ℓ } i∈{2•k-1|k∈[1,⌈ ℓ 2
⌉]} . Both movements link S to S ′ in SG and are labeled with lower or equals concurrent moves than k. Therefore, it exists unsafe movements. This is in contradiction with the initial assumption that ∀P ∈ P k , MOTI is P -solvable.

⊓ ⊔

In a practical setting, there are two possible methods to guarantee that the conditions at the basis of Theorem 6 always hold. The first method requires to choose, as the PCG, a topology characterized by cycles of length strictly larger than 2 • x. As a consequence, MOTI is P-solvable in any system characterized by an acyclic graph as presented in the following Theorem 7. The second method requires to limit the number of objects that can move concurrently in the system.

Theorem 7 MOTI is P-solvable in any system characterized by an acyclic graph G(V, E).

Proof. We can consider G as a graph with a cycle of infinite length. Due to Theorem 6, MOTI is P-solvable as long as no more than an infinite number of objects move concurrently in the system. Given that O is finite, the P-solvability is always guaranteed. ⊓ ⊔

Conclusion

In this paper, we have considered the possibility of assigning trajectories to moving objects on a generic sparse passage connectivity graph. We have shown that assigning a unique identifier to a track revealed by a binary sensor network, namely the MOTI problem, is impossible. To make the result as strong as possible, it has been proved under strong assumptions i.e., perfect binary sensors, perfect coverage and omniscient observer of the state of the graph. We proved that this impossibility depends primarily of the topology of the graph and secondly of the number of moving objects. Following this impossibility result, we have considered restricting the model to make such assignments possible. More specifically, we have shown that MOTI can be solved either if the graph is acyclic or the length of the smallest cycle in the graph is strictly greater than the double of the number of objects that can concurrently move in the system. This leaves the opportunity to modify the topology of the passage connectivity graph like for example in an indoor scenario. Once the maximum number of moving objects is known, our results mainly impact on the deployment phase of a sensor network.

Lot of open questions have still to be considered. For instance, some characterizations can be reformulated in order to reduce the computation of the observer. In a distributed way, identifying distributed algorithms able to impose the aforementioned restrictions to the system model, without relying on a global knowledge of the system is not trivial. This leaves the space for an exciting research agenda.

Fig. 1 .

 1 Fig. 1. Example of a trajectory of an object o in the interval [t0, t3] : Pt 0 ,t 3 ,o = [C, D, E, I].

4

  The Problem of Identifying Objects and Tracking Trajectories 4.1 The MOTI Problem Let us consider an interval of time [t i , t j ]. The Multiple Object Tracking and Identification (MOTI) problem is the problem of defining a function tag such that the following condition holds: ∀o ∈ O, ∃o ∈ O : P ti,tj ,o = P ti,tj ,o . In a global view, we can define MOTI as the following condition:

1 Fig. 2 .

 12 Fig. 2. A simple example in which the observer cannot track precisely the trajectories of objects: For a PCG G presented in (a) with two objects, two global trajectories P and P ′ , presented in (b) and (c) respectively, can occur and the observer is not able to distinguish them with only the information presented on (d) if objects have moved following trajectory P or P ′ .

4 S 6 Fig. 3 .

 463 Fig. 3. Example of a state graph for a 4 vertex PCG G (shown on the left) including 2 objects.

Fig. 4 .

 4 Fig. 4. Representation of the PCG G which illustrates the possibility of exiting paths between v1 and vn+2.

  Given an interval of time [t i , t j ], a PCG G(V, E), a set O of x objects and a tag function. MOTI can be solved if, and only if, ∀P, P ′ ∈ P ti,tj :

	characterisation of the MOTI unsolvability.	⊓ ⊔
	Corollary 2 (MOTI Solvability)

A An Algorithm for Computing SG

In this appendix, we propose a state graph construction algorithm, based on the conditional transitive closure of a one-movement only state graph. This condition ensures that no inconsistent movement will be included in the state graph generated by the algorithm.

This protocol is composed of two main parts. The first part creates an empty edge set and a complete vertices set. Then, starting from line 3 to line 6, the algorithm puts in the state graph all one-object-movement edges. From line 7 to line 13, following the same mechanism as the one used in the Floyd-Warshall algorithm for transitive closure computation, three nested loops compute iteratively all possible movements with any number of concurrent movements. Finally, the last lines from 14 to 15, merge symmetric movement edges in order to return an undirected state graph.

The termination of this protocol is trivial as it is composed only of nested loops of finite length. Moreover, the complexity of this algorithm is obviously O(|S| 3 ) as it contains three nested loops on S.

The correctness of this algorithm is based on the correctness of the Floyd-Warshall algorithm [START_REF] Floyd | Algorithm 97: Shortest path[END_REF][START_REF] Warshall | A theorem on boolean matrices[END_REF]. The condition of line 12 only ensures that no inconsistent movement can be included in the state graph, and given that new edges in SG are generated from consistent movements, no existing movement can be ignored.

Algorithm 1: State graph construction

Data: a graph G, the number of moving object x Result: the associated state graph SG(S, M) S ← {S ∈ {0,


Seafront Reclamations, Rubble, and Waste: A Metabolic Reading of Lebanese Urbanization E r i c V e r d e i l

September 16, 2021 Imad Kaafarani, Biodegradable, Digital illustration. 2021

Since the outbreak of the waste crisis in the wider Beirut area in 2015, the Lebanese government has resorted to the supposedly temporary solution of storing municipal waste in the coastal landfills of Borj Hammoud, Jdeideh, and Costa Brava. Far from being new or temporary, this solution is in fact merely a repetition of decisions implemented during the Civil War, and in a number of Lebanese coastal regions such as Saida and Tripoli, all of which share several characteristics. [START_REF]Des déchets aux remblais: imaginaire aménageur, corruption et dérèglements métaboliques à Beyrouth[END_REF] For instance, reclamations are often assigned to areas allotted for development in urban plans from the 1950s and 1960s, that were never implemented. These reclamations have become an important source for public works and real estate actors who are linked to leading Lebanese politicians, to dramatically increase profits and, in some cases, monopolize the land rent generated by these developments. Finally, the material that gives these embankments their reality erupts in moments of what we might call metabolic disturbances: when a seemingly sudden urban crisis results in an unexpected flow of materials that need to be stored in a particular place (e.g. municipal waste, rubble). These mechanisms of urbanization are a clear illustration of the notion of the Anthropocene, in that they constitute a new geological stratum created by human action.

Urban Metabolism: Consumption, Dejection, Recycling

The notion of urban metabolism enables us to look at urbanization and reclamation projects along the Lebanese coast with a focus on the circulation and transformation of the materials that give the city its consistency. Using a bodily analogy for the city amounts to thinking of the materiality of the city as the food that our ancestors ate, and in turn the manure they fertilized their fields with. This organic cyclical thinking however does not apply to the embankments fed by the rubble of today's demolished buildings, excavated soils, and municipal trash; as what remains of them is infertile soil drenched in toxic fluids, poisoning maritime fauna and flora along with bathers audacious enough to soak themselves in the sea nearby. I offer here a look at urban political ecology as envisaged by geographer Erik Swyngedouw and his colleagues in the book In the Nature of Cities. [START_REF]In the nature of cities: urban political ecology and the politics of urban metabolism[END_REF] Indeed, if the metabolism analogy is to be useful in bringing awareness to the materiality of the flows which constitute the city, we must also recognize the absolutely political nature of these operations of transportation and transformation. As political processes, they participate in the production and reproduction of power relations, in particular through the unequal mechanisms of capital circulation, thus once again posing the question of corruption and its role in the reproduction of the political elite in Lebanon, through the creation of monopolies. Another essential political dimension in this process of transformation concerns the representation of the future of Lebanese society and cities, through what I have called elsewhere a "planning imaginary". [START_REF] Verdeil | Beyrouth et ses urbanistes : une ville en plans (1946-1975[END_REF] By this I mean a set of norms and representations or visions foregrounded in the development and urban planning policies of the Lebanese capital. Such visions were born from the interplay of major political players and elitist planners often closely connected to them. In particular, these visions define specific territories of intervention and political and social projects for specific places, most often on the coastline. The new coastal contours of the Beirut metropolis can only be understood as the combined product of the construction of this political and financial imaginary, as embodied in the resulting projects, and the materials that give shape to them.

Solidere and its Reclaimed Land

Beirut's current city center includes the most famous example of an embankment, often identified as BIEL, comprising of more than 60 hectares of parcellated plots and including a conference and exhibition center. This extension on the sea is the result of a series of projects and initiatives dating back to the 1960s, in particular one aimed at gaining seaside land while building a road bridge linking the Ain el Mreisseh corniche to the highway at the eastern exit of Beirut.

The fifteen years of civil war and the metabolic disruption it caused for the storage of domestic waste created the opportunity to fill in the Normandy bay, which became a dumpsite in 1978. Fouad Awada, an urban planner who was, a member of Master Plan for the Development and Urban Planning of the Beirut Metropolitan Region's team in the 1980s, wrote: "Those who speak ill of the project remind us that this embankment on the Normandy bay, which spoiled one of the most beautiful sites of Beirut, was not as "spontaneous" and "forced" as it is claimed. The administrator had concocted it since the early 1960s, when he was Director General of Urban Planning, and he dreamed of making a highway pass through the width of the bay, to "close" the ring road around Beirut. The municipality would have received assurances that the embankment would be used for the construction of buildings, whereas the current management intends to turn it into a large central amusement park." [START_REF] Awada | La gestion des services urbains à Beyrouth pendant la guerre : 1975-1985[END_REF] As early as 1983, the bulldozers of Oger Liban, then put at the disposal of the government free of charge by Rafiq Hariri, demolished buildings and neighborhoods considered irretrievable, most notably the souks of Beirut. This initiative was taken in a hurry, without planning, and provoked protests and indignation by public opinion. It is known that the reconstruction work in the downtown area, from 1991 to 1998, increased demolitions, amounting to a total of 80% of existing buildings in the area. This new rubble, in turn, was dumped onto the Normandy landfill adding considerably to its size.

The Normandy dumping site grew continuously throughout this period. Future plans to construct high-rises on this embankment required powerful reinforcements (a dyke capable of withstanding a tsunami, soil stability for high-rises among others), and therefore an added cost of several hundred million dollars had to be accounted for to clean up the site and provide new backfill materials. As the State could not pay this cost, it offered the land (with a high exploitation ratio) to Solidere as an in-kind contribution. In doing so, it validated the profits the developers and their political backers anticipated, when they started a dump in the sea.

Empty land on the BIEL-Solidere reclamation project in 2015 (Photo Eric Verdeil)

The example of the city center embankment suggests that the first plans of sea reclamation played a role in channelling an unexpected influx of material (waste and rubble) resulting from the destruction of the city center. Subsequently, the financial imagination of the developers saw the landfill as an opportunity for profit. They consequently not only extended the area of the embankments but also imposed reinforcement works, which were at the same time a source of large profits.

The Reclamations of the North Metn

Several plans were proposed for land reclamation on the North Metn coast, where suburbs have been spreading out in disorder since the 1960s. The vision of the urban planner Gabriel Char in 1974 aiming at extending the port of Beirut was never realized, but in 1981, Metn MP Amine Gemayel launched a study carried out by Dar Al-Handasah to create an eightkilometer stretch from Borj Hammoud to Dbayeh. This was intended to restructure the sprawl of urbanization, which had accelerated with the civil war, by building missing infrastructural elements such as a new maritime road, a wastewater treatment station, commercial and light industrial zones, as well as real-estate and touristic developments around marinas. Once elected president, Gemayel kicked off the project with the support of Rafiq Hariri and that of the entrepreneur Joseph Khoury, who specialized in maritime works and owned the large Nahr-el-Mott quarry which was able to supply the dyking materials. From then onwards, the Borj Hammoud region became a waste material dump, much like the Normandy bay. But Gemayel and Khoury gave priority to the Dbayeh area, which was of a shallower nature and was thus more prone to development. Architect Ricardo Bofill drew up a plan, and works promptly began with the construction of a protective dam. The materials brought in from the quarry turned out insufficient and too expensive, and, with the use of municipal waste spoiling the site, the project came to a halt.

It was then revived in the 1990s. The Dbayeh area was subject to a development plan, the realization of which was once again entrusted to Joseph Khoury who received a third of the land in exchange for his services. Sold to the Emirati operator Majid al Futtaim Group, the development now forms The Waterfront City, a marina associated with a luxury residential complex.

In parallel with the operations of Dbayeh, the Council for Development and Reconstruction (CDR) relaunched studies for the realization of a land reclamation embankment between Borj Hammoud and Antelias, under the name of Linord, a real-estate company based on the Solidere model. Fierce competition over who would control the future backfilled lands took place between several potential investors and political players who established themselves during the civil war such as then Prime Minister Rafiq Hariri, then Interior Minister Michel el-Murr, and other local entrepreneurs. The project also gave rise to various mobilizations of opposition, notably on the part of municipalities such as that of Borj Hammoud, which feared the nuisances of installing a wastewater treatment plant, when there was already a marked increase in the accumulation of waste, north of Borj Hammoud. This "mountain" of waste was the main landfill in the agglomeration from 1991 to 1997 and extended into the sea over a surface area of nearly 40 ha, standing 42 meters high. The chronic combustion of waste spread harmful fumes and a stench over the city. This pile represented a new form of metabolic disruption and therefore an opportunity to create the reclamations of the Linord project. However, their stabilization and reprocessing would increase the costs of the project, particularly due to the proximity of the steep slopes of the submarine canyon forming the bordering segment of the Beirut River. With the downturn of the real-estate market in 1996-97 followed by the arrival of President Lahoud, the project was abandoned. This episode shows that even if metabolic disturbance, i.e. the overflow of rubble and waste, offers opportunities for urban development, their feasibility remains constrained by the real-estate market and the circulation of urban capital.

The empty land on the reclamation project in Dbayeh in 2017 (Photo Eric Verdeil)

Accelerated Urbanization, Frenetic Consumption, Landfill Proliferation

The period from the 1990s to present day in Lebanon has seen unprecedented urban expansion (an increase of 80% between 1994 and 2013) at a rate far exceeding population growth. [START_REF]Population assessments are unreliable and contradictory in Lebanon, because of the lack of a census[END_REF] This urban sprawl goes hand in hand with an intensive use of natural resources for construction materials, largely taken from the mountains around Beirut. Much of the quarrying is illegal but tolerated, both because the construction sector's contribution to the Lebanese economy is deemed essential, but also because the quarry operators are protected by the corrupt political structure of the country, enabling them to sustain their activities. Increased demolitions of old buildings and excavations of new construction sites generated rubble that had to be disposed of. In 2006, Israeli bombs flattened 220 buildings in a 32-hectare neighbourhood in the heart of the southern suburbs of Beirut. As all destruction is an opportunity for growth within this system, the rubble was deposited on the seafront, in an area called Costa Brava, south of the airport.

In parallel with the spiking rate of construction, Lebanon is also experiencing an exceptional boom in consumerism, causing a sharp increase in the volume of waste. This rise -in inorganic waste in particularreflects the changing consumption habits of a hyper-urbanized and globalized population divided by growing social inequality: most of the goods are now imported and often manufactured abroad, from food to consumer products. In the region of Beirut and Mount Lebanon, the amount of municipal waste increased by 42% between 1999 and 2013, a rate much higher than the growth of the population. This boom of municipal waste fueled by goods consumption and associated discarding practices resulted in new coastal landfill projects.

The 2015 waste crisis worsened with the lack of a decision on an alternative for the treatment of municipal waste, thus forcing the government to find places to store it while reviving the Linord project which had been dormant for 17 years. In addition to this revival, Environment Minister Chehayeb aimed to create a 33.3 ha landfill between Borj Hammoud and Jdeideh. The soil of this site is composed of a mixture of sand and detritus from the nearby waste mountain which is now ironically considered non-polluting after having spread its pollution in the air, water, and soil for years. [START_REF] Mansour | From Trash Dump to Dreamland: An Entangled History of Toxicity and Capital[END_REF] Chehayeb, who gave his name to the plan, was also Minister of the Environment in 1997 when he had overseen the closure of the Borj Hammoud dump and the supposedly temporary opening of the Naameh dump. Thus, the 2015 crisis re-excavates the memory of suspended projects.

Landfill in Borj Hammoud (Google Image 2021)

The Chehayeb plan also included turning the Costa Brava site, where rubble was first disposed of in 2006, into another landfill [START_REF]Unlike other landfill sites, I am not aware of any planned coastal development projects there[END_REF] . Nevertheless, and despite the relative remoteness of the site from settlement quarters, the landfill has been strongly contested by the municipalities in the area as well as by environmental groups at large. It should be noted that the emergency construction of these two new landfills has given rise to numerous legal irregularities and exacerbated seawater pollution, as the dumping of waste began before the completion of the protective dykes and the installation of the insulating membranes planned to limit leakages.

On the other, we have seen how the anticipation of rising land values drives endeavors to appropriate seaside lands; and finally, how instances of metabolic disruption provide the materials to backfill the sea on the chosen sites.

However, the variable temporalities of these metabolic impulses suggest two conclusive thoughts. A distinction is made between sudden shocks (violent destruction as in the case of the Israeli onslaught of 2006, and the overflow of waste in 2015) as opposed to a constant acceleration of urban construction and consumption generating waste and excavated material flows sustained over the long term. In these two types of temporalities, the intensification of consumption and the rejection of materials (the production of rubble) are directly correlated to the circulation of capital which, in the Lebanese context, comes essentially from abroad (emigration remittances, foreign investments) and directly feeds consumption and real-estate. The transport of rubble resulting from building dismantling and excavation works towards the urban periphery and on the seashore can be observed in many rapidly changing metropolises -particularly in Asia-and constitute a characteristic of the Anthropocene. [START_REF] Zalasiewicz | City-Strata of the Anthropocene[END_REF] Cities no longer grow on their ruins, as they had done for centuries, rather they export their ruins to the periphery. In Lebanon, this movement is accelerated by the inability to regulate the flow of waste through policies of volume reduction and recycling. In recent years, ad hoc solutions to the waste crisis have led to the construction of landfills that risk foreclosing other uses for those lands for the foreseeable future. The model of coastal landfill urbanization has only resulted in deserted plateaus and new mountains of rubbish overlooking the sea, wasting natural resources and disregarding basic principles of urbanity, until the foreseeable future.

Analyzing the large backfilling projects in Greater Beirut and Saida makes abundantly clear a strong connection between three impulses. On the one hand, we can see how ideas of modernity and regeneration were instrumental in the conquest of new land on the sea in early urban plans.