Distinct Difference Configurations: Multihop Paths and Key Predistribution in Sensor Networks

DOI10.1109/TIT.2010.2050794MaRDI QIDQ5281354zbMATH OpenFDO

Authors Simon R. Blackburn, Tuvi Etzion, Maura Paterson, Keith M. Martin

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.3896

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: A distinct difference configuration is a set of points in $mathbb{Z}^2$ with the property that the vectors (emph{difference vectors}) connecting any two of the points are all distinct. Many specific examples of these configurations have been previously studied: the class of distinct difference configurations includes both Costas arrays and sonar sequences, for example. Motivated by an application of these structures in key predistribution for wireless sensor networks, we define the $k$-hop coverage of a distinct difference configuration to be the number of distinct vectors that can be expressed as the sum of $k$ or fewer difference vectors. This is an important parameter when distinct difference configurations are used in the wireless sensor application, as this parameter describes the density of nodes that can be reached by a short secure path in the network. We provide upper and lower bounds for the $k$-hop coverage of a distinct difference configuration with $m$ points, and exploit a connection with $B_h$ sequences to construct configurations with maximal $k$-hop coverage. We also construct distinct difference configurations that enable all small vectors to be expressed as the sum of two of the difference vectors of the configuration, an important task for local secure connectivity in the application.

Cited in

(5)

• Key predistribution schemes for distributed sensor networks via block designs
• A unified approach to combinatorial key predistribution schemes for sensor networks
• The rise and fall and rise of combinatorial key predistribution
• Problems on Two-Dimensional Synchronization Patterns
• On the Applicability of Combinatorial Designs to Key Predistribution for Wireless Sensor Networks

This page was built for publication: Distinct Difference Configurations: Multihop Paths and Key Predistribution in Sensor Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281354)