This may be a good lead on prior art. Unfortunately, the Wikipedia article itself doesn't qualify: Its earliest version dates back only to 2003; the original provisional patent application was filed in 2002.

The Street Performer Protocol definitely predates the patent, although I don't know if it directly addresses the claims of the patent:

http://www.schneier.com/paper-street-performer.html