Project PASA, Passive Broadcast for Smartphone Ad-hoc Networks


The Problem:

The location based service plays an important role in users' daily life. For example, users use Yelp to check out the restaurants around; Foursquare is popular for checkin and receive coupons. If you wanna chat with someone nearby, wechat is one of your choice. These location based services have some common features,
  • It is fast (wifi / LTE).
  • It can deliver large amount of information.
  • Based on user provided data.
  • configurable radius (controlled by server).
However, they also have some limitations,
  • It has a centralized architecture.
  • Based on GPS or indoor localization.
  • Radius too large than we need.
  • Require internet access.
  • The “nearby” data may not updated.

What we need,
  • Decentralized model
  • Work under indoor environment / without internet access
  • Short range communication
  • Get what we are interested

Our Solution:

We inroduce PASA that utilizes Bluetooth service discovery process to passively share information with others nearby.


During a service discovery process, for example, A starts the discovery , others inside its communication range (upto 100m) and in the discoverable status respond A with its device name, type, MAC address, etc. PASA uses devices name as an information carrier for transmission.

Message format:
  • Payload
  • Header : 1 Scanning interval; 2 Index range of active messages; 3 Message reception feedback



The Challenges:
 

Since devices name is not initially designed for data transfer, PASA encounters some challenges,
  • Device name length : Usually, the protocol only allowed upto 248 bytes for the device name
  • Frequency hopping: Bluetooth service discovery scan the channels consecutively
To overcome the length limit of a device name, we need to split the long message into smaller ones. However, due to frequency hopping feature, their is a probability that during a discovery process A can not receive others' most recent messages.


Reception probability, P(x,y):

P(x,y), the probability that a phone with scan interval of x can receive a message from another phone with update interval of y.

1.      y ∊ (0, x)

2.    y ∊ (0, x+S)

3.   y ∊(S, x+2S)





The Evaluation:
  

 
  • Implement PASA on Android with Twitter
  • Experiments consist five smartphones
  • Simulation for the large testing
                          
Experiment Settings:
  • Case 1: The same scan interval (T) and number of messages (k)
  • Case 2: Different T but the same k
  • Case 3: Different k but the same T
  • Case 4: Both T and k are different.
Evaluation metric: Find the optimal update interval  from our theoretical model and compare it with experiment and simulation






Case 1 (experiment):
 
 
Case 4 (simulation):





Publication :

PASA: Passive Broadcast for Smartphone Ad-hoc Networks
[ICCCN'14 ]The IEEE International Conference on Computer Communications and Networks.