Prof. Dr. Adrian Perrig

aperrig

Prof. Dr. Adrian Perrig

CAB F 85.1
Universitätstrasse 6
8092 Zürich

Phone: +41 44 632 99 69
E-Mail: adrian.perrig@inf.ethz.ch



Our main project is on the SCION secure Internet architecture.
We have founded Anapaya Systems, a startup to commercialize SCION technology.

Publications

by Haowen Chan and Adrian Perrig
Abstract:
The efficient subdivision of a sensor network into uniform, mostly non-overlapping clusters of physically close nodes is an important building block in the design of efficient upper layer network functions such as routing, broadcast, data aggregation and query processing. We present ACE, an algorithm that results in highly uniform, near optimal sized cluster formation. By using the self-organizing properties of three rounds of feedback between nodes, the algorithm induces the emergent formation of clusters that are a near-optimal cover of the network, with significantly less overlap than the clusters formed by existing algorithms. The algorithm is scale-independent — it completes in time proportional to the deployment density of the nodes regardless of the overall number of nodes in the network. ACE requires no knowledge of geographic location and requires only a small constant amount of communications overhead.
Reference:
ACE: An Emergent Algorithm for Highly Uniform Cluster Formation. Haowen Chan and Adrian Perrig. In Proceedings of European Workshop on Wireless Sensor Networks (EWSN) 2004.
Bibtex Entry:
@InProceedings{ChaPer2004,
  author = 		 {Haowen Chan and Adrian Perrig},
  title = 		 {{ACE}: An Emergent Algorithm for Highly Uniform Cluster Formation},
  url = {/publications/papers/ewsn04.pdf},
  booktitle =	 {Proceedings of European Workshop on Wireless Sensor Networks (EWSN)},
  year =		 2004,
  month =		 jan,
  abstract =	 {The efficient subdivision of a sensor network into uniform, mostly
non-overlapping clusters of physically close nodes is an
important building block in the design of efficient upper layer
network functions such as routing, broadcast, data aggregation and
query processing.

We present ACE, an algorithm that results in highly uniform, near
optimal sized cluster formation. By using the self-organizing
properties of three rounds of feedback between nodes, the algorithm
induces the emergent formation of clusters that are a near-optimal
cover of the network, with significantly less overlap than the clusters
formed by existing algorithms. The algorithm is scale-independent ---
it completes in time proportional to the deployment density of the
nodes regardless of the overall number of nodes in the network. ACE
requires no knowledge of geographic location and requires only a small
constant amount of communications overhead.}
}