Bigraphs were originally proposed as a model for the behaviour of ubiquitous systems since interaction between mobile devices is dependent on both placing (locality) and linking (connectivity). However, there has yet to be a bigraph that represents the complete physical world. Such a bigraph will enhance the computer's representation of its location from a simple latitude-longitude pair to a context more familiar to humans: the room it is in, the street the building is on, and the town the street is in. This will allow for location-aware applications and policies about connectivity of mobile devices to work based on the defined locality of buildings, streets and administrative regions.
The physical world has also long been represented by maps. OpenStreetMap
(OSM) is a freely-licensed geographic database built by a community of
volunteers through the annotation of data collected through surveys, aerial
imagery and other free geodata sources. Boasting a user base of 10 million, OSM
has labelled buildings, streets and regions with impressive detail comparable
with commercial counterparts. The map elements are supplemented with key-value
pairs called "tags" that describe characteristics of the element. Tagging
conventions vary across countries, but there are standard practices such as the
addr tag on buildings to describe its address.
This project will demonstrate modelling the physical world as a bigraph. Places marked on OSM will be hierarchically structured in a place graph, guided by administrative boundaries such as country, state, city etc. Then, a link graph will be built on top of the place graph to model the network of connected streets. The use of such bigraphs for ubiquitous systems will be demonstrated with the use case of Bluetooth connectivity, using reaction rules that allow devices to move to a new place and form links with other devices in its proximity.
1 Outcome
Roy Ang finished this as a Part II dissertation in 2025, published as Building Bigraphs of the real world. It partitions every building, street and administrative area in OpenStreetMap into a hierarchical space-partitioning tree and encodes that as a bigraph, so the place graph carries containment and the link graph carries the street network. The tool is written in OCaml and builds a bigraph for a region anywhere in the world.
The map was not the whole of it. The open source bigraph tools could not construct or transform graphs of this size, so the dissertation also contributes algorithmic improvements to them, worth up to a 97 times speedup.
The spatial networking architecture this work fed into is written up in An Architecture for Spatial Networking, with Josh Millar, Ryan Gibb and Hamed Haddadi. Bifröst uses bigraphs to express containment and connectivity at once, which is what lets a policy be scoped by a physical boundary and a device be named by the place it is in.