Papers for

wireless sensor network developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Grid navigation algorithm disperses agents efficiently in optimal time

Beyond the Boundary: Optimal Grid Dispersion by Spread, Reverse, and Collect

Abstract: \emph{Dispersion} requires a set of mobile agents to occupy distinct nodes of a graph such that each node contains at most one agent. We study deterministic dispersion of $k\le n$ agents on an $n$-node oriented square grid, where each node has globally consistent North, East, South, and West port labels, from arbitrary initial configurations. This includes both \emph{rooted} configurations, where all agents are co-located initially, and \emph{general} configurations, where agents are initially distributed arbitrarily across the nodes. On oriented square grids, Kshemkalyani, Molla, and Sharma~\cite{KMS20} gave an $O(\min(k,\Side))$-round algorithm in the local-communication model, where only agents on the same node can exchange information, and an $O(\sqrt{k})$-round algorithm in the global-communication model, where any two agents can communicate regardless of position, both using $O(\log k)$ bits per agent. The bound in the local communication model is optimal when $k=Θ(n)$, but it remains open whether local communication alone can match the $Ω(\sqrt{k})$ time lower bound when $k=o(n)$. We solve this by presenting \textsc{Spread--Reverse--Collect} (SRC), a deterministic algorithm that disperses any $k\le n$ agents in $O(\sqrt{k})$ synchronous rounds using $O(\log k)$ bits of persistent memory per agent, matching both time and memory lower bounds. SRC is based on a geometric primitive, a \sharpS-shaped parallel sweep, together with a simple priority rule. Unlike earlier grid algorithms that gather agents at the boundary and spread out from there, each SRC sweep starts from the agents' current position, and when it reaches the boundary the group simply reflects its sweep back inside and continues. SRC therefore needs no knowledge of the grid size and runs unchanged on an infinite oriented grid.

Mon 12 OctDistributed, Parallel, and Cluster Computing
The gist
The problem is to move multiple agents on a grid so each ends up on a different square without overlap. Previous methods needed either slow or complicated communication. The authors present a new way to spread agents using a zigzag sweep that goes out and then back inside the grid, requiring no knowledge of the grid size. This approach is faster for small groups of agents and uses limited memory, matching known theoretical limits.
Open → 2610.16935v1