Finding an optimal key assignment (subject to given constraints) for a key
predistribution scheme in wireless sensor networks is a difficult task. Hence,
most of the practical schemes are based on probabilistic key assignment, which
leads to sub-optimal schemes requiring key storage linear in the total number
of nodes. A graph theoretic framework is introduced to study the fundamental
tradeoffs between key storage, average key path length (directly related to the
battery consumption) and resilience (to compromised nodes) of key
predistribution schemes for wireless sensor networks. Based on the proposed
framework, a lower bound on key storage is derived for a given average key path
length. An upper bound on the compromising probability is also given. This
framework also leads to the design of key assignment schemes with a storage
complexity of the same order as the lower bound.