Seems some learning from p2p networks like Gnutella could be used, where some nodes become "supernodes", used to maintain routing details for nodes further afield, whilst other nodes just maintain routing to nearby supernodes. When one node needs to talk to another, it can query its nearest supernode(s) for this information, and then cache it locally.