Congestion in cellular networks

During the WWRG meeting today, Kamran mentioned a problem about congestion in the cellphone networks in crowded places. It is indeed a valid problem because each cell can only accomodate a maximum number of users and the provisioning is always done for an average load.

I suggested that one way to get around this would be through the use of cellular relays. Most cellphones now have WiFi and Bluetooth that can form an adhoc network to transport messages or push-to-talk packets out of a congested cell into a neighboring vacant cell. This solution is well known, but the problems with implementation are incentives on why should somebody forward messages from an unknown person at the expense of his battery, and how to handle security in this case where possibily neither cellphone can connect directly to the outside network.

Incentives can be built through a notion of long term fairness using brownie points. Each time somebody forwards somebody else's messages, he earns points. He can encash these points later when he is in a situation where he needs to use the same (or a different) service from another person. How to ensure security in this so that tokens for brownie points cannot be impersonated, cannot be replayed, and cannot be stolen? My paper with Keshav on Practical Security for Disconnected Nodes is perfect in this situation. Slides about the protocol details are also available.

Message secrecy can also be ensured using the techniques outlined in our paper.