  This paper considers a data collection network consisting of uncoordinated,
heterogeneous, and possibly mobile devices. These devices use medium and
short-range radio technologies, which require multi-hop communication to
deliver data to some sink. While numerous techniques from managed networks can
be adapted, one of the most efficient (from the energy and spectrum use
perspective) is \emph{network coding} (NC). NC is well suited to networks with
mobility and unreliability, however, practical NC requires a precise
identification of individual packets that have been mixed together. In a purely
decentralized system, this requires either conveying identifiers in headers
along with coded information as in COPE, or integrating a more complex protocol
in order to efficiently identify the sources (participants) and their payloads.
  This paper presents a novel solution, Network Coding with Random Packet Index
Assignment (NeCoRPIA), where packet indices in NC headers are selected in a
decentralized way, by simply choosing them randomly. Traditional network
decoding techniques apply directly when all original packets have different
indices. When this is not the case, i.e., in case of collisions of indices, a
specific decoding algorithm is proposed. A theoretical analysis of its
performance in terms of complexity and decoding error probability is described.
Simulation results match well the theoretical results. Comparisons of NeCoRPIA
header lengths with those of a COPE-based NC protocol are also provided.
