# Object Tracking Using Multiset Color Coding

Chung Shue Chen, Yuan-Hsun Lo, Wing Shing Wong, Yijin Zhang

► To cite this version:

Chung Shue Chen, Yuan-Hsun Lo, Wing Shing Wong, Yijin Zhang. Object Tracking Using Multiset Color Coding. 2024 International Symposium on Information Theory and Its Applications (ISITA), Nov 2024, Taipei, Taiwan. pp.378-383, 10.23919/ISITA60732.2024.10858214. hal-05367395

HAL Id: hal-05367395

https://hal.science/hal-05367395v1

Submitted on 15 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Object Tracking Using Multiset Color Coding

Chung Shue Chen*, Yuan-Hsun Lo†, Wing Shing Wong‡, and Yijin Zhang§

*Nokia Bell Labs, Paris-Saclay Center, Massy 91300, France

†Department of Applied Mathematics, National Pingtung University, Taiwan

‡Department of Information Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR

§School of Electronic and Optical Engineering, Nanjing University of Science and Technology, China

Email: chung_shue.chen@nokia-bell-labs.com, yhlo0830@gmail.com, wswong@ie.cuhk.edu.hk, yijin.zhang@gmail.com

*Abstract*—We consider the tracking problem of an object that can randomly appear on a line of a fixed length. We want to determine the position of the object and rely on sensors that can detect objects with a predefined range and report that to a remote observer. Sensors are equipped with a transmitter that can transmit at a limited data rate. Once a sensor is triggered, it transmits its own ID to inform. A straightforward protocol is to label each sensor with different ID. However, this would require a large number of unique IDs and many bits to represent. As a result, higher data rate is required. We propose a newly defined protocol using multiset color coding with optimal design or efficiency in reusing a much smaller number of IDs for the whole system. We only require the minimal number of bits for labeling each sensor. We derive the factor of reduction and show its significance. We present some optimal constructions for the required multiset color coding sequence. Besides, we derive the general upper and lower bounds for the maximum length (size) of the system. Numerical examples have also demonstrated the effectiveness and improvement by the proposed new method.

# I. INTRODUCTION

Tracking an object or determining the position of a robot from local observations is a natural and interesting problem of practical importance. There is a strong demand on localization and tracking system for industrial Internet-of-things (IIoT) and beyond 5G (B5G) [1]. It is however challenging to design simple and efficient solution for such at low cost and low system complexity. For example, ambient IoT is a wireless sensor network connecting a large number of low-cost self-powered sensor nodes (e.g., ambient backscatters [2]) for detecting moving objects for instance under an automated factory or modern warehouse environment. Object tracking or localization is a key element and there are many use scenarios such as smart cities, environmental sensing, asset tracking, user mobility management, etc. One would like to track the location of a robot or detect its occurrence through some sensor nodes which however have quite limited communication bandwidth or power capabilities [3].

A basic solution for the object tracking in an industrial wireless IoT deployment may just assume that each sensor node has its own identification number (ID), which is different from each other. However, if the number of sensor

nodes is large, the number of bits required to represent an ID is also going to be large, consequently requiring higher transmission channel data rate [4]. An interesting question that one may raise is what is the minimum number of required different/unique IDs for the sensors so that the channel data rates can be minimized. It is desirable that the number of bits required for representing each ID is small such that a very narrow bandwidth or low channel data rate would suffice [5]. A protocol using IDs composed of fewer bits is clearly preferred. Simply labeling the sensors using unique IDs is inefficient and will not work under bandwidth limited or communication data rate constrained large system.

In this paper, we address the above question and consider the tracking problem of an object that can randomly appear on a line of a fixed length. We propose a newly defined color coding protocol with nice design which would use the minimal number of bits required for each ID. The technical results and main contributions of the paper are summarized below.

* We propose a newly defined object tracking protocol by using multiset color coding in minimizing the number of required IDs in the system.

* We show that by reusing the given IDs suitably in taking the advantage of their possible combinations, one can substantially reduce the number of required bits for each ID. This implies significant efficiency gain or improvement. Moreover, the result is necessary for supporting large system.

* We derive the general upper and lower bounds for the maximum length of the line for various system configuration parameters (e.g., the chosen sensor detection range and the number of available IDs). Besides, we provide construction methods for the required multiset color coding.

The rest of the paper is organized as follows. In Section II, we describe the system model and present the proposed scheme, called color coding protocol. In Section III, we formalize the color coding as a coloring problem and present the obtained main results. We show the performance gain of the proposed protocol against the conventional protocol by deriving the factor of reduction during Section IV. Finally, we conclude the paper in Section V.

Authors are presented in alphabetical order. A part of the work was carried out at LINCS (www.lincs.fr). This work was supported in part by the National Science and Technology Council, Taiwan, under Grant 112-2115-M-153-004-MY2 and by the National Natural Science Foundation of China under Grant 62071236.
## II. SYSTEM MODEL

Consider a tracking problem of an object that randomly appears on a line of length L. We divide time into discrete time slots of duration h. At the beginning of each time slot, the object may show up anywhere on the interval [0, L), kind of a quantum system. We want to determine the position of the object at the beginning of each time slot i, for each i with upside precision δ, i.e., if the system says the object is located at 3δ, then it is located in the interval [3δ, 4δ). Note that we can also define symmetric precision with more technical details.

For the above tracking and localization, we rely on sensors that can detect objects. Without loss of generality, a sensor can detect objects to its left or right with arbitrary pre-set distance or a predefined range. For example, a sensor located at position 0 can detect object in one and only one of these ranges: [-a, b) or (-a, b) or [-a, b] or (-a, b], where a, b ≥ 0 unit in distance. To report the location of the object to a remote observer, all sensors are equipped with a transmitter that can transmit B bits per h time unit. So, the data rate is R = B/h bits/s.

### A. Straightforward Protocol

For tracking accuracy δ, a common sense model is to set a sensor at x to detect objects in the range [x - δ, x).<fnref n="1" /> Sensors are located at δ, 2δ, ..., [L/δ]δ, so that the sensor at (j + 1)δ can detect object in the range [jδ, (j + 1)δ). In other words, it is to say if the object is located within [jδ, (j + 1)δ), only the sensor at (j + 1)δ is triggered and it will report the detection of object to the remote observer and transmit its own ID (identification number or label) to signal. Given that each sensor has a communication channel with data rate R, since there are [L/δ] sensors, we require

$$ \log_2 [L/\delta] \leq R\delta, \quad (1) $$

which implies that $L \leq \delta^2 R\delta$. For convenience, we denote $N \triangleq [L/\delta]$ throughout this paper. Fig. 1 illustrates the system and its setup.

One can see that we would use N unique IDs for the N sensors and each ID requires $\log_2 N$ bits to represent. If the expected length L is greater than $\delta^2 R\delta$ (i.e., Eqn. (1) does not hold), the above unique ID protocol cannot be used. Moreover, if the detection range of each sensor is larger than the tracking accuracy δ, the straightforward protocol seems a bit lavish. Therefore, we can consider the following newly defined protocol.

### B. Color Coding Protocol

For accuracy δ, set a sensor at x to detect objects in the range [x - mδ, x), where m is positive integer, while

<figure><img src="image_2.png" /><figcaption>Fig. 1. N = 4 sensors are sufficient for the case that 3δ < L ≤ 4δ. Sensor at (j + 1)δ detects whether the object is located within [jδ, (j + 1)δ), where j = 0, 1, 2, 3, and transmit its preassigned unique ID to signal (report) to a remote observer.</figcaption></figure>

sensors are located at δ, 2δ, ..., [L/δ]δ as usual. Note that in comparison to the aforementioned common sense model, we have the detection range with a system configuration parameter m, i.e., [x - mδ, x).<fnref n="2" /> By doing so, if the object is located within [jδ, (j + 1)δ), the sensors at (j + 1)δ, ..., (j + m)δ are triggered and they will report the detection of object in parallel to the remote observer, see Fig. 2. While the triggered sensors will transmit their IDs to inform the remote observer, the number of unique IDs for the system (with the same accuracy δ) indeed can be reduced. That is, we would use a set of k ≤ N IDs, from which we select one ID for each sensor but can reuse. For a set of k IDs for the N sensors, each ID requires $\log_2 k$ bits to represent. The condition is:

$$ \log_2 k \leq R\delta. \quad (2) $$

For the system with length L and $N = \lfloor L/\delta \rfloor$ sensors, in order to locate the object, we need a set of k IDs and label each sensor appropriately such that their combination of m consecutive IDs would be distinguishable (unique), when the IDs are collected by the remote observer. Here is a coding and optimization problem, which will be formalized in Section III. As an example shown in Fig. 2 where m = 2, only two IDs which are indicated by colors blue (B) and yellow (Y) are required for the sensors, instead of four IDs spent under Fig. 1 (the straightforward protocol), since the remote observer can distinguish where the object is located by each combination: {BB}, {BY}, {YY}. In the above setup, we consider the remote observer can decode the received signal and read the collected IDs but cannot distinguish {BY} from {BY} during its observation, i.e., the ordering of the received signals (IDs) cannot be sorted out, otherwise one may require a more sophisticated system with multiple time or frequency sub-channels and also a dedicated or very carefully managed channel assignment and mapping scheme among the sensors, which is either complicated or costly. It is also to say that what we concern about is only the multiset but not the exact pattern of these letters. Note that, the scenario in which the ordering of observed IDs can be determined was investigated in the literature. Some constructive solutions were proposed

<footnote n="1">¹For the simplicity of discussion, we consider the detection range of sensor at x is towards the left hand side interval [x - δ, x), however a generalization of the above consideration to the case that the detection is towards the right hand side or both sides is also possible and the result in this paper can also be applied.</footnote>

<footnote n="2">²It should be noted that a simple extension of the detection range won't work or improve the system's performance or efficiency. A color coding scheme is required for optimal design, to be discussed.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2. We use $N = 4$ sensors in this example. As $m = 2$, if the object is located within $[j\delta, (j+1)\delta)$, the sensors at $(j+1)\delta$ and $(j+2)\delta$ are triggered. Both of them report the detection of object to the remote observer. As shown above, only two IDs (indicated as two colors) are required for the four sensors (instead of four IDs spent in the case of Fig. 1) since the remote observer can distinguish where the object is located by each set of $m$ consecutive sensors.</figcaption></figure>

based on de Bruijin sequences [6] and M-sequences [7]. For more information on this related topic and its 2-dimensional generalization, please refer to [8]–[11].

Let's denote the number of combinations of the IDs of $m$ consecutive sensors by $N_m(k)$. In order to locate the objects, we need:

$$N = [L/\delta] \le N_m(k). \quad (3)$$

Once $L, \delta$ and $m$ are given, it suffices to find $k$ such that $N \le N_m(k)$. It is clear that the reduction on the number of required IDs is from $N$ to $k$. Thanks to coding, we can use a minimal $k$ and require the minimal number of bits for labeling each sensor in representing their IDs.

### III. SEQUENCE CONSTRUCTION AND LENGTH BOUNDS

We start with some necessary preliminary definitions for presenting the technical results.

#### A. Mathematical Modeling

For a positive integer $n$, let $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$ denote the ring of residues modulo $n$, and let $[n] = \{1, 2, \dots, n\}$.

Consider a sequence $S = s_0s_1 \cdots s_{N-1}$ in which each element $s_i \in [k]$. Elements in $[k]$ are called colors. Starting from an index $t$, the combination of elements $s_t, s_{t+1}, \dots, s_{t+m-1}$ can be viewed as a multiset, denoted by $S_t(m)$. The sequence $S$ is called $m$-distinguishable on $[k]$ if the multisets $S_t(m)$, $t \in \{0, 1, \dots, N-m\}$, are all distinct. For fixed $m$ and $k$, let $N_m(k)$ denote the maximum length of an $m$-distinguishable sequence on $[k]$. For convenience, we call an $m$-distinguishable sequence cyclic if the multisets $S_t(m)$, $t \in \mathbb{Z}_N$, are all distinct. Let $N_m^c(k)$ denote the maximum length of a cyclic $m$-distinguishable sequence on $[k]$.

Take the sequence $S = 12234511335524$ of length $N = 15$ with $k = 5$ colors as an example. When $m = 2$, $S$ is both 2-distinguishable and cyclic 2-distinguishable. When $m = 3$, $S$ is 3-distinguishable but not cyclic 3-distinguishable because of $S_{13}(3) = \{1, 2, 4\} = S_{14}(3)$.

Let $S = s_0, s_1, \dots, s_{N-1}$ be a cyclic $m$-distinguishable sequence. It is easy to see that, for $t \in \mathbb{Z}_N$,

$$s_{t+1}s_{t+2}\cdots s_{N-1}s_0s_1\cdots s_t s_{t+1}\cdots s_{t+m-1} \quad (4)$$

is an $m$-distinguishable sequence. The method to produce the sequence in (4) is to “cut” the original cyclic sequence $S$ at the position $s_t$ and repeat the consequent $m-1$ elements. So, a sequence in the form (4) is called a $t$-cut of $S$.

The following upper bound on $N_m(k)$ is directly from the definition.

**Proposition 1.** For given positive integers $m$ and $k$, one has

$$N_m(k) \le \binom{k+m-1}{m} + m-1. \quad (5)$$

*Proof.* Let $S = s_0s_1 \cdots s_{N-1}$ is a longest $m$-distinguishable sequence. By definition, the $N-m+1$ multisets $S_t(m)$, $0 \le t \le N-m$, are all distinct. By representing each of these multisets as $\{1^{e_1}, \dots, k^{e_k}\}$, where $e_s$ indicates the multiplicity of the element $s$, those non-negative multiplicities must satisfy $e_1 + e_2 + \cdots + e_k = m$. Therefore, the number of all possible $S_t(m)$ is $\binom{k+m-1}{m}$, the number of non-negative integral solutions of the equation $e_1 + e_2 + \cdots + e_k = m$. It follows that $N-m+1 \le \binom{k+m-1}{m}$. $\square$

#### B. Universal Cycles and General Lower Bounds on $N_m(k)$

There are two combinatorial structures in literature related with cyclic $m$-distinguishable sequences: universal cycles [12] and universal cycles for multisets [13].

* Universal cycles (Ucycles): A $(k, m)$-Ucycle for $m$-subsets of $[k]$ is a cyclic $m$-distinguishable sequence $S$ in which every $m$-subset of $[k]$ appears exactly once as $S_t(m)$, for some $t$.

* Universal cycles for multisets (Mcycles): A $(k, m)$-Mcycle for $m$-multisets of $[k]$ is a cyclic $m$-distinguishable sequence $S$ in which every $m$-multisubset of $[k]$ appears exactly once as $S_t(m)$, for some $t$.

A $(k, m)$-Ucycle is of length $\binom{k}{m}$, while a $(k, m)$-Mcycle is of length $\binom{k+m-1}{m}$. By the action of $t$-cut, it is obvious that if a $(k, m)$-Ucycle exists, then $N_m(k) \ge \binom{k}{m} + m - 1$. And, if a $(k, m)$-Mcycle exists, then $N_m(k) = \binom{k+m-1}{m} + m - 1$ by Proposition 1.

We first consider Ucycles. As $m|\binom{k-1}{m-1}$ is the sufficient condition of the existence of a $(k, m)$-Ucycle, it was conjectured by Chung, Diaconis and Graham [12] that the necessary part holds as well whenever $k$ is sufficiently large. Recently, this conjecture was confirmed by Glock, Joos, Kühn and Osthus [14], see below for the completeness. Let $\mathbb{N} = \{1, 2, \dots\}$ denote the set of all positive integers.

**Theorem 2** ([14]). For every $m \in \mathbb{N}$, there exists $n_o \in \mathbb{N}$ such that for all $k \ge n_o$, there exists a $(k, m)$-Ucycle whenever $m$ divides $\binom{k-1}{m-1}$.

Let $p_{k,m}$ denote the longest length of a cycle such that each $m$-subset of $[k]$ appears at most once, which is called a $(k, m)$-Ucycle packing. The best known asymptotic result about Ucycle packings is due to Zhang [15].

**Theorem 3** ([15]). For $m \in \mathbb{N}$, one has $p_{k,m} = \binom{k}{m} - O(k)$.
We conclude this subsection by the following corollary, due to Theorem 2 and Theorem 3.

**Corollary 4.** Let $m \in \mathbb{N}$ and $k$ be a sufficiently large integer. Then,

$$N_m(k) \ge \binom{k}{m} + m - 1 \quad (6)$$

if $m$ divides $\binom{k-1}{m-1}$; and, there exists a constant $c$ such that

$$N_m(k) \ge \binom{k}{m} - ck + m - 1 \quad (7)$$

otherwise.

### C. Lower Bounds of $N_m(k)$ by Constructive Methods

This subsection is devoted to provide some constructive solutions to the existence of $m$-distinguishable sequences on $[k]$ for some small $m$. Let us first focus on Mcycles.

By definition, any permutation of $[k]$ is a $(k, 1)$-Mcycle. Let $G_k$ denote the complete graph of $k$ vertices labeled by elements in $[k]$. An Eulerian circuit of a graph is a circuit that contains all edges. See Fig. 3 (a) for an example. As such, any Eulerian circuit of $G_k$ (with a self-loop on each vertex) is a $(k, 2)$-Mcycle. As a graph contains an Eulerian circuit if and only if each vertex's degree is even, $(k, 2)$-Mcycles exist for all odd $k$. See [16, Theorem 1.2.26] for more details about Eulerian circuits.

Notice that an $(m, k)$-Mcycle exists if and only if $m$ divides $\binom{k+m-1}{m}$. The existence of Mcycles for $m = 3$ was verified in [13].

**Theorem 5** ([13]). For $k \ge 4$ with $k \equiv 1, 2 \pmod 3$, a $(k, 3)$-Mcycle exists.

As a $(k, m)$-Mcycle is a cyclic $m$-distinguishable sequence on $[k]$, the following result follows directly from Theorem 5 and aforementioned arguments on $m = 1, 2$ cases.

**Corollary 6.** One has

$$N_m(k) = \begin{cases} 1 & \text{if } m = 1, \\ \binom{k+1}{2} + 1 & \text{if } m = 2 \text{ and } k \equiv 1 \pmod 2, \\ \binom{k+2}{3} + 2 & \text{if } m = 3 \text{ and } k \equiv 1, 2 \pmod 3. \end{cases}$$

For the cases missing in Corollary 6 when $m = 2, 3$, we have the following lower bounds.

**Theorem 7** ($m = 2$). For any even $k \ge 2$, one has

$$N_2(k) \ge \binom{k+1}{2} + 1 - \frac{k}{2}.$$

*Proof.* Let $F$ be a 1-factor in $K_k$, that is, a collection of $k/2$ independent edges. Then, $K_k - F$ is an even graph, i.e., each vertex's degree is even. A 2-distinguishable sequence can be obtained by the following three steps.

(i) Find an Eulerian circuit in $K_k - F$.

(ii) Repeat the first occurrence of every element and denote by $S$ the obtained cyclic sequence.

<figure><img src="image_4.png" /><figcaption>Fig. 3. (a) An Eulerian circuit of $K_5$. The vertices that it travels is 1234513524 in order. (b) An Eulerian circuit of $K_6 - F$, where $F$ contains the three edges $\{1, 2\}, \{3, 4\}$ and $\{5, 6\}$. The vertices that it travels is 132451625364 in order.</figcaption></figure>

(iii) Pick an arbitrary $t$-cut of $S$.

Take Fig. 3 (b) as an example, where the Eulerian circuit is set to be 132451625364. Following the three steps, we have

$$\begin{align*} 132451625364 \xrightarrow{\text{(ii)}} & 113322445516625364 \\ \xrightarrow{\text{(iii)}} & 1133224455166253641, \end{align*}$$

where the last step is taken the 0-cut.

<figure><img src="image_5.png" /></figure>

**Theorem 8** ($m = 3$). For $k$ a multiple of 3, one has

$$N_3(k) \ge \binom{k+2}{3} - \frac{k}{3} + 2.$$

*Proof Sketch.* It suffices to show that there exists a cyclic 3-distinguishable sequence on $[k]$ of length $\binom{k+2}{3} - \frac{k}{3}$. The proof is proceeds by induction on $[k]$. Due to the page limit, here we only provide the recursive construction.

Assume as induction hypothesis that there exists a cyclic 3-distinguishable sequence on $[k-3]$ of the form $S'T'$, where:

* $S'$ is a cyclic 3-distinguishable sequence on $[k-6]$ and contains all 3-multisets of $[k-6]$ except the $\frac{k}{3}-2$ ones: $\{1, 2, 3\}, \dots, \{k-8, k-7, k-6\}$, and

* $T'$ is a cyclic 3-distinguishable sequence on $[k-3]$ and contains all 3-multisets of $[k-3]$ with at least one element from $\{k-5, k-4, k-3\}$ but excludes the one $\{k-5, k-4, k-3\}$.

We shall construct a cyclic 3-distinguishable sequence on $[k]$ of the form $WXYZ$, the concatenation of three subsequences $W, X, Y$ and $Z$.

Firstly, let $W = S'T'$. Next, let $X$ be a sequence obtained from $T'$ by replacing each $k-5$ by $k-2$, $k-4$ by $k-1$, and $k-3$ by $k$. Finally, the constructions of both $Y$ and $Z$ are divided into two cases according to the parity of $k$. For notational convenience, we use symbols $a, b, c, d, e, f$ to denote elements $k-5, k-4, k-3, k-2, k-1, k$, respectively. When $k$ is even, let

$$Y = \text{aaffc aeebb decec bddcc fbada dfbf,}$$

and

$$\begin{align*} Z &= \text{be}(k-6)\text{af}(k-7)\text{be}(k-8)\text{af}(k-9)\cdots\text{af1be} \\ &\quad \text{ad}(k-6)\text{ce}(k-7)\text{ad}(k-8)\text{ce}(k-9)\cdots\text{ce1ad} \\ &\quad \text{cf}(k-6)\text{bd}(k-7)\text{cf}(k-8)\text{bd}(k-9)\cdots\text{bd1cfe.} \end{align*}$$
And, when $k$ is odd, let

$$Y = \text{beblf abd1c ffaae cbfbf dadal eccfa eecdc bd,}$$

and

$$\begin{align*} Z ={}& \text{be}(k-6)\text{af}(k-7)\text{be}(k-8)\text{af}(k-9)\cdots\text{af}2\text{be} \\ & \text{ad}(k-6)\text{ce}(k-7)\text{ad}(k-8)\text{ce}(k-9)\cdots\text{ce}2\text{ad} \\ & \text{cf}(k-6)\text{bd}(k-7)\text{cf}(k-8)\text{bd}(k-9)\cdots\text{bd}2\text{cfe.} \end{align*}$$

<figure><img src="image_6.png" /></figure>

We use the following example to illustrate the construction given in Theorem 8.

**Example 1.** When $k = 9$, we pick

$$\begin{align*} & 11122\ 23331\ 16631\ 55224\ 53532\ 44336 \\ & 21414\ 62625\ 14365\ 55444\ 6665 \end{align*}$$

as a cyclic 3-distinguishable sequence on [6], where $S' = 111222333$ and $T'$ is the remaining segment. Then, by replacing each 4, 5, 6 in $T'$ by 7, 8, 9, respectively, we get

$$\begin{align*} X ={}& 11993\ 18822\ 78383\ 27733\ 92171 \\ & 79292\ 81739\ 88877\ 79998. \end{align*}$$

Since $k = 9$ is odd, we have

$$Y = 58519\ 45716\ 99448\ 65959\ 74741\ 86694\ 88676\ 757$$

and

$$Z = 58349258\ 47368247\ 693572698.$$

The resulting cyclic 3-distinguishable sequence on [9] is $S'T'XYZ$, which is of length 162. We get a 3-distinguishable sequence on [9] of length 164 by taking any $t$-cut.

In application, we can use $k = 9$ colors to label the $M = 164$ sensors using the above sequence, instead of 164 colors if using the simple straightforward protocol. The factor of reduction on the number of bits required for labeling each sensor is given by $\log_2(k)/\log_2(M) \approx 0.43$. We will discuss the gain by applying the proposed color coding protocol in more detail in the subsequent section.

**Remark 1.** The concept of cyclic $m$-distinguishable sequences was recently discussed in [17] and generalized to higher dimensional cases, called *grid colourings*. The key structure, *vector sum packing*, of the proposed solution is a cyclic $m$-distinguishable sequence with an assumption that the sums of any $m$ consecutive elements are all distinct. Therefore, the result does not cover ours herein.

## IV. COLOR CODING GAIN

In the following, we derive the color coding gain, i.e., the factor of reduction on the number of sensor ID bits or how much the proposed color coding protocol can help to speed up. Note that $L$ is the length of the line and $N = [L/\delta]$ is the number of deployed sensors.

For $m, N \in \mathbb{Z}^+$ with $m \le N$, let $\chi_m(N)$ denote the minimum value of $k$ for the existence of an $m$-distinguishable sequence of length $N$ on $[k]$. On the other hand, the notion $\chi_m^c(N)$ can be defined similarly for the cyclic case.

Note that the number of bits needed to represent an ID of a sensor in the straightforward protocol is $\log_2 N$, while in the multiset color coding protocol it is $\log_2 \chi_m(N)$.

Let $m$ be a fixed positive integer. For large enough $k$, by Corollary 4,

$$N \approx \frac{k^m}{m!}.$$

Then, we have

$$\begin{align} \log_2 N &\approx m \log_2 k - \log_2 m! \nonumber \\ &= m \log_2 k - (m \log_2 m - m \log_2 e + O(\log_2 m)), \tag{8} \end{align}$$

which implies that

$$\log_2 \chi_m(N) = \log_2 k \approx \frac{\log_2 N}{m} + \log_2 m - \log_2 e + \frac{c \log_2 m}{m}, \tag{9}$$

for some constant $c$. The identity in (8) is due to Stirling's approximation formula [18]. Therefore, by (9), the factor of reduction by the proposed color coding protocol is

$$\frac{\log_2 k}{\log_2 N} = \frac{1}{m}. \tag{10}$$

One can choose the value of system parameter $m$ for a preferred reduction factor at the cost of larger detection range of sensor, as a kind of implementation cost tradeoff.

## V. CONCLUSION

In this paper, we consider the tracking problem of an object that randomly appears on a line of a fixed length. We propose a newly defined color coding protocol with nice design which employs the minimal number of bits for labeling each sensor (i.e., representing their IDs), and show that the number of required IDs can be reduced by a factor $1/m$. Some corresponding sequence construction methods are provided. Besides, we derive the upper and lower bounds for the maximum length in general. Numerical examples have also demonstrated the substantial improvement by the multiset color coding protocol. It is worth noting that the proposed scheme can be generalized to multi-target tracking problem and also two-dimensional use scenario, which are left for future study. Another direction is to consider real-world factors and challenges such as interference, measurement errors and engineering practice.

## ACKNOWLEDGMENT

We would like to thank P. Baracca, P. Keevash, S. Kennedy, F. Liu, E. De Panafieu, A. Vetta and many colleagues for their continuous discussion and support.
REFERENCES

[1] T. Wild, V. Braun, and H. Viswanathan, "Joint design of communication and sensing for beyond 5G and 6G system," *IEEE Access*, vol. 9, pp. 30845–30857, Feb. 2021.

[2] N. V. Huynh, D. T. Hoang, X. Lu, D. Niyato, P. Wang, and D. I. Kim, "Ambient backscatter communications: A contemporary survey," *IEEE Commun. Surveys & Tutorials*, vol. 20, no. 4, pp. 2889–2922, May 2018.

[3] 3GPP, "New SID: Study on x-IoT," 3rd Generation Partnership Project (3GPP), Technical Specification 3GPP TSG RAN#97e, Sep. 2022.

[4] 3GPP, "Ambient IoT study on use cases and requirements," 3rd Generation Partnership Project (3GPP), Technical Specification 3GPP TSG RAN#98e, Dec. 2022.

[5] J. Kimionis, H. Huang, M. Eggleston, and H. Viswanathan, "6G B-IoT: Backscatter radio system for ultra-low power Internet of Things," *Nokia White Paper*, Apr. 2022.

[6] T. Etzion and A.Lempel, "Algorithms for the generation of full-length shift-register sequences," *IEEE Trans. Inf. Theory*, vol. 30, no. 3, pp. 480–484, May 1984.

[7] P. V. Kumar and V. K. Wei, "Minimum distance of logarithmic and fractional partial-sequences," *IEEE Trans. Inf. Theory*, vol. 38, no. 5, pp. 1474–1482, Sep. 1992.

[8] T. Etzion, "Constructions for perfect maps and pseudo random arrays," *IEEE Trans. Inf. Theory*, vol. 34, no. 5, pp. 1308–1316, Sep. 1988.

[9] K. G. Paterson, "Perfect maps," *IEEE Trans. Inf. Theory*, vol. 40, no. 3, pp. 743–753, May 1994.

[10] T. Etzion and E. Yaakobi, "Error-correction of multidimensional bursts," *IEEE Trans. Inf. Theory*, vol. 55, no. 3, pp. 961–976, Mar. 2009.

[11] A. M. Bruckstein, T. Etzion, R. Giryes, N. Gordon, R. J. Holt, and D. Shuldiner, "Simple and robust binary self-location patterns," *IEEE Trans. Inf. Theory*, vol. 58, no. 7, pp. 4884–4889, Jul. 2012.

[12] F. Chung, P. Diaconis, and R. Graham, "Universal cycles for combinatorial structures," *Discrete Math.*, vol. 110, pp. 43–59, 1992.

[13] G. Hurlbert, T. Johnson, and J. Zahl, "On universal cycles for multisets," *Discrete Math.*, vol. 309, pp. 5321–5327, 2009.

[14] S. Glock, F. Joos, D. Kühn, and D. Osthus, "Euler tours in hypergraphs," *Combinatorica*, vol. 40, pp. 679–690, 2020.

[15] X. Zhang, "Short *k*-radius sequences, *k*-difference sequences and universal cycles," *J. Combin. Des.*, vol. 28, pp. 509–524, 2020.

[16] D. B. West, *Introduction to Graph Theory*. Upper Saddle River, NJ07458: Prentice Hall, 2001.

[17] C. S. Chen, P. Keevash, S. Kennedy, É. de Panafieu, and A. Vetta, "Robot positioning using torus packing for multisets," *51st International Colloquium on Automata, Languages, and Programming (ICALP)*, 2024.

[18] J. Dutka, "The early history of the factorial function," *Archive for History of Exact Sciences*, vol. 43, pp. 225–249, 1991.