The middleware presented here deals with three different aspects. The first one is the need to provide a higher level of abstraction to simplify the development of WSAN applications. We believe that the publish/subscribe model is a feasible programming abstraction for WSANs and one that matches the reporting paradigm that a WSAN usually has, that is, a large number of nodes report their readings to a small number of data consumers. For the developers, it greatly simplifies the task of programming since they do not have to worry about low level communication primitives and can focus on the program logic rather than on how to distribute the data it generates. The second issue is that QoS support is essential for most modern applications, in particular for reliability, therefore the proposed middleware layer must be able to handle different QoS requirements. The final issue tackles the dynamicity of WSANs. WSANs are usually deployed in changing and adverse environments and therefore routing protocols should be able to handle new node additions or node failures. This, for example, means that the communication scheme should not only rely on a node’s physical addresses, because available nodes’ addresses can change over time if new nodes are added or existing ones fail. Also, because the publish/subscribe programming abstraction requires specific routing requirements such as the use of a multicast mechanism or to keep track of publishers and subscribers locations, the routing protocol must be able to provide these features.

PS-QUASAR is a lightweight middleware that provides a topic-based publish/subscribe scheme with an event/listener abstraction over the traditional message passing abstraction provided by all current WSAN platforms. The PS-QUASAR routing protocol is especially tailored to the publish/subscribe requirements. In other words, it connects multiple publishers to subscribers in a transparent way for the programmer and at the same time ensures that the QoS requirements are met. The PS-QUASAR middleware is composed of three different modules: PS-QUASAR Maintenance Protocol, PS-QUASAR Routing Module and the API.

Publish/subscribe programming model PS-QUASAR provides a lightweight topic-based publish/subscribe model suitable for wireless sensor devices, which are constrained devices in terms of size, cost, memory and bandwidth. Topic-based publish/subscribe means that the matching process between publishers and subscribers is done entirely on the basis of a topic name. A topic is simply a keyword that identifies the subject of the information generated by a publisher or the subject of the information that a subscriber wants to receive. In PS-QUASAR the topic name is encoded in a 16-bit integer for reasons of efficiency. Each piece of information generated by publishers is associated with a 16-bit integer (chosen by the developer and specified in the ps publish primitive). This information will be automatically delivered to nodes which have declared their interest in the same 16-bit integer (by means of the ps subscribe primitive). The publish/subscribe programming model provided by PS-QUASAR is really simple and easy to use. The simplicity of the model helps developers to implementWSAN applications without worrying about common low-level issues such as data packet encoding/decoding, message handling, etc.

The publish/subscribe programming model API is shown in this figure. The primitives are classified depending on whether they are called from the publisher or the subscriber side. The proposed publish/subscribe programming model is based on two different mechanisms: publish/subscriber primitives and listeners. The publish/subscribe primitives allow information to be transparently sent from publishers to subscribers. These two entities can be located in different nodes or in the same one. By doing this we use an homogeneous publish/subscribe approach that is used for all communications that are carried out in the network, either in a local or remote way. In the proposed publish/subscribe model, the QoS requirements are only specified on the publisher’s side. This simplifies the task of delivering information and avoids time-consuming QoS-matching algorithms. In DDS, for example, QoS is specified on both sides and only when the QoS policies are compatible does the communication take place. This however requires an additional matching algorithm or must rely on a central server that carries out this task. The QoS parameters offered are deadline, reliability and priority. Deadline is expressed in ms, reliability in number of node-to-node retransmissions. Priority is expressed as a number, the higher it is the more priority is given to the packet. Listeners are functions that are executed whenever a message is received by a subscriber. Only subscribers can make use of listeners to process received data. Listeners are specified as a parameter in the ps subscribe method. Listeners receive two parameters: the ID of the node sending the information and the data itself. In addition, the developer needs to specify the behavior of the main function. This function is called once, upon initialization. From it, subscriptions are chosen (ps subscribe) and publish methods can also be called. For example if periodical reporting is needed, periodical timers are set in the main function.

Maintenance protocol

Tree-based routing protocols usually require a maintenance protocol that allows each node to find its neighbors and coordinate them to form a tree. One of the classic algorithms to form a routing tree in a distributed manner is the Bellman-Ford algorithm. The algorithm maintains a table at each node with the best known distance to each destination (subscriber) and where it has to relay the information to get there. This distance is iteratively updated by exchanging information with its neighbors. Eventually, each node in the network is able to find the shortest distance to the destination. The distance is typically measured as the number of hops towards the destination. One identified issue in the Bellman-Ford algorithm is the count-to-infinity problem.

The PS-QUASAR routing protocol is based on a tree-based routing protocol and as such requires a maintenance protocol. The proposed maintenance protocol is a modified version of Bellman-Ford algorithm. The maintenance protocol is based on periodical beaconing to exchange node information (e.g. remaining energy) and subscriber information. Node information is used to meet QoS requirements. All nodes periodically broadcast a maintenance packet with information about themselves and also with information about the subscribers that are accessible from the current node. In every node, information about the subscribers found so far and information about the neighbors are kept in a local table. This table keeps track of all the subscribers discovered so far and all the possible neighbours through which the node can relay the information to make the packet reach the subscriber. Because of this, PS-QUASAR routing protocol is not strictly a tree-based routing protocol but rather a directed acyclic graph based protocol. All possible next-hop that are part of minimum distance paths are stored and are taken into account during the routing process. If one of the paths with minimum distance towards the destination fails the others are still available and the routing protocol will continue to operate normally. Only when all paths with minimum distance fail will the unsubscription/ failure protocol presented be executed.

Two facts can be deduced from the proposed maintenance protocol. The first is that all nodes in the network are aware of the number of subscribers and how to reach them and the second is that multiple paths towards each subscriber are identified. The first fact means that in PS-QUASAR all nodes in the network can act as publishers without having to notify of this fact in advance (unlike traditional publish/subscribe systems). The second means that PS-QUASAR can select the most suitable path towards a subscriber based on the state of the network.

PS-QUASAR routing protocol

The PS-QUASAR routing protocol uses a weight function to evaluate each of the neighbor nodes to which it can relay data packets. The PS-QUASAR weight function that evaluates the importance of each path from a node towards a subscriber based on the information it has about the network and about the neighbor. By defining this function so that it takes into account different parameters such as LQI (link quality indicator), remaining energy, traffic, etc, routing decisions can be customized to tailor the protocol behavior to the need of the users. The weight function can be configured to discard certain nodes which do not want to be considered as relay nodes. The weight function is the mathematical tool that shapes the behavior of the routing module.

PS-QUASAR does not cache information. The information is sent as soon as it is produced by means of a directed acyclic graph based routing protocol. The PS-QUASAR routing protocol extends the concept of a simple routing tree to make use not only of one path towards each subscriber but to use as many paths as possible. To achieve this, nodes establish links with each other to form a directed acyclic graph for each of the publishers in the network. Although this implies that more memory is necessary to keep the information about all adjacent nodes, the number of neighbors a sensor node has, even in dense networks, is relatively small. This extra memory can be handled perfectly well by current sensor nodes.

The PS-QUASAR routing protocol dynamically adapts its behavior to the neighbor status to route the packets using different paths and allows the information to be transmitted with certain QoS policies. The use of multiple paths towards the subscriber node improves the energy efficiency of the algorithm. The routing protocol uses the information collected by the maintenance module to send data packet associated with a topic to all subscribers of that topic in the network.

PS-QUASAR proposes a publish/subscribe programming model that allows multiple subscribers to declare their interest in the same topic. Because of that, data associated with a topic may need to be delivered to more than one node in the network. One option would be to send a packet for each of the subscribers in the network. This however, generates unnecessary traffic as the same information is duplicated. To optimize this type of communication PS-QUASAR proposes a multicast mechanism.In general terms, packets are not duplicated whenever possible unless the network topology requires it.

The routing module takes the information that the maintenance protocol collects and reuses paths whenever possible when more than one subscriber of a topic is detected. If subscribers cannot be reached by relaying to the same direction then packets are duplicated. In order to control duplicate packets a packet field called “Already notified” is used to tell the nodes the list of subscribers that do not need to be notified to the nodes. This field contains a list of all subscriber ids that are being notified by other packet duplicates or that have already being notified.

QoS

In PS-QUASAR, reliability deals with increasing the probability with which packets are transmitted whereas priority finds short paths towards the destination based on the importance of the packets. Reliability is achieved using node-to-node retransmission. Priority is handled by means of queues where incoming and outgoing packets are ordered according to their importance. Priority is specified as an integer number that is stored inside each packet. Finally, PS-QUASAR provides a deadline mechanism that allows packets to be discarded if their deadline has expired before reaching destination. The user can specify a deadline that expresses the maximum time allowed for the packet to reach the destination. In PS-QUASAR, the deadline, if specified, is stored in a field in each data packet and updated everytime is relayed. Whenever a deadline field of a packet is updated and the resulting value is less or equal to 0 the packet is discarded.

Evaluation

The prototype of the algorithm has been implemented in C programming language for the TelosB motes running the Contiki operating system. The resulting code has been simulated using the Cooja simulator. The Cooja simulator emulates TelosB motes at machine code instruction set level. The communication model takes into account packet loss when nodes are transmitting at the same time. The test scenario is composed of a network of 110 nodes arranged in a grid and a total of 5 subscribers and 9 publishers dealing with data from 3 different topics: temperature (TM), humidity (HM), linear displacement (LD). Publishers/ subscribers are marked with square/diamond/triangle symbols indicating that they produce/ receive data from TM/HM/LD topics respectively. The communication in this scenario follows a many-to-many communication pattern that allows the features of our algorithm to be analyzed.

The results obtained show that PS-QUASAR successfully identifies suitable paths toward each of the subscribers and can effectively handle QoS. All the evaluation details and results can be found here.