2 Implementing reverse localisation

2.1 Cellular reverse localisation

The naive approach to the implementation of a reverse localisation function is to cover the space with cells ^[2] . For each cell there is a server which is kept informed of the communicating objects located within (or associated with) the cell area.

To know the objects situated in a given location, one just needs to request them from the server of the corresponding cell (for local reverse localisation one's own cell server). This approach has many problems.

2.1.1 Cell operating cycle

When an communicating object enter a cell, it must inform the corresponding server: How does the object know in which cell it is located? Does it know its position (then it need local localisation) and the geometry of all the cells?

Moreover, a network allowing communication with one's cell server is needed, and only the communicating objects that are enabled for this telecommunication network will be taken in account.

A solution could be that given as a fact that an object is probably in communication with some of its neighbors (that means that local reverse localisation is partially available) will be able, by this means, to know in which cell it is located and tell the corresponding neighbour about its presence.

2.1.2 Deployment and coverage

Prior to the adoption by most of the communicating objects, the coverage (or the promise of coverage) should have an extension wide enough, and that without knowing exactly how to dimension the system:

The coverage level depends on the system's success:
- Cells must be smaller if the number of communicating objects is large
And the system success depends on the coverage level
The system will be adopted by a high number of communicating objects only if the coverage is wide enough and the cells small enough to handle the objects' density.

In addition, complex financial mechanisms (billing, peering agreements, who pays what etc) should be implemented to put up the money for the cell servers and all that without knowing how much income the reverse localisation will generate.

2.1.3 Scalability

Since cells can only handle a limited number of communicating objects, a cell can become overloaded at any moment (meanwhile other cells might be nearly empty). Therefore, the system that determines the cell areas and boundaries should be highly dynamic (particularly in respect of adding new cell servers) and oversized.

2.1.4 Conclusion

Although it is technically feasible , the cell-based approach is probably unrealistic unless the cells have other applications. For example, it might be interesting to add reverse localisation functions to the GSM and/or the UMTS equipments and networks. In this manner it will be possible to gather the GSM/UMTS devices that are present in a given cell.

2.2 Reverse localisation using a network of peers

Another approach, inspired by peer-to-peer, gnutella-like systems or ad hoc networks, is conceivable. In this approach, the communicating objects participate and collaborate to provide the reverse localisation function. The communicating objects organise themselves into a peer network in which each participates depending on their capabilities (energy, bandwidth, CPU etc).

In this system there is no need for dedicated resources and the resources of the system are provided by the end users.

2.2.1 How it works

Let us start with the hypothesis that each communicating object is aware of and able to establish a communication with its nearby neighbors and hence that it implements local reverse localisation. At first glance, this hypothesis may seem paradoxical since it states that prior to implementing local reverse localisation we need local reverse localisation.

But the paradox is only apparent and means indeed that the property (knowledge of and ability to communicate with surroundings neighbors) is maintained (at least partially) most of the time, by most of the communicating objects and that the communicating objects should work constantly to maintain the property.

This property (and also local reverse localisation) can be extended to software-only communicating objects related to a location ( eg a database or any software object related to a given location) that can be considered in this case to be virtually present at the location and participating in the peer network like any object physically present at the location.

2.2.2 Maintaining the network of peers

Keeping knowledge of the vicinity is performed by neighborhood collaboration: communicating objects at an given place inform one another of the approach and moving away (the appearance and removal) of the communicating objects they know.

Knowledge and communication with the neighbors can be achieve using either a short-medium range network ( eg bluetooth or and ad hoc network), or a global network ( eg UMTS), or both.

It is worth noting that the more dynamic the network (mobility communicating objects), the greater the number of exchanged messages (up to the extreme limit of a system changing too fast to function). If some peers are permanently associated with a location (kind of "servers") they help stabilizing the peer network around this location. Any non moving physical object or any logical object, permanently associated to a location, may play this "server" stabilizing role.

2.2.3 Reverse telelocalisation

The problem is the following: How to "interrogate" from far the local reverse localisation "service"? How to know which communicating objects are located in a given place?

Since every communicating object (element of the peer network) knows its neighboring objects, to know the whole communicating objects located at a place it is enough to interrogate one of these objects.

Also, as soon as a given object knows the communicating objects in a particular area (and if it is able to communication with them), it is possible to assume that the object is virtually located in that area and integrate it into the peer network. In this way it will participate in maintaining the peer network and help in providing the reverse telelocalisation function. The association with this area or place is not arbitrary, since the object not only knows the (objects located in the) place, but by calling the reverse telelocalisation function it has shown a clear interest in the place.

The reverse telelocalisation system is a relational network (a graph) of either logical or physical communicating objects. Each node or object knows its own, either virtual or physical, position (a least approximately) and it is able to communicate with its neighbors (it may be able to communicate with further objects).

To identify the communicating objects that are located in an given place (reverse localisation), one just finds, to begin with, one communicating object (physical or logical, mobile or motionless) that is located in that place and then enquires of this object about its neighbors (these objects may be also requested if necessary); so step by step, all the objects in that area will be eventually known. The first object or starting point is found using distributed search techniques (a la gnutella) within the peer network.

2.2.4 Conclusion

Reverse localisation of communicating objects is not provided by the deployment of servers or equipment but by the organisation of all communicating objects concerned in a peer network (each object has, a priori , the same role) in which all the participants collaborate in providing, one to another, the reverse localisation service.

However, this approach is not incompatible with the notion of a cell and it is possible, if there a background business logic, to deploy reverse localisation "servers", i.e. motionless communicating objects that are (totally or partly) dedicated to the reverse localisation of a area (around their position).

The advantage of using a peer network is that the deployment costs are minimal and the available resources are utilised to their maximum, all with very low cost of administration and maintenance. The main disadvantage is that no quality of service (in terms of response delay, spacio-temporal availability, accuracy, exhaustiveness etc) can be completely guaranteed . The user have to conform to the available service (more than often nothing but sometimes satisfactory).

^[2] Cell like in cell phone, eg CDMA or GSM.