Paper Menu >>
Journal Menu >>
![]() Wireless Sensor Network, 2010, 2, 612-628 doi:10.4236/wsn.2010.28073 Published Online August 2010 (http://www.SciRP.org/journal/wsn) Copyright © 2010 SciRes. WSN A Real-Time-Enabled, Blackboard-Based, Publish/Subscribe Architecture for Wireless Sensor Nodes Björn Stelte Faculty of Computer Science, Universität der Bundeswehr München, München, Germany E-mail: bjoern.stelte@unibw.de Received May 6, 2010; revised May 18, 2010; accepted May 25, 2010 Abstract Wireless sensor network nodes have only limited resources concerning memory and battery life-time. Mem- ory can be efficiently used by sharing data, and the life-time of a battery can be extended, when the node has long power saving sleep-phases. We propose a publish/subscribe architecture that achieves these two aims. The results of our work are of great interest for sensor application developers, giving them now the opportu- nity to use our architecture for sharing data among different applications on the node as well as the different layers of the operating system. We introduce a blackboard which is used for centrally storing published val- ues, like measured data from a monitored sensor. This makes it possible to share stored data without moni- toring the sensors once again, which is advantageously concerning power consumption, memory space, and reaction time. Beside the proposed publish/subscribe method for sensor nodes with its notification possibili- ties, our architecture fulfills also real-time requirements. We show how the well-known sensor operating system MANTIS OS can be extended by a real-time enabled, blackboard-based publish/subscribe architect- ture. This architecture and first of all its implementation is of special interest for cross layer optimization of sensor applications. Cross-layer approaches benefit from our architecture because the available implementa- tion can be used as an efficient framework for central storing and managing of shared values. Keywords: Blackboard, Real-Time, Publish/Subscribe Architecture, Wireless Sensor Network 1. Introduction Today, sensor nodes are on the one hand small in size and economically cheap to produce, but on the other hand the applications on the nodes get more and more complex. So an application developer has to cope with limited re- sources, like memory space, power consumption, and CPU performance. Resource-sharing can moderate the resource limitations. In this paper the sharing of informa- tion between program parts is considered, not the com- munication between devices. A resource-sharing system enables parts of the system to share information. A system that uses continuous que- ries for the resource-sharing is called publish/subscribe system. The continuous queries are the subscriptions and the submitter of the queries are the subscribers. If a new value is published by a publisher, this event triggers an inquest whether at least one of the queries is matching. So the system handles all publications and subscriptions as well as the notification process. An good example for a publish/subscribe system can be found at the stock exchange. Because the price of a share is fluctuating, a profit is possible as long as a prospective customer buys the share when the price is low and sells it later when the price has risen. Assumed that the customer is willing to maximize his total profit, he will observe more than only one share at the same time. But the more shares the customer has in its portfolio, the more complex gets his situation. At the stock exchange a publish/subscribe notification system is often used to moderate the complexity. Cus- tomers submit subscriptions with the name of the share and a threshold value for the price of the monitored share to a notification system at the market. This allows to have more than one subscriber for the same subscription. So instead of having several customers monitoring a share, the system does the job for them. If the given price is reached, then the system tries to immediately inform all relevant subscribers. So at the stock exchange a publish/subscribe notifica- tion system is very useful. The system provides advan- tages for both the customer and the stock exchange. The ![]() B. STELTE613 customer displaces the monitoring process to the system and saves time, because he gets a notification of his sub- scribed event as requested. The stock exchange benefits from the publish/subscribe system, because the number of customer queries is reduced dramatically. Secondly, the same continuous queries from different submitters can be summarised to one query for all interested subscribers. To sum up, resources are spared, if a publish/subscribe sys- tem is used for sharing stock information. 2. The Publish/Subscribe Paradigm For a dynamic interaction between components, asyn- chronous communication models are used, like message passing, broadcast, and publish/subscribe. Eugster et al. Describe in [1] that only the publish/subscriber commu- nication fully assists all three decoupling dimensions, which are the time, space and synchronization decoup- ling. Karl and Willig explain in [2] as well as Köpke et al. in [3] that also a WSN application can benefit from the publish/ subscribe paradigm. So before analyzing the suitability of publish/subscribe for sensor node applica- tions, we should have a deeper look at the publish/ subscribe basics first. A subscriber is not interested in all events a publish/subscribe service may support. So the subscriber specifies the events it is interested in and cuts the amount of all possible events towards its interest. There are three different types of subscriptions possible, namely. 1) Topic-based 2) Content-based 3) Type-based At a topic-based publish/subscribe scheme, participants subscribe to a topic or subject, which is identified, e.g., by keywords. This is like joining a group, where pub- lished data for the group is forwarded to all group members. A mailing list is a good example for this type of pub- lish/subscribe, where every topic is like an event ser- vice of its own. In a content-based publish/subscribe scheme, the decision if a subscriber gets a notification or not, is based on present keywords in the content of the event. A subscriber defines filters or constraints, which identify valid events. If a published value fulfills the subscription filter, the notification service informs the active sub- scriber. The other way round, if it is not valid the sub- scriber gets no notification message. The type- based publish/subscribe variant enables the subscriber to specify in which kind of values it is interested in. An event can be of different subtypes, e.g., a number could be of the type’s integer or float. Type safeness may be an argument to use this type of publish/subscribe scheme. The content-based scheme is an extended form of the topic based one. At the topic-based publish/subscribe, every publication is for- warded to every subscriber of the event. The con- tent-based scheme uses an addition filter, allowing to notify only all subscribers of the event with a matching subscription. 2.1. Publish/Subscribe Architecture for Sensor Nodes Especially for distributed system publish/subscribe ar- chitectures are widely available. So if such an architecture is fitting for a sensor node, we can use the architecture for an implementation. But unfortunately, these classical publish/subscribe architectures are not suitable to sensor nodes, because they pay no attention to the before men- tioned resource limits of sensor nodes. As Köpke et al. describe in [3], a blackboard can be used for storing shared values at a central point. Within a data-centric control interface, setting and accessing data is possible. In their implementation for TinyOS, they use a publish/subscribe based control interface. The interesting part is how they solved the space problem which leads to the fact that concepts like the well-known Elvin concept is being unimplementable for WSNs. Köpke et al. use a blackboard for storing the data. In their implementation, each published information is defined by a unique number, a so called notification event number. A publisher writes its data on the blackboard and then informs the blackboard about the publication. Because of the unique event num- ber, the publisher can tell the blackboard the corre- sponding event for the published value. The blackboard itself consists of three elements: the index table, the sub- scriber table and the subscriber flags. The tables are of constant size, which have to be calculated at compile-time. The index table consists of two entries for each event, namely the event offset and the event count. The offset value states the relative start position of the event at the subscriber table and subscriber flags. The count value gives the amount of subscribers for the event. So the index table has a size of twice of the number of events. The subscriber table stores the handlers for each subscriber. The position of the handler can be calculated from the offset value in the index table. An entry in the subscriber array has two flags for each subscriber. The first flag is the published flag and the second one is the subscribed flag. The published flag is set if an event is published for the subscriber. The subscriber flag is set only if the subscriber is currently subscribed to the event, otherwise the flag is clear. Subscriptions and unsubscriptions can be done at run-time, but the storage for the subscriber is reserved at compile time. The subscriber flags are stored in RAM, all other tables are transferred into the program structure at compile time. So the concept uses a minimal amount of RAM storage. This is effective and safes memory because of a central storage. But the concept has the disadvantage of being not flexible. The number of events and sub- scribers, and also the handler addresses have to be known Copyright © 2010 SciRes. WSN ![]() B. STELTE 614 at compile time. A modification at run-time is not possible, because the storage is in ROM. So a subscriber can not declare it is interest in an event at runtime, this is done at compile time. The unsubscribe functionality is more like a pause function, where the subscriber declares its not willing to get more notifications at this point in time. The concept uses the publish/subscribe paradigm for decoup- ling in space and time. In Köpkes concept subscribers can only make a topic-based subscription for an event. On every event change they get notified if their subscription is active. The subscribers are notified by calling the function whose address is stored at the handler field. 2.2. Static Data Storage Köpke’s concept allows only topic-based and static sub- scriptions. Our idea is to extend the given concept to a content-based system, so that subscribers can set and modify a subscription filter, like type and limit, as well as the stored handler address. Instead of storing index and subscriber table in the structure, these now have to be stored in RAM too, in order to modify the values at run-time. Because a WSN node has only limited resources, especially RAM, the maximum number of events and subscribers is limited. At compile time, the needed stor- age size has to be calculated and reserved, since most operating systems for WSN nodes have no malloc() functionality available (MANTIS has non). A developer should know the number of events which are published by a publisher thread, and subscribers for the events. Subscriber and events are in a relationship to one another. Each subscriber has to know the name or id of the event it wants to subscribe to. So the storage ca- pacity required by the concept is calculated at compile time. A test should show at compile time, if enough ad- ditional space is available to handle the storage of the blackboard. Köpke et al. use one published flag per subscriber in the subscriber flags array. In this concept, we use one publish flag for each event. There can be several distinct sub- scribers for one event, with different subscription filters. The subscriber flags array here is similar to Köpkes ar- chitecture, within the difference that one publish flag followed by n subscriber flags and one block flag are used for one event. The block flag is needed for safeguarding reasons. To calculate the bit position of the flags, we need no additional field in the index table. The offset value used to calculate the handler reference can also be used here for the subscriber flags. If a publisher sends a new value for an event to the blackboard, the published flag for this event is set and in the notification state entered later, only the events with an activated published flag have to be processed. In contrast to Köpke’s concept, this pub- lish/subscribe system is able to handle content-based notifications. On subscription, the subscriber commits the event identifier and the subscription filter. This filter consists of two fields, namely the subscription type and subscription limit. When a new value is published and the subscriber is subscripted for this event, the blackboard has to prove, if the subscription filter is fulfilled or not. On a positive decision, the subscriber gets a notification. As in Köpke’s concept, this could be done by invoking a han- dler. The advantage of this concept over Köpke’s is that it is more flexible. A subscriber is able to unsubscribe, if a subscription is not needed anymore, and a second sub- scriber can later subscribe and can reuse the reserved storage from the first subscriber. In order to reduce the amount of storage, the index table can be skipped if the number of subscribers is fixed, e.g. having fixed the number of subscriber for each event to 6, the offset in the subscriber flags is 8. So for each event, only 1 Byte has to be reserved for the flags per event statically. The problem here is fragmentation. In the worst case, assuming at least one subscriber is available, space for 5 additional subscribers are unused, but the storage for them is still allocated. If more than 6 subscribers are interested in the event, a dummy sub- scriber can be created, which publishes to new event on notification of this dummy subscriber. Additionally sub- scribers can subscribe to this event, instead of the fully subscribed root event. 2.3. Dynamic Data Storage In a static storage, storage reservation is necessary at compile time. Space for events and subscribers is calcu- lated and each gets its own part of storage space. Another concept is to reserve a given size of storage for the noti- fication system at compile time and reserve space for events dynamically at run time. On creation of an event, a data container is created, which holds all relevant data of the event. The published values as well as the subscriber filters are outsourced and only accessible by a pointer. Therefore, the event container holds the pointer addresses to these data. Beside the pointers, information like the number of subscribers and the number of publishable values is also stored in the container. The number values are needed to calculate the last position of either the pub- lished value array or the subscriber arrays for subscriber limits and types. The subscriber flags are stored in the event container. Unlike the static variant, the subscriber flags are not limited and can have different sizes for each event. The number of subscribers can be found in the container, so the size of the subscriber flags in bits is two plus number of subscribers. Each event container has a pointer to the next container, so each container is reach- able through its predecessor. A direct access on a con- tainer could be done by using a index table, which holds all next pointers. Storing pointers to the values instead of the values in Copyright © 2010 SciRes. WSN ![]() B. STELTE615 the container has the advantage that sharing is possible. In a situation where two different events have the same subscribers, the pointers for subscriber limits and types are the same. The individual subscribers of the two events share the subscriber array and so reduce the amount of needed space. A modification of the filters will influence both events at the same time, this means that cycle counts are reduced for modifying the filters. Secondly, not only the last published value can be stored, now several values can been stored externally with the pointer to the first value in the container. Each event container can handle a different number of published values. The containers are linked by a next pointer, so a list of containers arises. This list can represent a priority order, where a container in the front has a higher priority as its successor. The priority order can be changed at run time by swapping the next pointers. At the notification phase, the blackboard starts with highest priority containers. As in the static concept, only event container, whom published flag in the subscriber flags array is set, need further processing. If at least one of the subscriber flags is set as well and the corresponding subscriber filter is true, the blackboard marks the subscriber to be notifiable. After all containers are processed, the notify list with all marked subscribers can be processed. A method like first-come- first-serve should be adequate here, with the subscribers of higher prioritized events first. Reordering should be used for containers which are used often. Reordering can be done at run time, depending on a situation or event. The event container is easily expandable for the developer. Additional values can be stored in the structure by adding new variables in the event container. The main problem with the dynamic storage concept is the needed storage capacity and the needed computational time for modify- cations. Specially on publishing a value for an event, we need a index table to get the current pointer address to the container for the event quickly. The index table is only needed for publishing. Without the table, we would have to search for the correct container by hopping from one container to the next, until the correct container is found. The index table, holding the id of the event at its pointer to the container, has also the problem of being static. Since sensor operating systems like MANTIS OS do not support malloc() functionality, the storage for the index table has to be reserved at compile time. So even when the dynamic storage concept is used, the amount of accepted events is limited at compile time. 2.4. Combination of Static and Dynamic Storage Since neither the static nor the dynamic concept (ex- plained in the sections before) seems to really suit to WSN nodes, a combination of static and dynamical should be discussed. The idea is to reduce used space while keeping flexibility. The static concept limits the subscriber to define better filter constraints for their subscription. A subscriber can only post one filter for each event. It should be possible for the subscriber to define several rules, which have to be valid for notification. In Elvin [4], a special subscription language was used for defining subscription filters. De- fining a special subscription language is expensive re- garding storage and computational time. Another idea is the creation of special subscriber type, used for dummy subscriptions. When the first subscription filter is valid, a sub-event is notified by a dummy subscriber with the second filter rule. The second stage subscription rule is validated after the notification and the real subscriber can be informed if this second subscription filter is also valid. This idea leads to a tree-like subscription filter net. So a nesting of subscriptions covers the same complexity as a subscription language, like the one in Elvin. At the dynamic concept, an index table has to be used for finding the requested event container or the list of container has to be gone through to find the correct con- tainer. In the static variant, no index table is needed, be- cause the number of subscribers are fixed. The idea now is to get a combination of the two concepts, but the ques- tion is how to do this? First, an observation may help. Subscriptions are for an event and the event is well known to the developer. The application developer uses a sub- scriber for an event with a fixed identifier. So the devel- oper knows the total number of subscribers and events in the system. As a result, the developer is able to reserve as much space as necessary for the notification system at compile time. Because the dynamic concept uses storage space wastefully, a more static concept is needed. Figure 1 shows the combination of static and dynamic storage for one event. A management frame is used instead of a container. This frame consists of six parts, which have a total size of 7 Bytes. The first part contains the well known subscriber flags. The number of subscribers is limited in this example to six, so the first management frame part has exactly a size of 8bit. This is profitable, because having a 8 bit CPU, flags can be set and cleared rapidly without being vigilant about byte bounds. The second part of the management frame consists of eight 1bit flags for describing type and status of the event. We will discuss the meaning of this field later in this section. The remaining parts of the management frame are the four pointers to the published data, the subscriber limit, type, and handler. A pointer itself has normally a size of 32 bit, but with the observation in mind that every data or sub- scriber value has a size of 32 bit, only storing the position instead of the real pointer address is enough. In the management frame, each of the positions, which can be stored, has a size of 10 bits. So for all four positions, we need 40bits, and with adding the 16bits from part one and two, we have 56 bits, which are 7 Bytes, in total for a management frame. As in the static variant, an index table Copyright © 2010 SciRes. WSN ![]() B. STELTE Copyright © 2010 SciRes. WSN 616 Figure 1. Effective data storage. is not needed, because each management frame has the same size. So calculating the start position of event x is easy. We have reserved 10 bits for storing the position, in- stead of the pointer. The question is know how to use this position for calculating the real pointer and is the size of 10 bits huge enough? First we will show that 10bits are sufficient by taking into consideration that data is stored on a sensor node. Secondly the pointer calculation with position value as an offset value is shown. With 10 bits representing the position of a value, there are 210 possibilities. So 10 bits are sufficient to number at least 1024 values. Each value has a size of 32 bits and so in total 32 bits × 1024 = 32768 bits or 4096 Bytes are ad- dressable. A sensor node like the Mica2dot has only 4 kByte RAM, the considered 10bits are adequate for addressing 32bit values. With a start address and the 10bits for the position, the pointer is calculateable. The position multi- plied with 32 gives the offset, which has to be added to the start position. The result is the searched position address of the value. When the total size of RAM would be reserved for the notification system, realistically at most 35 events can be created with 35 × 6 = 210 possible subscribers. When all of them store an individual subscription filter and all events store one published value, than 35 × 7 Bytes + 35 × 96 Bytes = 3605 Bytes are used. Not surprisingly, the amount of needed space can be cut, if subscription sharing is used, like in the dynamic variant. Additionally, unlike in the dynamic variant, the subscription blocks for all 6 subscribers can be partly shared. As mentioned, no index table is needed, because of a static size of the management frame. Therefore, the number of possible subscriptions to one event is fixed to a number like six. If there are more than six subscribers for an event, the idea is to create a new event and make one special subscription at the first event, which is always true at examination. The new event is called a sub-event of the first one. There may be at most six sub-events for each event and also each sub-event could have its own sub-events. So the number of sub- scribers for an event is only limited by the available storage space and not by the architecture. The special subscription used here needs a significant value in the subscription type and the position of the sub-event in the subscription limit field. As seen in the dynamic concept, a priority based scheme is possible. The subscribers in the root event have a higher priority than its sub-events. Next to prioritization, it is possible to create a sequence of subscriptions, which represents multiple equations of a subscription. For example, a subscriber who would like to get a no- ![]() B. STELTE617 tification, provided that the published value is larger than a limit x and smaller than a limit y, defines two subscrip- tion filters. The first filter, from the type forwarding and greater with the subscriber limit value of x, only notifies a sub-event if the greater equation is valid. The subscriber handler field of this first subscriber filter holds the address of the sub-event. The second subscriber filter is the filter of a subscriber of the sub-event. This filter is a normal subscription filter with a smaller type of subscription equation and the limit y. If the first equation is valid, the sub-event is activated by a notification. If also the second subscription equation is valid, the real subscriber gets a notification. The positive effect is, that the published value is stored only once. Both management frames have the same position stored for the published value. It is also possible to extend this strategy for n equations, but than reducing the offcuts is more and more important. When sub-events are created, a tree of events is built. In this scenario, it is possible to use the quenching strategy from Elvin. If no subscriber of a sub-event is active, all subscriber flags are cleared, than the subscriber flag for the sub-event should also be cleared in the subscriber flags array of the root event. This has the consequence that the blackboard cuts the sub- event branch of the event tree. Quenching for sub-trees reduces computational time and should be used as often as possible. As mentioned before two bits in the management frame are reserved for the event type. So far there is no sensible necessity for using the event type. A later possible usage may be the decision if one of the bits should be used as a storage flag. This flag than indicates if the blackboard information is stored in RAM or in the ROM part. A set storage flag lets the blackboard use for calculating the correct storage pointers the start address of the RAM part as a cleared flag means the start address of the ROM part has to be taken. If more than one publication should be stored, the difference between the number of the publish and the subscriber type pointer has to be greater than one. Than there is enough space reserved for storing more than one published value. For simplification the front value, which is in the position of the pointer address should always been the latest value. So on each publication all published value has to be pushed 32 bits to the right within their space reservation. Than the first entry is overwritten by the new published value. 2.5. Evaluation In this section, we will compare the memory usage of the three discussed storage concepts. Since a WSN node has only limited amount of available memory, one goal is to use as less as possible memory for storing event and subscriber values plus minimizing the management overhead. On the other hand, the storage concept should be flexible. The flexibility of the dynamic concepts need more memory than the static one, but the question is how big this gap is and how is it justifiable? For a comparison, we need the memory usage of all three concepts. First we will calculate the number of bits the static concept needs for storing one event. With the values of Table 1, defini- tion 1 shows the amount of needed bits for one event with n subscribers and one published value. DEFINITION 1. bitsstatic = 97 bits * #subscribers + 2 bits + 32 bits * #value For the dynamic concept, Table 2 shows the addi- tional needed space the dynamical concept needs com- paring to the static one. This additional amount of mem- ory is statically, so for each event the dynamic concept needs at least 160 bits more memory than the static con- cept. Definition 2 shows the total amount of memory in bits for one event with n subscribers and i published val- ues. DEFINITION 2. bitsdynamic = 97 bits * #subscribers + 162 bits + 32 bits * #values The static-dynamically mixed concept needs 56 bits for the management frame and 32 bits per published value. For each event six subscribers are possible and space is reserved for this six subscribers, which is 6 * 96bits per event. When more than six subscribers wants to subscribe, additional events, so called sub-events are created. Each of them has its own management frame and the additional space for the subscribers. That published values are ref- erenced by the value pointer, which is for all subevents the same. Definition 3 shows the needed space mathematic- cally. DEFINITION 3. bits concept = 32 bits * #values + (56 bits + (6 * 96 bits)) * (ceil(#subscriber/6))) On a node, like on any other computer board, the available memory for the notification system is fixed. In the following figures a capacity of 4 kByte is assumed. As Figure 2 shows, the extreme points, where a huge amount Table 1. Storage for the static event handling. published value 32 bit status flags 2 bit + n bit * subscribers subscriber handlers 32 bit * subscribers subscriber limits 32 bit * subscribers subscriber types 32 bit * subscribers Table 2. Additional Storage for the dynamic event han- dling. pointers 96 bits numbers 16 bit event type 16 bit next pointer 32 bit Copyright © 2010 SciRes. WSN ![]() B. STELTE 618 Figure 2. Number of possible events vs subscribers for 4 kByte. of subscriber or events are capable, are unusable. In this example a range of 3 to 20 events seems to be a good working area. On the one hand a huge amount of sub- scribers but a less number of events are supported and on the other hand a huge amount of events but a less number of subscribers are capable. It is a trade-off between this two factors. A developer has to decide, for which of them he wants to optimize his system. When a subscription on many events should be possible, like up to 20 events in the example of 4 kByte of memory, the question is how many subscribers are supported in average. Assuming a uniform distribution of the subscribers on the events, all events have the same number of subscribers, all events get the same quota of memory allocated. All calculations in this section are for events with six subscribers. In this scenario the static concept dominates its competitor concepts, because its overhead per event is small. The dynamic concept needs only a static additional amount of 160 bits per event, assuming that all stored values, the published value and the subscription values, can be stored compact. This assumption leads to an efficient storage but addi- tional computational time for shifting the values on add- ing and removing new subscribers or events. The pre- sented architecture does not need this additional compu- tational time but pays its dynamically with additional needed memory 3. Real-Time-Enabled Publish/Subscribe A value is published on the blackboard when the publish function is executed within a thread. The function needs as parameters the event id, which is unique, and the new value, which should be published. When the blackboard thread is activated later, the blackboard works off the publishing procedure. First it tests if the event is blocked by another process. If the blocked flag in the subscriber flags array is set, the publisher has to wait for unblocking or skip the publishing process for this event. When the block flag is not set, the blackboard set the block flag and the publish flag. Now no other process can disturb the publishing process for this event. The publish flag is set and so leads to later verification of the subscription. If all subscriber flag are cleared the published flag should also be cleared, because when there is no subscription, no subscriber can get a notification. Also it could be possible to inform the producer about this situation. This process is called quenching and instructs the producer to skip further publishments for the event. When at least one subscription is made for the event, the producer has to be informed once again, now to stop the skipping. In our concept, not the complete management frame has to be modified, only the first byte needs a modifica- tion. The first byte consist of the subscriber flags, which should be notified as described. In order to store the pub- lished value in the right position, the publish block of the management frame is read and the value is stored at the real address. After finalization of the publishing process the block flag in the subscriber flags array is cleared. A consumer thread calls the subscribe function of the blackboard API for creating a subscription for an event. The event id and the subscription filter values are given to the function by parameters. The subscriber gets a unique subscription number, which is the next free number of the all subscriber flags in the event, back as a result of the function call. Which this number a later pausing or un- subscribing can be done. Like in the publishing process, the block flag is tested and set. If no other subscriber flag is set before and quenching is used, the producer has to be informed, that there is at least one subscriber, who is interested in its published value. The first two bytes of the management frame have to be modified. In the first byte, the subscriber flags array, the corre- sponding subscriber flags has to be set. In the second byte, the type field, also the corresponding flag is set, standing for a reservation of the subscription block for the sub- scriber. Since a structure optimization for reducing offcuts is not done so far, the data flags block should be a copy of the subscriber flags. The needed next free subscriber number, is the first position of a subscriber flag, which is cleared and which representing flag in the data block is not set. If no space is available in the management frame for an additional subscriber, a new event is created, called sub-event. One of the subscribers is copied to the new event, meaning coping subscription filter values and set- ting the subscriber and data flags in the new sub-event. In the gap of the old subscriber in the root event, a new subscriber is created with a subscription filter of a special forwarding type. This subscription is always true and on notification processing, the new sub-event gets activated by notification. Because the root event holds the position to the published value, the position can be copied to the position stored in the sub-event. The subscription filter values are subscription type, limit and handler. These values are stored at the position, which stand in the three position blocks of the manage- Copyright © 2010 SciRes. WSN ![]() B. STELTE619 ment frame. The first subscriber takes the first 32bit be- ginning at the given position, the second subscriber the next 32bits and so on. This procedure is done for all three values. An unsubscription has to be divided in a pausing and a real unsubscription request. Pausing means that the subscriber wants to skip notifications for a short time and wants to resume later. Unsubscribing means that the subscriber gives its subscription up and that the reserved memory space can be used be another subscriber. The subscriber executes the unsubscribe routine with the pa- rameter of the event id, the subscriber number and if its willing to pause or not. Like in the other processes, the block flag is tested and set first. If the corresponding subscriber flag is set, the flag will be cleared. If not pausing, but unsubscribing is chosen, also the corresponding data flag is cleared. After all, the block flag is cleared and the unsubscribe process has finished. If a new value is published and a subscrip- tion inequality of at least one subscriber is fulfilled, the subscriber needs a notification. But how to notify the subscriber? Before possible solutions can been discussed, the goals should be clear. A notification method should be 1) effective concerning space and time 2) be implementable (Mantis prototype) 3) fulfill the three publish/subscribe constraints Subscribers can be splitted into two parties. Subscribers, which are interested only in the notification itself, not in the published value, are in the first party. These sub- scribers are namely the alert subscribers. The second party of subscribers need the value for their further proceeding, like sending a message with the published value to an- other node. These subscribers react on a notification like the alert ones, but also need the value at notification. Each of these subscribers could be build as an alert subscriber, which requests the value at notification or the value is passed to the subscriber with the notification. Subscribers who are only interested in getting a noti- fication as an alert have three choices in getting a notify- cation. First, the subscribers could poll for a notification. The blackboard needs a notification queue, in which all subscriber ids are stored which have to be to notified. On a poll request, the blackboard will give a true back as re- sponse, when there is an entry for the subscriber in the queue and false otherwise. After every valid polling request, the found subscriber entry is removed form the queue. The problem with the polling method is, that when its used too often, too much computational time is wasted, having an active consumer thread. So the thread with the waiting and polling sub- scriber disables the operating system to switch to lower electric consumption state. The time the subscriber waits for the notification may be used to let the micro-controller sleep, but with an active polling process this not possible. In a situation, where the producer of the event is not in the same thread of the subscriber, it is possible to reduce the polling to a minimum. On a reactivation of the thread, only one polling is al- lowed, because a second request would always return false. But even in this situation, the polling method in- hibits an efficient power management. The only positive fact is, that the subscriber defines the point in time, when the notification should be processed. A second idea is the usage of a function call. In some operating systems a alert function is available, which starts a function, when a given point in time is reached. For execution of the function, a reference to the function is given to the alert process on creation of the alert. The same could be done here. The function would be executed in the context and time of the blackboard. So the sub- scription thread is definitely not blocked and does not wait or pull for getting a notification. The problem is, that the function may use some variables from the subscribing thread. This is not allowed, better not possible, when the function is executed at the blackboard thread. Only global variables are reachable for the function in order to publish the computed new value. Another idea may be, that the function uses the publish function to make the value known. But then the whole process chain has to be built as nested functions. This complicates the process unnec- essary in context of debugging and implementation in- terested. The second point is that this function call method breaks the multi-thread concept. The process chain would be computed at the blackboard thread. The main scheduler would be useless in this situation. So a new additional, inline scheduler must be implemented in the blackboard. This scheduler schedules all function calls for the black- board. As we can see, the function call method is tricky and so arduously to proper implement. A third idea, how to implement a notification, is the idea of a locked sub- scriber block in the subscribing thread. At the first sight, blocking the subscriber is not wished, concerning the decoupling rules. But here, not the whole subscriber is blocked, only a part of it, the part which handles the things to do when a notification arrives, is locked. Instead of out-sourcing the code in a function, which has to be executed on notification, here the code is still in the thread, but locked with a global available semaphore, which the subscriber has defined. The previous discussed notifica- tion model with function calls can been transformed in this model. The code of the notification functions for the subscribers build subscription blocks in a special sub- scription thread. Each thread is locked by a semaphore, which is unlocked if the blackboard thread calls the noti- fication for the thread. Instead of executing functions at notification, the semaphore is unlocked and the subscrip- tion thread is activated once. The only thing the blackboard has to do, is to unlock the semaphore. In the subscriber block of the thread, it has than to be decided, if the semaphore should be relocked again or not. The positive effect on this method is that first the subscriber decides the point in time of the notification Copyright © 2010 SciRes. WSN ![]() B. STELTE 620 in the thread and secondly thread variables are still available. The problem is, that there could be a problem with the scheduler, when the subscribing thread is not activated contemporary. When the blackboard clears a semaphore for a subscriber, the subscriber could execute the now unlocked code. In a situation, where a producer publishes a new value for this event before the subscriber thread was activated, the blackboard once again tries to notify the subscriber by unlocking the already unlocked semaphore and the subscriber only gets the notification for the last published value. So when a notification guarantee should be given, than the scheduler has to prior the thread with an outstanding notification. The needed modification for the scheduler should be minimal. An additional queue is needed, where the blackboard writes all subscriber ids to notify down. The scheduler works off this list and gives the corresponding subscriber thread the highest priority. In the next step, the subscriber id is re- moved form the list, so that on the next scheduler round, the thread get its old priority back. The problem here, is that the scheduler must know, which subscriber id belongs to which thread id. The blackboard can store this infor- mation at subscription. Each thread knows its id, so this id could be given as a parameter to the blackboard on sub- scription and stored in a extra table. Either the scheduler reads this table to decide which thread to prefer or the blackboard does this and gives the scheduler the thread id instead of the scheduler id. The interference in the scheduler process has effects on the thread order. When many notifications should be worked off, it could be that some threads will become stunted, because all notified threads have a higher priority. Aging is a solution to avoid this scenario. A second problem is the question how in which order the high priority threads should be activated. A normal first-come-first-serve scheduling strategy should do that work in a normal scenario, but in a real- time enabled notification system the whole scheduler must been modified. 4. Concept of a Blackboard for WSN So far, we have shown how to store events and subscrip- tions on the blackboard and how producer and consumer can use the blackboard API. Now we will discuss the blackboard process, which is settled in an own thread, the blackboard thread. The assignment of the blackboard thread is to process all publish and subscribe requests as well as verifying the subscriptions and start the notifica- tion process if necessary. The blackboard thread can join five different states. These states are 1) sleep state 2) modify state 3) prove state 4) notify state 5) optimize state The sleep state is always the first and last state in the blackboard process. First, being in this state, it is proved if at least one producer has published a value. This can be done, by looking in the publisher queue. If this list has at least one entry, the blackboard thread switches to the modify state, else the thread is let sleep and the scheduler can switch to another waiting thread. The publishing queue is needed, because the publish/subscribe paradigm demands a decoupling in time. When a publisher would access the storage management directly, than one part of the blackboard assignment would be done by the pro- ducer. But than the producer would be blocked, while it writes its data to the blackboard storage. To prevent this, the producer only pushes its data to the blackboard, which queues this in the publisher queue. Not surprisingly, the same is done for the subscriber so the queue is extended to also store subscription requests. On activation of the blackboard thread, the queues are worked off by switch- ing to the modify state. In the modify state, each entry in the queue is worked off in a first-come-first-serve manner. This is done because of the fact that a subscriber should only get a notification for an event, which is published after the subscription. For the unsubscribe request its vice versa, if a consumer unsubscribes no further notification should arrive after the unsubscription. If all subscriptions in the queue would have be done before publishing in the blackboard, than the resulting process order may be in- correct. After the processing of each queue entry, the item can be purged from the queue. When the queue is empty and at least one publish entry was processed, than the thread switches to the prove state. Else the blackboard has finished and switches to the sleep state. In the prove state, the blackboard process goes over all management frames, in order to find an activated publish flag in the subscriber flags array of the frame. If one is found, it is proved if one or more subscriptions are ful- filled. For each of them an entry with the subscriber id and the subscription handler address is stored in the notifica- tion queue. Next, the publish flag is cleared and the next management frames are tested. When all frames are worked off and at least one notification has to be done, the blackboard thread switches to the notify state. Else, no notification has to be done and so the sleep state is acti- vated. In the notify state, all notification assignments, which are stored in notification queue, have to be worked off in a first-come-first-serve order. Therefore, all notifications semaphores, which reference is the subscription handler address, are cleared. Following, the value of the thread id, which belongs to the subscriber, is pushed to the sched- uler. As described in the section before, the scheduler de- cides, when a thread is activated, When the queue is processed, the blackboard finishes its process by switch- ing to the sleep state. Copyright © 2010 SciRes. WSN ![]() B. STELTE621 Optional, a optimize state can be insert after the publish state. The assignment of the optimize state is to reduce offcuts in the blackboard storage. This state increases the needed computational time of the blackboard, so it should only be used, if the fixed available memory for the blackboard is nearly reached. 5. Integration of Publish/Subscribe into MANTIS OS The interaction style describes how parties communicate which each other. As Rozanski and Woods describe in Chapter 11 of [6] the interaction style for a blackboard depends on referential and non-temporal coupling. The referential coupling means that the sender has a reference to the receiver’s address. Concerning the blackboard the sender is the publisher which publishes an event. The publisher knows the event identifier, so it has an indirect reference to all subscribers of the event by the event itself. An asynchronous data exchange between sender and receiver is a non-temporal coupling. Exactly this decoup- ling in time is one of the three main conditions explained in Section 2. The point in time when the receiver gets the notification of the publication is not predictable. It could happen at once after the publication or some time later. Therefore, setting a deadline is conceivable in order to isolate the notification point in time. This directly leads to the idea of an real-time enabled publish/subscribe system. The presence of deadlines requires the modification of the operating system scheduler. The scheduling of threads, which contain deadline afflicted subscribers, leads to the question if all deadlines could be met. First and foremost, the used real-time scheduler algorithm determines, if all deadline expections will be fulfilled. For simplifying the choice for the correct scheduler algorithm, we will make two important assumptions in this paper. We will assume that the system is always schedule-able and that the sys- tem is never in an overloaded condition. This assumptions can be made, because the task is to create a real-time enabled publish/subscribe system and not a real-time enabled OS. This makes things different, because in this scenario a central component, the blackboard, decides the point in time when the deadline of a thread should be modified and how the value of the deadline should be modified. 5.1. Overview MANTIS OS MANTIS OS [1] is built in the classical multi-thread design. The application threads are separated from the underlying operating system, which is split into two layers. The upper layer consists of the system API. The threads are using the system API, when a radio communication is started or a sensor is triggered. The system API is based on the lower layer which consists of the kernel, the com- munication (COMM) and the devices (DEV) part. The COMM part handles asynchronous I/O, like radio, serial, etc. and the DEV part all synchronous I/O e.g. reading data from the sensor. The COMM part is interrupt-driven and so no polling is used. For example a received data packet from the antenna triggers a hardware interrupt, which pushes a transfer function for storing the packet into a receive queue. The main part of the base layer is the part of the operating system kernel. Besides the existence of mutex, semaphore and alarm functionality, the sched- uler is the main part of the kernel. The scheduler decides which of the available and ready threads to activate. Threads can call a sleep function to sleep for a defined time. Then the system API gives the scheduler the opportunity to determine a new schedule omitting the sleeping threads. If no thread is ready for activation, a idle thread is activated, which lets the mi- cro-controller sleep for the rest of the time-slice. The number of threads in MANTIS OS is limited to at most 8. This was a design decision with the total available memory in mind. The problem is that each thread gets a reserved memory block of its own. These blocks are re- served statically with the best-fit method. So a dynamical allocation inside the thread is not possible. MANTIS OS is built in the classical multi-thread design. The applica- tion threads are separated from the underlying operating system, which is split into two layers. The upper layer consists of the system API. The threads are using the system API, when a radio communication is started or a sensor is triggered. The system API is based on the lower layer which consists of the kernel, the COMM and the DEV part. The COMM part handles asynchronous I/O, like radio, serial, etc. and the DEV one all synchronous I/O e.g. reading data from the sensor. The COMM part is interrupt driven and so no polling is used. For example a received data packet from the antenna triggers a hardware interrupt, which pushes a transfer function for storing the packet into a receive queue. The main part of the base layer is the part of the oper- ating system kernel. Besides the existence of mutex, semaphore and alarm functionality, the scheduler is the main part of the kernel. The scheduler decides which of the available and ready threads to activate. Threads can call a sleep function to sleep for a defined time. Then the system API gives the scheduler the opportunity to determine a new schedule omitting the sleeping threads. If no thread is ready for ac- tivation, a idle thread is activated, which lets the micro- controller sleep for the rest of the time-slice. 5.2. Scheduler The scheduler is preemptive designed, allowing MANTIS OS to switch active threads even if they have not finished their execution. The scheduler is built as a priority-based Copyright © 2010 SciRes. WSN ![]() B. STELTE 622 Figure 3. Blackboard extension of MANTIS OS. Round-Robin scheduler with five defined priority levels. The time slices are 20 msec long and controlled by a hardwarebased timer interrupt. At the end of a time slice or if a thread calls an interruption command (like mos_thread_sleep() ), the running thread is halted and appended to the end of the ready queue. The dispatcher function of the scheduler grabs the first thread from the ready queue and executes a context switch. The ready queue itself is split into five separated queues. Each pri- ority level has its own queue, so in total we have five queues for the ready queue. The implemented Round- Robin scheduler first looks at the existence of a head element in the highest priority queue, then in the next lower prioritized queues. The queues are build as a chained list with a head and a tail element. The cost for the search of a defined element in the list has a complexity of O(n). Beginning the search at the head of the list, at most all n elements have to be visited once. The round-robin scheduler always takes the first element, the head of the list, which it found in O(1). The extended scheduler needs to purge the ready queue from the thread the EDF sched- uler has chosen for activation. So if the EDF part is active, the dispatcher function has to find the thread in the ready queue and to overwrite the predecessor threads next pointer with the next pointer of the chosen thread in the list. Fortunately, MANTIS OS already has such a function, which is called mos tlist get thread(). Unfortunately, this function has a bug not finding the correct thread nor any thread in the list. The problem here was a incorrectly defined if clause, not correctly testing the thread id against the search id. We have bug-fixed this function and use it in the EDF part of the dispatcher. As seen in the section before, the implemented com- bined scheduler always tries to find a EDF schedule-able thread first and only falls back to the round-robin method if none is found. To find at least one thread with a dead- line, all entries for the threads have to be visited once. The MANTIS OS scheduler uses a thread table for storing all thread relevant information. Here, we have extend the thread table by the deadline variable. To set the deadline for a variable, I have written a new function called set deadline (thread, deadline). This function can be used to assign a given deadline to a certain thread. The scheduler will go through the all thread table entries beginning at the first and memorizes the thread that is in the ready status and has the lowest deadline of all ready threads. This search has a complexity of O(n), with n as the number of all threads. If no thread is found, the round-robin part of the dis- patcher determines a thread to activate. Going through the different priority queues of the ready queue, this has a complexity of O(k) with k as the number of queues. If a thread is found, the EDF part has to remove the thread from the ready queue. In contrast to the round- robin part, the priority of the chosen thread is known, so the search function mos tlist get thread() is used here. This function needs at least one iteration to find the correct thread in the queue and in worst case n iterations, which is the number of elements in the queue. Because only 10 threads are possible in MANTIS OS, the time needed for searching and removing the element of the list is short. My extension of the dispatcher function has the same complexity class of O(n) as the original scheduler of MANTIS OS. As well as the real-time ability, activating threads only when they are needed is also a design goal of the sched- uler. To do so, a new thread state, called blackboard state, was created. A thread in this state cannot be activated by the Round-Robin scheduler, because the thread is not in the needed ready state and so it’s not listed in the ready queue. The EDF scheduler part is able to schedule this kind of thread. It handles the blackboard state thread like a ready thread. So if the thread is in the blackboard state and has a deadline lower than the maximum value for a deadline, it is schedule-able by the EDF scheduler part. The advan- tage over the normal scheduling is that the thread is only activated if it has a deadline. Because only the blackboard thread sets the deadline for a thread with at least one ac- tive and valid subscription, a thread in blackboard state will only be woken up when it is required. The wake-up process is similar to the sleep method. The difference between the sleeping and the blackboard state is that a sleeping thread cannot been awoken when it sleeps and that the sleeping thread sleeps for a defined time. After the sleep time, the thread has to compete for a time slice, processes its commands and sleeps again. A thread in blackboard state is only activated if the correct published value is available and is suspended again after its processing. This new method allows longer micro- processor sleep and suspend times, because the idle thread will be activated more often as when only sleeping thread Copyright © 2010 SciRes. WSN ![]() B. STELTE623 would be used. In order to set the blackboard state for a thread, we have implemented a new function, called mos give up(). This function changes the current thread state to the blackboard state by overwriting the state parameter of the thread entry in the thread table. The Round-Robin scheduler does not know this new state type and so it does not interfere. The blackboard thread uses this blackboard state. If for ex- ample a value is published, the blackboard thread gets a very low deadline and is activated after the another thread publishes a value. When the blackboard thread has finished the processing, it sets the deadline to infinity and the state type back from running to the blackboard value. So the blackboard thread is only active when it is required. No unneeded processing time is wasted, because the thread is not activated when it has nothing useful to do. 5.3. Blackboard API The publish and subscribe process can be done at once by directly executing the corresponding function or by using a buffer which the blackboard processes afterward. By buffering all publish/subscribe commands the sender of these commands has not to hand over process time for the publish or subscribe process. When the blackboard thread is the next activated thread after the buffer is filled, we can guarantee that the all buffer entries are processed directly after the thread switching. The blackboard thread proc- esses all buffer entries the notification process has started. We have implemented a queue which is filled with blackboard commands that the API makes available to the application threads. On filling the buffer or executing the publish command, the deadline of the blackboard thread is modified. The value of the deadline is set to the lowest possible value for the deadline (the number one). This will lead to an activation of the blackboard thread instead of any other one on the next scheduler run. The blackboard is preferred against the other threads. So when a thread executes a buffering command or pushes at least one new publication, the blackboard thread is always executed directly after the publishing thread. Each entry in the buffer consists of several components. The most important one is the identifier, which has the following values for the different blackboard commands. 1) subscribe 2) modify subscription 3) unsubscribe 4) pause subscription 5) publish Other stored components are always the number of the event for that the command is and the current time-stamp. If a subscription command is called, the buffer has also to store the subscription parameters subscriber id, type, value, deadline, and the address of the semaphore of the notification process. The buffered communication be- tween the application threads and the blackboard thread is asynchronous. All commands are buffered first and processed later. The problem is that it could happen that an unsubscription is temporally before a publication. So this unsubscribe command has to be processed before the publish process to avoid side-effects. The time when the command is stored in the buffer is important. All buffered commands have to be processed in the order of their entering in the buffer. So the imple- mentation of filling and removing buffer elements is used in the first-in first-out manner. Besides using the buffered commands subscribe_ re- quest() and publish_request(), the direct commands sub- scribe() and publish()-without using the buffer-are also possible. The difference is the point in time when the command is processed. The direct commands are ex- ecuted at calling and use up processing time of the cur- rent thread. On the other hand, the buffered commands are stored temporary and executed when the blackboard thread is activated. The processing of the calling thread is not inhibited, because the command execution is after the thread was suspended from the scheduler. The second difference can be found at the error handling. Because the buffered commands communicate asynchronously with the blackboard, the blackboard ignores errors. The calling thread does not wait on the command execution, so no value is returned as status information. It is differ- ent for the direct command procedure. Because the thread executes the command and waits on a result af- terward, an error return is possible. 5.4. Blackboard Thread As described before the blackboard thread is only awaken if at least one element is in the blackboard buffer. The blackboard thread will process the buffer in the modify state beginning with the head element of the buffer. Af- terwards the kind of the element is identified by its id number. Each kind of element has its own function that is called for storing the parameters on the blackboard stor- age and the management frames. This first modify state is finished when no element is left over. In the first instance of the second phase it is proven if at least one command processed in the modify state was a publish command. Therefore, a flag is set on occurrence of a publication. In the prove state the test flag can be easily tested on activation. If no value was published before, the black- board is finished and resets its deadline afterward. Be- cause no value was published, no subscriber needs a no- tification. There is no new value for which a subscriber may wait. The next thread will be chosen by the scheduler and this one is not the blackboard thread, because its deadline has been set back to infinity and its thread state has been set to Copyright © 2010 SciRes. WSN ![]() B. STELTE Copyright © 2010 SciRes. WSN 624 dominates the new one. When all active subscriptions are proven for the event, the next event with an enabled pub- lish flag is searched. The blackboard process has finished when all management frames have been visited. the blackboard value. But if at least one publish command was processed in the modify state, there is the possibility that one or more subscription filters are fulfilled and so a notification process has to be launched. The elapsed time of the notification process is O(n) with n events or in worst case 6 * n with n events in total and all with a set publish flag. Normally a blackboard thread should be finished within a time slice. If not and the dispatcher is launched while the thread is active, the blackboard thread is chosen again by the EDF scheduler part and because current running thread and new thread are the same, no context switch is done. So the blackboard thread always finishes its task before another thread is chosen for execution. First the events with possible notifiable subscribers have to be found. Therefore, the search algorithm goes through all management frames and stop if it found one with a set publish flag. This flag is cleared and for all active subscribers of the event it has to be tested if their subscription filter matches to the stored publication. If the test result is positive, the notification of the subscriber is interpolated. In this notify state, the stored subscription data is used to clear the semaphore at the given address and to set a new deadline for the thread with the stored thread id. The deadline is the latest point in time when the noti- fication arrives at the subscriber. For setting the new deadline, the deadline has to be calculated. The formula for computing this point in time is t_deadline = t_ pub- lished + Dt_deadline where Dt_deadline is the value for the deadline given at the subscription and t_published is the point in time when the value was pushed from the publisher thread in the blackboard queue. 6. Validation of the Implementation First, we will show that if a deadline-enabled notification for at least one subscriber is available, the deadline for the subscription thread is set and the thread is activated within the deadline. We assume that all deadline threads are schedule-able concerning their deadlines, since this is our prerequisite as mention before. So the publisher willing to publish a new value starts the publish request() function. Inside this function call, the deadline for the blackboard thread is set to an initial value. This leads to an activation of the blackboard thread after the currently running thread is interrupted, because of the initial deadline value. No other thread could have a lower deadline than the black- board thread. In the implementation, the calculation is started as early as possible or more exactly directly after the positive subscription test. The calculated deadline time is passed to the scheduler by setting the new deadline time for the subscriber thread in the thread table. If this thread has already a deadline, which is lower or equal than the new calculated value, the old will not be overwritten. Then the old deadline is tighter as the new one and so the old value Figure 4. Blackboard thread process. ![]() B. STELTE Copyright © 2010 SciRes. WSN 625 The largest period of time that a thread could be acti- vated is the duration of one time slice, here 20 msec. At the latest of this time period the blackboard thread is running, processes the publish request and starts the noti- fication process. Because the publish/subscribe paradigm forbids to block the publisher, starting the blackboard thread directly as the next thread is the earliest permitted point in time. Beside the activation time of the blackboard thread, this thread has to be nonpreemptive. This is guaranteed by the fact that the blackboard thread keeps its initial deadline value until the blackboard task has fin- ished. If the scheduler tries to switch the threads, the EDF part of the scheduler will find the blackboard thread as the one with the highest priority and will keep running the blackboard thread. So if the blackboard thread has fin- ished its task, every mutex for the subscription notifica- tion has been cleared and all subscription threads have their deadline. After the blackboard task execution the scheduler is ready to activate the deadline enabled threads in their priority or better deadline defined order. Secondly, we will discuss the problem of mutual exclusions. Shared resources are normally saved by using the mutual exclu- sion concept. But by using a real-time scheduler and mutual exclusion, a so called priority inversion can occur. This means that if a low priority thread allocates a re- source by setting a mutex, a later try to allocate a high priority thread is blocked and has to wait until the mutex is cleared. So there is the possibility that the blocked thread misses its deadline, because it has to wait for the lower priority thread to release the mutex. Therefore, it is important to activate a high priority thread early to prevent priority inversion. The first con- dition, the early activation of the highest priority thread, is fulfilled by the EDF scheduler, because the highest pri- ority means that the thread has the lowest deadline of all ready threads. The second condition needs some modify- cation of the mutex processing. For our implementation we have chosen the concept of priority inheritance as described in [5] for preventing the priority inversion problem. Therefore a thread that tries to set a mutex an- other thread with a lower priority has blocked, helps the mutex owner by passing on its lower deadline to the thread. The original deadline is preserved within the mutex structure and reverted when the mutex is released. The needed modifications in the MANTIS source code are only marginal. A blocked thread is in the so called blocked thread state and its deadline is not influenced. So after releasing the mutex the blocked thread gets back in the ready state and is - because of its lower deadline - the first thread that will be activated. Its waiting time abetted its priority class, now it is even more important to sched- ule this thread. The following shows parts of the mutex code. On each mutex set attempt it is proven if the mutex is free or not. If not it is tested if a priority inversion situation has occurred or not. This could only happen if the current thread dead- line is lower than the deadline of the mutex owner thread. Than the original deadline of the owner thread is stored in the mutex structure and afterwards its deadline is over- written with a copy of the current thread’s deadline. Since the current thread is blocked, the thread which has set the mutex is activated afterwards. Only the blackboard thread could have a sooner deadline as the owner thread, all other threads have lower priority. In the code that unlocks the mutex, only one additional line was added for testing on existence of a stored old deadline and reverting it. On every successful mutex unlock, this line is executed before the scheduler function is called. Because MANTIS OS differs between mutex and semaphore, mutex and semaphore code is separated. So also the semaphore code is modified in the same manner as described for the mutex code. 6.1. A Simple Test Case This section discusses the use of the implemented pub- lish/subscribe architecture in MANTIS OS by an intro- ducing example application. This application consists of three autonomous threads with two of them periodically sleeping and one being only activated on notification of the blackboard. The application is spilt into tasks and each task has its own thread. One of the threads takes over the publisher part and the two others are processing the pub- lished data. The publisher process, which is in a sensor application the part which enquires a sensor, publishes a number and sleeps afterwards for 30 milliseconds by executing the mos sleep() function of MANTIS OS. The thread is re- scheduleable after the expiry of the sleeping time. The only task of this thread is to regularly push data to the blackboard, which has to react afterwards. The two threads with the subscribers for the publisher event are split in a thread, which is only activated on notification (subscriber1) and one which is periodically and on notification activated (subscriber2). The second subscriberthread sleeps for 10 msec after each execution period. In each running state of the publisher thread, one value is published before the state is switched to sleeping. The blackboard thread is executed afterwards and modifies the management frame and stores the value. Afterwards, the blackboard tests all subscriptions of the subscribers of the published event. If the subscription rule is valid, the blackboard notifies the thread with the subscriber by setting a deadline and clearing the correct mutex. Be- cause subscriber1 has a shorter deadline defined as sub- scriber 2, we have included debug code so that we could measure the execution times. The runtime diagram (6.1) shows the execution times of the MANTIS OS threads ![]() B. STELTE 626 Figure 5. Test case scenario. for this example. The example implementation was exe- cuted on a Mica2Dot sensor node. The node was con- nected to the host PC via JTAG interface. On the host, the avr-gdm application in combination with the averice JTAG communication software was used. Each round-robin time-slice has 20 milliseconds, but as the diagram (6.1) shows, no thread needs a complete time-slice of its own. The publisher thread is activated every 30 msec as supposed and executes within 1 milli- second. The blackboard thread is launched directly after the sleeping phase of the publisher thread begins. Then subscriber1 is activated before subscriber2, because of its sooner deadline. The diagram also shows long periods of the idle thread, which means that the micro-controller has relatively long sleep periods. Two threads, the blackboard and the subscriber1 thread, are only activated when its necessary. So a long active idle thread is possi- ble, which allows a low overall power consumption. Also, less context switches are the consequence. So be- sides a better response time, the multi-threading over- head is reduced by using the blackboard thread state in- tensely. Blackboard stated threads are executed in a just- in-time manner. In this example, the publisher thread issues new values and than goes to sleep at once. In the next scenario, we have added a simple waiting routine directly after the publication command. So it is possible to simulate a working task, since in a normal application the publish- ing thread needs some time for monitoring the sensors. The problem is that the publish/subscribe system should not block the running task. So it is possible that the current thread is not interrupted until the time slice is over, originate in that the developer has not used a inter- rupt function like the sleep command before the time slice interrupt occurs. If a defined notification deadline is sooner as the remaining time of the time slice, then the deadline is not grantable. In a test series we will show that a defined deadline is met when possible. In the other condition it is not predictable how long a subscriber has to wait on the notification additionally. Figure 6 shows the results of the test series. The results show the time the notification of the subscriber needs with reference to the time the publisher thread processes the waiting task after the publication. The deadline in this example is set to 10 msec for the subscriber. As long as the additional processing time of the publisher is under 10 msec, the deadline is met. All notifications are transferred within10 msec. But in the scenario when the additional processing time is over 10 msec, the values fluctuate. As the results show, the deadline of the notification is fulfilled as long as the publisher thread is interrupted in good time. If the developer does not let the thread interrupt after a public- cation and processed s time-consuming task instead, the deadline is not met. But the results also show that if the total additional processing time is over the time slice value of 20 msec, the time needed to notify the sub- scriber level off at about 11 msec. In this condition, the elapsed time slice is responsible for a thread switch. Be- cause then the blackboard thread has the highest priority, the blackboard processes the publication and notifies the subscriber before the interrupted thread is rescheduled again. This example shows that a developer has to take care, if the deadline is set to a value under 20 msec, and the publisher threads task is not interrupted soon enough after the publication. If the developer chooses for the subscriber (in this example) a deadline above 11 msec, the deadline would be met in the over-load scenario. A deadline of 20 msec and above would be always met. The problem is that the developer not always knows how long the blackboard thread has to wait for the interruption of the publisher thread. Therefore, the developer should execute a dis- patch thread() or mos sleep() directly after the publica- tion. If this is not done, then the ime needed between publication and interruption has to be stimated and added to the deadline value. The test results how that it is im- portant to choose an acceptable value for he deadline. A solution may be to increase the deadline alue by one unit every time the deadline is not met. Further esearch should show if this method is feasible and useful. The Copyright © 2010 SciRes. WSN ![]() B. STELTE Copyright © 2010 SciRes. WSN 627 Figure 6. Run-time diagram of the test case example. Figure 7. Results of the test case measurement. concept is similar to the deadline aging concept, used y several real-time scheduler implementations. We will not urther discuss this problem, because one conceptional assumption s that the thread is interrupted early enough when ubscribers have to be notified. The example shows that the deadline of the subscriber is met f possible. In the condition above 10mesc, the point in time hen the subscriber is notified is not pre- ![]() B. STELTE 628 dictable anymore as expected. 7. Conclusions We have shown in this paper that it is possible to develop and implement a blackboard-based publish/subscribe architecture for sensor nodes which is also able to fulfill real-time requirements. Next to the real-time ability the introduced architecture flexible concerning the amount of subscribers, subscriptions and events but on the other hand memory space is economically used. We have shown this by comparing our concept against a memory sparing but static architecture and against a total flexible but memory wasting dynamic storage concept. Our black- board-based approach shows a good tradeoff between memory usage and flexibility. Also, it is shown that the three publish/subscribe constraints, namley time, space and synchronization decoupling, are redeemed. Therefore, sensor application designer have now the possibility to use our available framework for easily sharing values between different program parts at least for MANTIS OS based applications. The development of crosslayer con- ceptions benefits from our architecture since the central storing of the published values is managed through our presented blackboard. All publishing and notifying pro- cesses are hidden for the application developer. The needed operating system modifications especially of the scheduler was shown exemplary for the MANTIS OS. The postulated real-time attribute of the publish/subscribe architecture made it necessary to convert the existing scheduler implementation towards an EDF scheduler. Not only it was shown that it is possible to make a sensor operating system real-time enabled but also the shown architecture benefits from the real-time ability. Subscribe are able to define deadlines concerning the notification which enables us to keep track of the system even in an overload situation where deadlines can be fulfilled any- more. 8. References [1] P. Eugster, P. Felber, R. Guerraoui and A. Kermarrec, The Many Faces of Publish/Subscribe, 2003. [2] H. Karl and A. Willig, “Protocols and Architectures for Wireless Sensor Networks,” John Wiley & Sons, Hobo- ken, 2005. [3] A. Köpke, V. Handziski, J.-H. Hauer and H. Karl, “Structuring the Information Flow in Component-Based Protocol Implementations for Wireless Sensor Nodes,” Proceedings of Work-in-Progress Session of the 1st European Workshop on Wireless Sensor Networks (EWSN), Technical Report TKN-04-001 of Technical University Berlin, Telecommunication Networks Group, Berlin, Jan- uary 2004, pp. 41-45. [4] B. Segall and D. Arnold, “Elvin has Left the Building: A Publish/Subscribe Notification Service with Quenching,” 1997. [5] M. Hohmuth and H. Härtig, “Pragmatic Nonblocking Synchronization for Real-Time Systems,” Appears in the Proceedings of the 2001 USENIX Annual Technical Conference, Boston, 2001, pp. 217-230. [6] S. Bhatti, J. Carlson, H. Dai, J. Deng, J. Rose, A. Sheth, B. Shucker, C. Gruenwald, A. Torgerson and R. Han, “ANTIS OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms,” Mobile Networks & Applications, Vol. 10, No. 4, 2005, pp. 63-79. [7] N. Rozanski and E. Woods, “Software Systems Archi- tecture: Working With Stakeholders Using View-Points and Perspectives,” Addison-Wesley Professional, Reading, 2005. Copyright © 2010 SciRes. WSN |