Soumyabrata Saha

Rituparna Chaki
email: rituchaki@gmail.com

Weighted Energy Efficient Cluster Based Routing for Wireless Sensor Networks

Keywords: Wireless Sensor Networks, Weighted, Energy, Cluster, Routing;

Wireless sensor network comprises of numerous tiny sensor nodes to form an ad hoc distributed sensing and data propagation network to collect the context information on the physical environment. Wireless sensor networks are used for remotely monitoring tasks and effective for data gathering in a variety of environments. Minimizing energy dissipation and maximizing network lifetime are one of the central concerns to design applications and protocols for wireless sensor networks. Cluster based architectures are one of the most practical solutions in order to cope with the requirements of large scale of sensor networks. Clustering results in a reduced number of messages that propagate through the network in order to accomplish a sensing task. In this paper, we have presented a brief review of the state of the art scenario of various routing protocols and propose a weighted energy efficient cluster based routing for wireless sensor networks. Conducted simulation experiments on different scenarios shown its ability to obtain effective & efficient communications among different clusters and achieves scalability in large scale of wireless sensor networks.

Introduction

Wireless sensor networks are formed by densely and usually randomly deployed large number of sensor nodes either inside or very close to the phenomenon that is being monitored. The potential applications of sensor networks are highly varied, such as natural phenomena, environmental changes, controlling security, estimating traffic flows, monitoring military application, and tracking friendly forces in the battlefields. Wireless sensor networks consist of sinks and sensors. Sinks play a role of collecting data which is transmitted by sensors. Sensor nodes sense the desirable physical phenomenon and locally do the data aggregation to avoid communication of redundant data. Using routing protocol sensor nodes determine the path for sending data to sink. A sensor node is comprised of four basic components: sensing unit, processing unit, radio unit and power unit. The sensing unit is used to measures a certain physical condition. Processing unit is responsible for collecting and processing signals. The radio unit transfers signals from the sensor to the user through the gateway. All previous units are supported by the power unit to supply the required energy in order to perform the mentioned tasks.

Clustering in wireless sensor networks provide scalability and robustness for the network. It allows spatial reuse of the bandwidth, simpler routing decisions, and results in decreased energy dissipation of the whole system by minimizing the number of nodes that take part in long distance communication. A cluster is a group of linked nodes working together closely for same purposes and belongs to same topological structure. A cluster head is responsible of resource allocation to all nodes belonging to its cluster and directly associated to its neighbor clusters for performing various task of intra and inter cluster communication. Sensor network used to be designed as clustering structure to minimize transmission costs and energy usage to prolong the network lifetime.

In this paper we propose a weighted energy efficient cluster based routing for wireless sensor networks. This proposed routing scheme comprises of five different steps. At first cluster head selection mechanism has been executed. The main motive of dynamic cluster head rotation mechanism is to evenly distribute the energy load among all the sensor nodes so that there are no overly utilized sensor nodes that will run out of energy before the others. Cost calculation technique has been introduced in second stage. Depends upon the dynamic cluster head selection and cost estimation technique, cluster formation mechanism has been presented at third step. Communication procedure has been described at step four. In step five route maintenance mechanisms take an important role to maintain the routes to deliver the messages from sender to receiver.

The rest of the paper is organized as follows. A comprehensive survey of related works of different routing techniques in Wireless Sensor Networks is presented in Section 2. In Section 3, we have design and describe a new routing algorithm, which incurs the transitions among these five different phases and improves energy efficiency to prolong the whole network lifetime. Energy Estimation mechanism is described in section 4. Intensive result analysis is presented in section 5. Finally, we conclude our paper with final remarks in Section 6.

Related Works

In recent years, cluster based architectures are one of the most suitable solutions to cope with the requirements of large scale wireless sensor networks. The clustering protocols have been extensively studied in this literature, which mainly differ in the selection of cluster heads, reformation strategies, hopping limits and routing scheme. In this section we take a brief look at some of the common clustering algorithms applicable for wireless sensor networks.

In HCBQRP [START_REF] Saha | HCBQRP: Hierarchical Cluster Based Query-Driven Routing Protocol for Wireless Sensor Networks[END_REF] the main objective was to design a cluster based routing algorithm for sensor networks to find route from source to destination. HCBQRP [START_REF] Saha | HCBQRP: Hierarchical Cluster Based Query-Driven Routing Protocol for Wireless Sensor Networks[END_REF] was designed based on the query-driven approach and provides the real time communication between sensor nodes.

Maximum Degree and Negotiation Strategy Based Clustering Algorithm for wireless sensor networks [START_REF] Wang | A Maximum Degree and Negotiation Strategy Based Clustering Algorithm for Wireless Sensor Networks[END_REF] was proposed by Qiang Wang et.al. MXAD-N [START_REF] Wang | A Maximum Degree and Negotiation Strategy Based Clustering Algorithm for Wireless Sensor Networks[END_REF] is divided into two phases; one is communication and computation of node degree and other is cluster head election and cluster formation. MAXD-N [START_REF] Wang | A Maximum Degree and Negotiation Strategy Based Clustering Algorithm for Wireless Sensor Networks[END_REF] selects candidate based maximum degree and determines cluster head according to the negotiation strategy.

Babar Nazir et.al. proposed Mobile Sink Based Routing Protocol [START_REF] Nazir | Mobile Sink based Routing Protocol for Prolonging Network Lifetime in Clustered Wireless Sensor Network[END_REF] for prolonging network lifetime in clustered wireless sensor network. In MSRP [START_REF] Nazir | Mobile Sink based Routing Protocol for Prolonging Network Lifetime in Clustered Wireless Sensor Network[END_REF] mobile sink moves within cluster area to collect sensed data from cluster heads and maintains information about the residual energy of the cluster head.

In [START_REF] Ying | A Novel Chain-Cluster Based Routing Protocol for Mobile Wireless Sensor Networks[END_REF] Tian Ying et.al. presented Energy Efficient Chain Cluster Routing protocol for wireless sensor networks. ECRM [START_REF] Ying | A Novel Chain-Cluster Based Routing Protocol for Mobile Wireless Sensor Networks[END_REF] protocol divided into backbone setup phase, cluster formation phase and steady communication phase. ECRM [START_REF] Ying | A Novel Chain-Cluster Based Routing Protocol for Mobile Wireless Sensor Networks[END_REF] includes efficient cluster head selection mechanism to prolong the network lifetime and improve the energy efficiency.

Asif U. Khattak et.al. proposed a Two Tier Cluster Based Routing Protocol [START_REF] Asif | Two-Tier Cluster Based Routing Protocol For Wireless Sensor Networks[END_REF] for wireless sensor networks. TTCRP [START_REF] Asif | Two-Tier Cluster Based Routing Protocol For Wireless Sensor Networks[END_REF] configures the nodes in the form of clusters at two levels. TTCRP [START_REF] Asif | Two-Tier Cluster Based Routing Protocol For Wireless Sensor Networks[END_REF] introduced a power control algorithm to allow the isolated sensor nodes as well as cluster heads to dynamically change their transmission power and provides network robustness.

LU Li fang et.al proposed Weight Based Clustering Routing Protocol for wireless sensor networks [START_REF] Lu | Weight-based Clustering Routing Protocol for Wireless Sensor Networks[END_REF]. In WCR [START_REF] Lu | Weight-based Clustering Routing Protocol for Wireless Sensor Networks[END_REF] cluster head selection algorithm is designed for periodically select cluster heads based on the node position and residual energy. WCR [START_REF] Lu | Weight-based Clustering Routing Protocol for Wireless Sensor Networks[END_REF] is used to minimize the energy dissipation of intra cluster and inter cluster data transmission.

In [START_REF] Samer | Cluster Based Routing Protocol for Mobile Nodes in Wireless Sensor Network[END_REF] Awwad et.al. presented adaptive time division multiple access scheduling and round free cluster head protocol called Cluster Based Routing Protocol for Mobile nodes in Wireless Sensor Network [START_REF] Samer | Cluster Based Routing Protocol for Mobile Nodes in Wireless Sensor Network[END_REF]. CBR Mobile-WSN [START_REF] Samer | Cluster Based Routing Protocol for Mobile Nodes in Wireless Sensor Network[END_REF] is energy aware scheme and used to handle packet loss and reduces the energy consumption.

An Energy Level Based Routing Algorithm of Multi sink Sensor Networks [START_REF] Wu | Energy level based Routing Algorithm of Multi sink Sensor Networks[END_REF] was proposed by Zhongbo et.al. In ECR [START_REF] Wu | Energy level based Routing Algorithm of Multi sink Sensor Networks[END_REF] two different hierarchy structure of the network topology are presented. The operation of ECR [START_REF] Wu | Energy level based Routing Algorithm of Multi sink Sensor Networks[END_REF] can be divided into three steps, cluster-formation phase, cluster head selection phase and steady state phase. Lu Cheng et.al. proposed an Energy Efficient Weight Clustering Algorithm [START_REF] Cheng | An Energy Efficient Weight-clustering Algorithm in Wireless Sensor Networks[END_REF] to reduce energy consumption by perfecting cluster formation procedure. In EWC [START_REF] Cheng | An Energy Efficient Weight-clustering Algorithm in Wireless Sensor Networks[END_REF] residual cluster energy, location and node degree and coefficients are takes an important role in cluster head selection stage and nodes' having minimal combined weight becomes cluster head.

In [START_REF] Boukerche | An Energy Aware and Fault Tolerant Inter cluster Communication based Protocol for Wireless Sensor Networks[END_REF] A. Martirosyan et al. presented an Energy Efficient Inter Cluster Communication based routing protocol for WSNs. ICE [START_REF] Boukerche | An Energy Aware and Fault Tolerant Inter cluster Communication based Protocol for Wireless Sensor Networks[END_REF] uses acknowledgement based approach to faulty paths discovery and provides QoS by finding a path with the least cost for high priority event notification messages.

An Adaptive Decentralized Re-clustering Protocol for wireless sensor networks [START_REF] Yu | Adaptive Decentralized Re-Clustering for Wireless Sensor Networks[END_REF] was proposed by Sethares et.al. ADRP [START_REF] Yu | Adaptive Decentralized Re-Clustering for Wireless Sensor Networks[END_REF] incurs high overhead in forming clusters due to the information exchanged between the nodes and the sink Boukercheet. al. proposed Clustering PEQ [START_REF] Boukerche | Fault-tolerant wireless sensor network routing protocols for the supervision of context-aware physical environments[END_REF], configures the dissemination tree using the PEQ's [START_REF] Boukerche | Fault-tolerant wireless sensor network routing protocols for the supervision of context-aware physical environments[END_REF] mechanism and an additional field contains the percentage of nodes that can become cluster head. CPEQ [START_REF] Boukerche | Fault-tolerant wireless sensor network routing protocols for the supervision of context-aware physical environments[END_REF] employs an energy aware cluster head selection mechanism in which the sensor nodes with more residual energy are selected as cluster head and increases the network lifetime.

Kyung Tae Kim et.al. presented an Energy Driven Adaptive Clustering Hierarchy for WSNs [START_REF] Tae | Energy Driven Adaptive Clustering Hierarchy for wireless sensor networks[END_REF] to increase the lifetime of sensor networks. EDACH [START_REF] Tae | Energy Driven Adaptive Clustering Hierarchy for wireless sensor networks[END_REF] protocol is based on partitioning of the network according to the relative distance to the base station for assigning different probability of cluster head.

In [START_REF] Kim | PEACH: Proxy-Enable Adaptive Clustering Hierarchy for Wireless Sensor Networks[END_REF] Proxy Enabled Adaptive Clustering Hierarchy proposed by Kim et.al. A proxy node assumes as cluster head in place of weak cluster head during one round of communication. In PEACH [START_REF] Kim | PEACH: Proxy-Enable Adaptive Clustering Hierarchy for Wireless Sensor Networks[END_REF], the clustering scheme avoids long range communication, data fusion and saves energy by compressing the data and rotation of cluster head allows to prolong the lifetime of every node.

An Energy Efficient Unequal Clustering [START_REF] Yong Youn | An Energy Efficient Unequal Clustering Mechanism for Wireless Sensor Networks[END_REF] routing protocol was proposed by Hee Yong Youn et.al. EEUC [START_REF] Yong Youn | An Energy Efficient Unequal Clustering Mechanism for Wireless Sensor Networks[END_REF] is a distributed competitive algorithm, where cluster heads are elected by locally and clusters are closer to the base station are expected to have smaller cluster sizes.

In [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Micro sensor Networks[END_REF], according to free space model, the propagation loss is modeled as inversely proportional to d i (where i=2, if d <d 0 ). In the multi-path fading channel model [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Micro sensor Networks[END_REF], the propagation loss is modeled as inversely proportional to d i (where i=4, if d ≥ d 0 ). At the time of transmitting message, the amount of energy dissipated by sensor node has been defined as;

, * ε * * To receive this p-bit message the energy dissipated; * Where p is the size of message, d is the distance between source and destination node, EP elec is the circuit energy cost for transmitting or receiving purposes, ε fs is the amplifier parameter.

In [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[END_REF], the first order radio model is used, which consists of three main models: the transmitter, the power amplifier, and the receiver. The amount of energy consumed by each sensor node while transmitting message, is defined as , * * * , where EP amp is the amplifier coefficient. Heinzelman et.al. proposed Low Energy Adaptive Clustering Hierarchy [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[END_REF] algorithm for sensor networks. Two layers architecture was introduced in LEACH [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[END_REF]. One used for communication within the clusters and the other was between the cluster heads and sink. Due to the random selection, there exists the probability of unbalanced cluster head selection and selected cluster head may be present in one part of the network, making other portion of the network unreachable.

Through the extensive literature review it is observed that the selection of cluster heads can greatly affect the performance of the whole network and well selected cluster heads not only decrease the energy consumption but also prolong the network lifetime. Energy efficiency is unanimously considered as core design issue and in order to improve the deficiencies of aforementioned schemes, the challenge is to develop a routing protocol that can meet these conflicting requirements while minimizing compromise. In the next section we are going to propose a new weighted energy efficient cluster based routing protocol for wireless sensor networks.

Proposed New Routing Protocol

The previous section leads to the observation of different cluster based routing protocol for wireless sensor networks. Clustering involves in the cluster formation techniques where low energy nodes are assigned the task of sensing. The main aim of cluster based routing algorithm is to efficiently maintain the energy consumption of sensor nodes by involving them in multi hop communication.

The assumptions made for this protocol are as follows: all sensor nodes in the network are immobile, homogeneous and are equipped with power control capabilities; sensor nodes are generally energy constrained and they are capable to operate in an active mode or a low power sleeping mode and have enough processing power to support the different protocols and data processing tasks; each sensor node has a unique identifier and uniformly deployed over the target area to continuously monitor the environment; every sensor node can directly communicate with its immediate neighbor; the transmission range of each node is same on one condition.

Wireless sensor network is usually data centric. Collected data are periodically transmitted from the sensor node to the remote sink node. It is assumed that the sensed information is highly correlated, thus the cluster head can always aggregate the data gathered from its members into a single length fixed packet. The correlation degree of sensed data from different clusters is relatively low.

In the proposed weighted cluster based routing algorithm protocol, WSN perceived as a network partitioned into different clusters and we present a new robust approach of routing. The proposed weighted cluster based routing scheme is divided in some subsections. In section 3.1 cluster head selection procedures has been presented. Section 3.2 is used for cost calculation technique. In section 3.3 we have described cluster formation mechanism. Section 3.4 presented communication procedure. Route maintenance technique has been presented in section 3.5.

Cluster Head Selection Procedure

In our proposed scheme we introduce a weight based cluster head selection procedure. The main objective of choosing cluster head that guarantees both the intra-cluster and inter-cluster data transmission with energy efficient manner. Many energy consuming activity have to perform by the cluster heads, such as, data collections from member nodes and forwarding processed data to other neighbors or to the sink node. To select the cluster head, we have considered some parameters like; number of neighbor nodes, distance between cluster heads and sink node, degree difference of node; residual energy of sensor node is another important parameter for cluster head selection process. Every sensor node takes part in cluster head selection procedure. A node is selected as a cluster head and its energy level is periodically monitored. Once the energy level goes below the threshold value, it is released from its' special responsibilities.

We assume that N number of sensor nodes are scattered randomly over the area of interest and left unattended to continuously sense and report events. We denote the sensor by s i and the corresponding sensor node set S= {s 1 , s 2 , ….., s N }, where |S|=N, where N is the total number of sensor nodes in the network. Definition 1: At time instance T n , to send a p-bit message from transmitter to receiver at the distance d i and to receive the p-bit message at same distance d i , the total energy dissipated from node s i is E req * ε * * * (i)

And the remaining energy for node s i is E r

(ii)

After calculating total dissipated energy and remaining energy of node s i for time instance T n , store all these different estimated energy in the ND_ENGY_TBL {S i, E init , E req , E r , T n } table.

Algorithm 1: Algorithm for Cluster Head Selection

Step1: Find the neighbors of each node s

i ŃģŃ ∑ ś € Ń, ś , ś (iii)
Step2: Compute the distance d for each node s i as: , Step3: Compute the degree difference for every node s i ∆ ∑ ś € Ń, ŃģŃ έ (iv)

Step4: Read initial energy E init and residual energy E r of node s i for each time instance T n from ND_ENGY_TBL and update this energy table.

Step5: Calculate the total weight of each node s i as:

* ŃģŃ * * ∆ * * (v)
Step6: Store all value of in the w s [] and select minimum value of as Ch_Id i Step7: END. By using the above technique, cluster head selection has been executed.

Cost Calculation

In this section we propose a method of calculating combined cost between various sensor nodes. After a brief survey of network environment, we are going to define some network parameters. These parameters reflect the cost of hopping to its neighbors, i.e., the cost of a link leading from the node to its neighbors. The parameters are described below: tp i

The throughput of sensor network. This can be estimated by counting total received and send packet by node i in a time interval. bw i The available bandwidth of NIC of node i. sb i Indicates the saturation of sending buffer at node i. If the length of buffer queue reaches 85% of its total size then sb i set to "1"; otherwise sb i set to "0". rb i Indicates the saturation of receiving buffer at node i. If the length of buffer queue reaches 85% of its total size then rb i set to "1"; otherwise rb i set to "0". By using the above parameters, we can estimate communication cost between two nodes as follows:

* (vi)
The total cost can be calculated using this following equation:

, (vii)

Cluster Formation Mechanism

After cluster head selection process is completed, each cluster head broadcast a CM_FRM_MSG {Ch_Id, Msg_Id, Ch_Wg, TTL} message to its neighbor nodes.

If a node receives this type of message from more than one cluster head, then it chooses to join the membership of the cluster head causing minimum cost.

Accordingly, the node sends a reply CM_RPLY_MSG {Ch_Id, Cm_Id, Ch_Wg, Msg_Id, Cost i,j , TTL} message to the corresponding cluster head with minimum total cost.

If any other cluster head receives this CM_FRM_MSG message from the other cluster head, then it will truncate the message and don't send any reply or acknowledgement to the sender cluster head. If any cluster member of other cluster again receives this message, then it will follow the same procedure. The total process is described below.

Algorithm 2: Algorithm for Cluster Formation

Step 1:

Ch_id i broadcast a CM_FRM_MSG message for cluster formation. For each node in the network:

Step 2:

If the node is already another cluster head or member of another cluster Then it discards the previous message.

Else

Step I: Calculates total cost between it and Ch_id i

Step II: If total cost <Th cost Then it sends a reply CM_RPLY_MSG message to Ch_id i and added to Ch_id i _Mem [ ]. Else Then it discards the previous message.

Step 3: END. By using the above procedure any non-member nodes can join to the cluster head.

Communication Procedure

In this section we have discussed the communication procedure between sensor nodes. Every cluster head maintains the NGH_CLSRHD_TBL {Ch_Id, Ch_Wg, Ch_Comm_Cost, TTL} table and also maintains their cluster members' information in CM_INF_TBL {Cm_Id, Msg_Id, Cm_Wg, Cost comm } table.

When any sensor node requires some information, it initiates communication. At first it communicates with its corresponding cluster head and cluster head searches in its CM_INF_TBL table. If required information is not available then it searches in NGH_CLSRHD_TBL table. The cluster head with lowest communication cost is selected as next hop. The algorithm is described below:

Algorithm 3: Algorithm for Communication Procedure

Step 1: Node N send a request message to corresponding Ch i .

Step 2: Ch i searches in its CM_INF_TBL.

Step 3: If required information is available

Step I: Then it appends corresponding node's Cm_Id in RT_INFO table.

Step II:

That node sends message to sink and updates its energy level.

Step III: Communication end.

Else

Step I: Searches in NGH_CLSRHD_TBL

Step II: The Ch i with lowest communication cost selected as next hop.

Step III: Go to step 2.

Step 4: END.

After successful execution of the above algorithm we find the node with required information. This node becomes source node and sends a message including the required information through selected path from RT_INFO {Snd_Nd_Id, Nxt_Hp, Dst_Id} table.

Route Maintenance Techniques

If in a particular route, a sensor node is damaged for a certain time period or link is broken, the route will be damaged. To handle this kind of situation we have incorporated route maintenance mechanism to overcome this problem.

After receiving any information from any sensor node, the receiving node has send ACK_MSG {Snd_Nd_Id, Recvr_Nd_Id, Msg_Id, Ack_Id, Tm_Stmp} to the sender node within a certain time period. These ACK_MSG message based repair mechanisms consist of two parts. One is failure detection and other is selection of alternative node.

Depends on the reception time of ACK_MSG sensor nodes can detect if its neighbor nodes are functioning properly or not. If ACK_MSG not received within a specified time, the sensor node initiates the communication procedure to find out the alternative route.

By using the above discussed algorithm any sensor node can communicate with any another nodes through the cluster head within that network.

Algorithm 4: Algorithm for Route Maintenance

Step1: If ACK_MSG is not received within specified time interval Then execute communication procedure for finding alternative route Else terminate the process. Step2: END. The total consumed energy of the sensor network is depends up on the construction of the cluster, if the clusters are not constructed in an optimal way, the total consumed energy of the sensor network per round is increase.

Result Analysis

The simulation model consists of a network model that has a number of wireless nodes, which represents the entire network to be simulated. The network simulator, NS-2 is used to evaluate the performance of the proposed protocol WECRP and present the following metrics for comparing the performance of WECRP with the AODV.

Table 2. Simulation Environment Parameters.

End2End delay is the average difference between the time the first data bit is originated by an application and the time this data bit is received at this destination. Throughput is defined as the total number of message sent or received per time unit. In this experiment, throughput is measured in terms of bits delivered per time unit. End2End of the data packet is one of the performances metric in our proposed scheme. The results for this metric are shown in fig 1 .   Fig1: Throughput of Sending Bits vs. End2End Delay. From this graph we have observed that in all situations the delay of WECRP is lesser than AODV. Though our proposed protocol induces a lower routing load than AODV, as a result data transmissions are less delayed. Thus our approach with lower End2End delay offers better QoS.

Fig2: Energy vs. Simulation Time.

In fig 2, we have depicted a relation between energy vs. simulation time. It has been observed that when more number of packet or data bit is transferred, corresponding energy are less dissipated compared to AODV.

Conclusions

In this paper we have summarized the generic characteristics of some well-known cluster based routing protocols for WSNs and present a new routing scheme, weighted energy efficient cluster based routing for Wireless Sensor Networks to achieve realtime communication and high energy efficiency. As the cluster head of each cluster acts as a local coordinator for its cluster, performing inter-cluster routing, data forwarding and has to undertake heavier tasks so that it might be the key point of the network. In our proposed routing scheme only cluster head can take part to share information with their neighboring cluster heads. In WECRP we have considered weight factor of every sensor nodes to select the cluster head. According to WECRP nodes having least weight factor will select as a cluster head. Using cost estimation technique each cluster head selects its neighbor cluster members. Within the same cluster or different clusters, communication procedure has been carried out and route maintenance takes an important role in this routing algorithm.

The routing of messages using the proposed WECRP is achieved in an efficiency manner as observed in the performance graph. The parameters used for performance analysis are energy efficiency, transmission delay and throughput. A comparative analysis of the proposed WECRP against AODV has been carried out. It has been observed that the proposed method shows better performance in each cases and achieved energy efficiency, scalability, information sharing and route maintenance mechanism.

Table 1 : Data Dictionary

 1 Eqn (x) represents average energy consumption per cluster member, assuming there are n numbers of cluster members are present within the cluster. The energy consumed by a cluster head is obtained by Eqn (xi). E ch is the energy consumption as the cluster head transmits the aggregated data to the sink node. Eqn (xii) represents average energy consumption per cluster head, assuming there are c number of clusters are present in the network. Since E ach change over time, the threshold is calculated in every data collection and transmission phase.

	Parameter	Details
	Ch_Id	Cluster head id
	Ch_Wg	Weight of cluster head
	Th cost	Threshold cost
	TTL	Time to leave
	E dg Recvr_Nd_Id	Data aggregation cost Receiver node id
	t r Nxt_Hp	Transmission range Next hop
	Cm_Id	Cluster member id
	Msg_Id	Message id
	Dst_Id	Destination node id
	Snd_Nd_Id	Sender node id
	Ack_Id	Acknowledgement id

sec] Throughput of Sending Bits Throughput of Sending Bits vs. End2End Delay WECRP AODV

	Channel Propagation Antenna Phy Mac Number of nodes WSNs field Initial energy End2End Delay [Parameter Data package size	Value Wireless Channel Two Ray Ground Omni Antenna Wireless Phy 802_11 10 (0,0)∼(500,500)m 0.5 J 2100 bits
	5	6	7	8	9


Um -E-Ghazia

Muhammad Awais Shibli

Rahat Masood

Muhammad Bilal
email: m.bilal@seecs.edu.pk

USAGE CONTROL MODEL SPECIFICATION IN XACML POLICY LANGUAGE XACML Policy Engine of UCON

Keywords: Access Control, Authorization, Obligation, Condition, Policy, Attribute

Usage control model (UCON) is one of the emerging and comprehensive attribute based access control model that has the ability of monitoring the continuous updates in a system making it better than the other models of access control. UCON is suitable for the distributed environment of grid and cloud computing platforms however the proper formulation of this model does not exist in literature in any policy specification standard. It is for this reason that UCON is not widely adopted as an access control model by industry, though research community is now paying attention to make standard policy specification for this model. In this paper we are suggesting the interpretation of UCON model in extensible access control markup language (XACML) which is an OASIS standard of access control policies. We also highlight UCON model features by explaining its core processes and characteristics with respect to the case study of financial application.

Introduction

Access control models play vital role in protecting digital resources in a way to control and mediate access from unauthorized users. These models assure the security requirements of different applications improving their protection from unauthorized access. They secure digital information and resources until the permission is granted to user and are suitable for closed domain comprising static entities. Continuous evolution of computing platforms demands advanced security procedures and mechanisms to handle the consequences of unauthorized access. Usage control model (UCON) has been proposed by Park and Sandhu that caters heterogeneous and dynamic environment conditions [START_REF] Park | Towards Usage Control Models: Beyond Traditional Access Control[END_REF]. It is an attribute based access control that judges three factors: authorization, obligations and conditions for access decision. Two distinctive characteristics are attribute mutability (updates) and access decision continuity which augments UCON model than other traditional access control models. In UCON model usage session is maintained that is categorized into three parts: pre access, ongoing access and post access phases. When the subject S is accessing resource R, UCON decision factors i-e. attributes, obligations and conditions are evaluated before granting access which is called pre access phase. Evaluation is also performed during the time when R is in use by S called as ongoing access phase.

In some cases, it is required to evaluate attributes and obligations after the completion of usage session which is known as post access phase. Decision is continuously evaluated during these three phases to monitor the changes in attribute values. In addition to it, UCON model is comprehensive enough to cover the traditional access control models. So it can be used to provide the better protection of system resources in a collaborative and dynamic environment. Despite of all the excellent features, UCON is not widely adopted as an access control model to restrict the unauthorized access.

The major reason for this is that the model features are not been translated in any of the standard policy language to offer the proper formulization of model.. XACML [START_REF]A Brief Introduction to XACML[END_REF] being a generic policy language of OASIS standard is suitable to represent the aforementioned features of UCON model. It describes the platform independent access control request/ response mechanism and policy specification. Its interoperability feature makes it widely used for various platforms and environments. XACML offers the extension points by introducing new data types, identifiers, elements and functions to offer a generic policy structure. Since UCON can facilitate the diverse range of applications like digital rights management (DRM), health care systems and social networking, it is highly encouraged to provide the formal specification of model in generic policy language like XACML. There is a need to define the separate profile of UCON in XACML that will enable organizations to adopt this flexible model. Also to guarantee the accurate access decision in different deployment scenarios, it is mandatory to propose the required alterations and additions in generic policy language of XACML which is not developed so far. We wish to propose the implementation of UCON model in XACML by incorporating additional elements and specify the information flow of different UCON processes in this paper. Organization of paper is as follows: Section 2 presents the detailed UCON model and its core features, Section 3 includes the profile of UCON model in XACML, use of this profile is explained in Section 4 by taking the scenario of posting vouchers service in financial applications and Section 5 concludes the paper and present future directions.

Usage Control Model

UCON being an attribute based access control model accommodates the security requirements by the addition of more than one decision factors which makes it more reliable and flexible [START_REF] Lazouski | Usage control in computer security: A survey[END_REF]. This model primarily restricts the usage of digital objects and provides the efficient mechanism to include the traditional access control models. Previous access control models only encompass authorization rules in making access decision; rather UCON model also consider the obligations and environmental condi-tions. Moreover collaborative environments demand the need of enhanced provisioning and controlled access to digital resources. In addition to the immutable attributes that are explicitly modified by the administrator, system controlled mutable attributes are also managed by constant monitoring throughout the stages of usage session. UCON model identifies three types of subjects; consumer, provider and identifiee. Consumers are the subjects who make request to perform certain action on object. Providers are the individuals who own services and issue the rights to the requesting party. Identifiee is the entity whose confidential information is incorporated within digital object. It is an optional group of subjects which may or may not be present depending on system requirements however it is always present in case of systems having users" confidential information. Depending on the job functions of subjects, three types of rights (actions) are specified namely consumer, provider and identifiee rights which indicates the set of actions or privileges on digital objects [START_REF] Park | Towards Usage Control Models: Beyond Traditional Access Control[END_REF]. Apart from these, there are other actions as well that fall in the category to perform updates in attributes values during the phases of usage session which are termed as usage control actions [START_REF] Zhang | Formal model and analysis of usage control[END_REF]. UCON model also classify the objects as privacy sensitive and privacy non sensitive objects that determines whether the object contains critical information of identifiee subject or not. Improper management of privacy sensitive objects cause security breaches which results in data disclosure to unauthorized users and compromising data integrity. There is another phenomenon of UCON model called as reverse UCON in which the position of consumers and providers are inverted depending on the scenario. Complete classification of UCON subjects, objects and rights is shown in Figure 1.

Fig. 1. UCON classification of subject, object and rights

All the traditional models include authorization rules that need to be satisfied before the using the resources called as rights related authorization rules. UCON identify additional obligations related authorization rules which are the set of actions related to access request to be completed before granting permissions of resources. Obligations are first time addressed by UCON model to improve the accuracy of access decision by enforcing users to perform certain actions before access. Obligations also act as functions that check whether the obligatory actions are fulfilled by the requesting entity or not. In order to further increase the accuracy of authorization decision, another factor to be considered important in UCON model are the environmental conditions such as ip addresses, current date or time. Conditions can be of two types; dynamic (stateful) and static (stateless). Dynamic conditions have constantly changing information so they needs to be evaluated for every update and static conditions do not have to be checked for each update during usage session [START_REF] Park | Towards Usage Control Models: Beyond Traditional Access Control[END_REF].

Authorization models of UCON

UCON Pre authorization models are carried out in the same way as for traditional authorization models. In this model, user credentials and resource attributes are checked before granting permission for the requested resource. Pre authorization models can be with immutable and mutable attributes (pre, ongoing and post updates) in which attributes either remain same during access phase or their values change before, during or after the access phase. Ongoing authorization models evaluate the attribute values during the resource usage by the user to perform the continuous verification. Ongoing authorization models can also be with immutable and mutable attributes as with pre authorization models. The effect of ongoing authorization evaluation in access control model is that the access rights can be revoked during the session as certain attribute value is changed.

Obligation models of UCON

Obligation models comprise the pre and ongoing obligation monitoring of access request. They improve the accuracy of access decision in a way that it requests user to perform the access related mandatory actions first and then access would be granted.. Obligations that are used before and during the usage session are termed as pre and ongoing obligations respectively. Post obligations are introduced in order to execute actions after access session is finished i-e access fulfillment notifications to service provider. These post obligations can affect the decision of future usage sessions by generating request to policy repository for policy modification [START_REF] Katt | A General Obligation Model and Continuity-Enhanced Policy Enforcement Engine for Usage Control[END_REF]. Pre, ongoing and post obligation models with immutable and mutable attributes perform the obligation checking before, during or after the access phase.

Condition models of UCON

UCON has two condition models; pre and ongoing condition with immutable attributes to cater the environmental constraints and system related parameters. Conditions are evaluated before and during the session in the same way as authorization rules. Rather condition models do not consider the mutable attributes such as the changing location of a subject.

UCON MODEL SPECIFICATION IN XACML

In order to provide UCON model specification in XACML, we are going to introduce additional identifiers and attribute values to incorporate the features of UCON model. XACML has identifiers for subject categories like access-subject, reci-pient-subject, intermediary subject. They are used under the tag of AttributeDesignator that is one of the methods of attributes retrieval in XACML. Subject-type identifier is introduced for UCON subject categories and their values might be consumer, provider and identifiee. UCON subject identifiers are used along with XACML subject category access-subject to further specify the type of accessing subject as follows.

<AttributeDesignator Rights related authorization rules can be mapped in XACML as general rules but the time of evaluating these rules needs to be managed. So the pre and ongoing element of authorization rules is explained by the rule-id attribute of the rule element.

RuleId="urn: oasis: names: tc: xacml: 3.0:pre-authorization"

Obligation element is specified in XACML for mandatory actions required to be performed by the subject that can also handle the obligation related authorization rules of UCON. Obligation expression element includes arguments that are required to execute the obligation. We have proposed the new attribute namely Fulfill-phase for specification of pre and ongoing obligations. It indicates the access phase during which obligation must have to be satisfied by PEP, so it may have the values of preaccess, ongoing-access that reveals the pre and ongoing obligations.

UCON Access Control Framework

We are proposing an access control framework which has the policy information flow modules of XACML like PDP, PEP, PIP and PAP. Policy repository is a unit in XACML that resides between the PAP and PDP containing the access control policies of corresponding model. Generally PAP creates the access control policies and pushed them into policy repository to be used for evaluation by PDP. We have proposed additional module integrated with PAP that has the capability to interpret the newly created UCON identifiers, attributes and their values. This interpretation will help to determine whether the processing is to be performed in before, ongoing or after phase of usage session. This module is called as UCON policy builder that incorporates UCON model features in policy specification, when PAP accepts the inputs from policy administrator to formulate the generic UCON policy (Fig. 2).

In addition to it, UCON policy engine module is incorporated with PDP that provides the main features of UCON model like attribute mutability and decision continuity.

UCON policy engine has sub modules like attribute mutability (AM) and decision continuity (DC) as shown in Figure3. AM handles the updating of attribute values in three access phases; before, during and after access. As a result of attribute values modification, DC monitors the continuous policy evaluation of three access decision factors; authorization, obligation and condition. So the pre and ongoing models of authorization, obligation and conditions are deployed accordingly with mutable and immutable attributes.

Fig. 2. UCON Access Control Framework

Fig. 3 UCON Policy Engine

UCON policy engine in conjunction with PDP evaluates the combined effect of target, condition, rules and obligations of policy or policy set and applies the specified combining algorithms to generate the final response for user. Functions for continuous policy evaluation are embedded in policy engine to carry out the constant monitoring of attributes, obligations and conditions in order to support the ongoing feature of UCON model. UCON policy engine in combination with policy builder will perform different functions such as obligation monitoring, attributes management, maintaining history of updated events of certain access request, notifies user about the current policy status for request.

Example Scenario

UCON model can be widely adopted in distributed environment to manage the controlled access for applications like health care systems, database management systems, resource sharing systems etc. We are considering the financial application to demonstrate the proposed specification of UCON model in XACML. Managing financial data is one of the key challenges in large enterprises. Financial data is comprised of financial entries regarding its employees, customers, vendors, assets, inventory, products, cost and profit centers etc hence play a vital role in enterprise progress and development. Often the highly secret and confidential in-formation related to enterprise and their employees also reside in these applications, thereby it is required to provide security in terms of data privacy, data loss and data access. General Ledger (GL) is a key component of financial applications that acts as a central repository of company"s accounting transactions. All the business transactions are posted to GL in the form of journal vouchers having debit and credit card entries. These entries are further classified into assets, liabilities, revenues, expenses, capital/owner equity. Core modules of GL includes chart of accounts, financial calendars, journal entries, ledgers, trial balance, balance sheet, profit and loss statement, cash flow statement and user defined report writer.

In this section, we will demonstrate our proposed methodology through the journal entries module. Journal entries are broadly categorized into five types like bank payment voucher, cash payment voucher, bank receipt voucher, cash receipt voucher and journal voucher. Every user of application is not authorized to create/post journal entries rather a user with specific attributes like name, department and role can create/post voucher for certain amount. For authorized users, they are not allowed to create/post entries for all accounts. Moreover an authorized user with permissions to create/post journal entries further requires quota/limit on journal entry amount for the permissible account. Different accounts act as object and the attributes allotted them are accessing list (specifies which user can access this account), limit of total amount (represents value that a user can post for a voucher). In this scenario policy is formulated as; user John having a role of Director General belonging to Administration department cannot post vouchers beyond the limit of 50,000$ in a day time. Further he can only reference City Bank Account # 345678B, 657463C in the credit entries of all vouchers. This scenario workflow is based on pre authorization and ongoing authorization, pre obligation and ongoing obligation and pre condition that are described below according to aforementioned scenario and their corresponding XACML code snippets.

Before providing access to journal entry management service, above specified subject and object attributes are verified according to policy specification that corresponds to pre authorization mechanism. UCON policy engine will represent this pre authorization mechanism for the attribute subject-id "John" as follows.

<Rule RuleId="urn: oasis: names: tc: xacml: 2.0: ucon-example: ongoing-authorization"...> <AttributeDesignator Category="urn: oasis: names: tc: xacml: 1.0: subject-category: access-subject" Type="urn: oasis: names: tc: xacml: 3.0: subject-type: consumer" AttributeId="urn: oasis: names: tc: xacml: 1.0: subject: subject-id" DataType="http://www.w3.org/2001/X MLSchema#string" Class="urn: oasis: names: tc: xacml: 3.0: attribute-class: immutable"/> Since voucher limit of John is fifty thousand for a day, posting voucher service is revoked as limit reaches before a day time. Request is no more facilitated and a mes-sage is prompt to user that he is not eligible to post a voucher in present day. It is an example of ongoing authorization model of UCON which is shown below.

<Rule RuleId= "urn: oasis: names: tc: xacml: 3.0: ongoingauthorization"...> <AttributeDesignator Category="urn: oasis: names: tc: xacml: 1.0: subject-category: access-subject" Type="urn: oasis: names: tc: xacml: 3.0: subject-type: consumer" AttributeId="urn: oasis: names: tc: xacml: 1.0: subject: subject-voucher-limit" DataType="http://www.w3.org/2001/X MLSchema#double" Class="urn: oasis: names: tc: xacml: 3.0: attribute-class: ongoing-mutable"/> Accessing list attribute of account object is updated after the usage session which is the example of post update. This attribute keeps record of users that are accessing certain account, so it is classified as privacy-sensitive object. It is also useful for auditing and management purposes. Obligations are categorized as system related obligations and subject related obligations [START_REF] Katt | A General Obligation Model and Continuity-Enhanced Policy Enforcement Engine for Usage Control[END_REF]. System related obligations are those actions that are executed by the service provider in order to ensure the verification of requesting party. On the other hand subject related obligations are performed by the requesting subject which is enforced by the service provider. In the present situation, subject related pre obligation is to accept the application terms and conditions before accessing journal management service. This subject related obligation is performed just once when the subject requests to access the service for the first time.

<ObligationExpression ObligationId="urn: oasis: names: tc: xacml: ucon-example: obligation: license-agreement" Fulfill-phase="pre-access"> <AttributeAssignmentExpression <AttributeDesignator Category="urn: oasis: names: tc: xacml: 1.0: attribute-category: resource

AttributeId="urn: oasis: names: tc: xacml: 1.0: resource: window-id" </AttributeAssignmentExpression> <AttributeAssignmentExpression <AttributeDesignator Category="urn: oasis: names: tc: xacml: 1.0: subject-category: access-subject" AttributeId="urn: oasis: names: tc: xacml: 1.0: subject: subject-id"> </AttributeAssignmentExpression> </ObligationExpression> As the specific limit of voucher is reached for particular user, insert option for voucher becomes invisible to that user. This is also an example of ongoing obligation performed by service provider. Voucher limit for John is fifty thousand in current scenario, after that the post voucher option is disable for him.

<ObligationExpression ObligationId="urn: oasis: names: tc: xacml: ucon-example: obligation: disabling-post-voucher" Fulfill-phase="ongoing-access"> <AttributeAssignmentExpression <AttributeDesignator Category="urn: oasis: names: tc: xacml: 1.0: attribute-category: resource AttributeId="urn: oasis: names: tc: xacml: 1.0: resource: disable-post-voucher-option"> </AttributeAssignmentExpression> </ObligationExpression> Further conditional parameters might be incorporated as pre condition in the form of user specific ip-address which helps to determine the user location before access. In this case, policy condition element states that specific ip-addresses of "x.x.x.x and "y.y.y.y" (which falls in the organization subnet) can access the service of posting journal voucher.

Conclusion and Future Work

For the applicability of UCON model features in XACML, some of the corresponding modifications are proposed in paper to cater the authorization requirements of distributed environment. Our main objective was to develop the comprehensive UCON framework in XACML that should be reliable, flexible and scalable. XACML being a generic policy language can better translate the UCON model features. It will provide model specifications in a formal manner to be deployed as an access control model by practical application environment. This framework provides the policy administration interface that will help enterprises in implementing UCON model within their applications. It will be generic and consistent to accept the arguments according to scenario and improve the accuracy of access decision. Future directions in this domain include the identification of issues and problems in UCON model with respect to distributed and collaborative platforms like grid and cloud computing. In addition to this, detailed performance analysis, usability and interoperability issues of UCON model need to be addressed. UCON models of authorization, obligations and conditions can further be investigated to integrate them with each other and to show interactions between parallel usage sessions. Moreover, UCON access control framework can be further extended to provide the main feature of extensibility. Different access control models can be incorporated within this framework to offer uniformity and consistency across applications. Depending on application security requirements, organizations can select any model with much more flexibility and ease. Distributed environments such as cloud computing can adopt this generic access control framework to provide better resource protection.

  <ObligationExpression ObligationId="urn: oasis: names: tc: xacml: ucon-example: obligation: license-agreement Fulfill-phase="pre-access"> Condition element in XACML contain single expression element which includes functions to be evaluated. We have introduced additional attribute conditiontype under the condition element to present the UCON dynamic and static conditions. Furthermore pre and ongoing element of condition models are expressed by introducing new attribute called as evaluation-phase under the condition element. It can have the value of pre-access or ongoing access. <Condition Condition-type = "urn: oasis: names: tc: xacml: 3.0: conditiontype: dynamic Evaluation-phase= ongoing-access">

  <Rule RuleId= "urn: oasis: names: tc: xacml: 3.0: ongoingauthorization"...> <AttributeDesignator Category="urn: oasis: names: tc: xacml: 3.0: attribute-category: resource" Type="urn: oasis: names: tc: xacml: 3.0: resourcecategory: privacy-sensitive" AttributeId="urn: oasis: names: tc: xacml: 1.0: subject: accessing-list" DataType="http://www.w3.org/2001/X MLSchema#string" Class="urn: oasis: names: tc: xacml: 3.0: attribute-class: post-mutable"/>

  Mutable attributes are then further narrow down into premutable, ongoing mutable and post mutable. This general classification of attributes is used with all of the attribute categories of subject, resource, action and environment.

	Category=urn: oasis: names: tc: xacml: 1.0: subject-category:
	access-subject
	Type=urn: oasis: names: tc: xacml: 3.0: subject-type: consumer>

In the same way, action-type identifier is introduced with the XACML attribute category of action to reflect the UCON categories of action i-e consumer, provider, identifiee and usage control actions. <AttributeDesignator Category=urn: oasis: names: tc: xacml: 3.0: attribute-category: action Type=urn: oasis: names: tc: xacml: 3.0: action-type: usage-control> For demonstrating UCON objects, resource category identifier is created under attribute category of resource that has the value of privacy-sensitive, privacynonsensitive or derivative. <AttributeDesignator Category=urn: oasis: names: tc: xacml: 3.0: attribute-category: resource Type=urn: oasis: names: tc: xacml: 3.0: resource-category: de-rivative> Since the UCON model consider both mutable (updating values) as well as immutable (constant values) attributes, new identifier attribute-class is constructed to differentiate between them.

<Condition Condition-type = "urn: oasis: names: tc: xacml: 3.0: condition-type: static" Evaluation-phase= pre-access"

	<AttributeValue
	Data-
	Type="http://www.w3.org/2001/XMLSchema#string">127.0.0.
	1
	</AttributeValue>
	<AttributeValue
	Data-
	Type="http://www.w3.org/2001/XMLSchema#string">128.84.1
	03.11
	</AttributeValue>
	</Apply>
	</Apply>
	</Condition>
	FunctionId="urn: oasis: names: tc: xacml: 1.0: function: not"
	<Apply
	FunctionId="urn: oasis: names: tc: xacml: 1.0: func-
	tion: string-at-least-one-member-of">
	<AttributeDesignator
	AttributeId="urn: internetexplorer: names: internetex-
	plorer: 2.1: environment: httpRequest: clientIpAddress"
	DataType="http://www.w3.org/2001/XMLSchema#string"/>
	<Apply FunctionId="urn: oasis: names: tc: xacml: 1.0:
	function: string-bag"


Tomasz Sitarek
email: tomasz.sitarek@ibspan.waw.pl

Wladyslaw Homenda

Efficient Processing the Braille Music Notation

Keywords: data understanding, knowledge processing, music representation, music data processing

Problem stated here is connected with music information processing, especially with Braille music notation. The main objective of this paper is usage of semantics for optimization of Braille music scores processing. This issue is important in the area of huge Braille music scores. Our approach is based on structuring -both syntactical and semantic -in spaces of music information. Optimization would not be possible without such structuring. The main idea is connected with logical score partitioning into smaller pieces that are weakly dependent between each other. Optimization is based on closing changes to small syntactical and semantic items of the structure. Each change during editing touches on of such small items instead of processing significant parts of the whole structure.

Introduction

In this paper we discuss the problem of processing Braille music notation. Braille music notation is an example of language of communication between people and, in this case, it is called a language of natural communication, c.f. [START_REF] Homenda | Integrated syntactic and semantic data structuring as an abstraction of intelligent man-machine communication[END_REF][START_REF] Krolick | How to Read Braille Music[END_REF]. Communication is seen as intelligent exchange of information, which involves information understanding by all sides of communication. Nowadays technologies support information processing helping to improve interpersonal communication. Languages of communication can be seen as tools for constructing vehicles carrying information. These vehicles are texts of natural languages, scores of music notation, scores of Braille music. This remark brings a way to deal with information processing including personal and automatic processing. Such processing requires information structuring as well as identification of structures of information.

In this study we discuss syntactic and semantic structuring of Braille music notation. The discussion is aimed on optimization of automatic processing of big scores of Braille music notation. Namely, we investigate a possibility of avoiding processing of big parts of the whole score in editors of Braille music. Such optimization is worth attention when big scores are edited. However, due to properties of music information, for many symbols of music notation, simple editor's tools do not allow for limited processing. It is necessary to employ deep syntactic and semantic analysis of the score or its fragment corresponding to editing activities in order to limit to necessary minimum the spectrum of processed symbols.

The paper is structured as follows. Fundamentals of syntactic and semantic tools involved in structuring music information are recalled in section 2. In section 3 we describe shortly formats of music information. We only recall general purpose music representation formats and describe to some extent formats related to Braille music notation. These formats are crucial for the main track of this study. Introduced efficiencies in Braille music processing are studied in section 4. On the basis of illustrative examples we describe syntactic and semantic methods leading to minimization of parts of Braille music score subjected to processing during editing operations. Expansion of presented examples to other symbols of music notation is straightforward. Finally, we come to conclusions anchored in real Braille music processing editor developed in frames of the acknowledged research project.

Syntactic and Semantic Mappings

Any intelligent processing of constructions of languages of natural communications requires uncovering structures of raw data. There are different ways leading to structuring. Our interest is focused on employing syntactic and semantic structuring of music information with special emphasis put on Braille music notation. It is obvious that raw data without any structuring is useless in intelligent communication. Otherwise the processing covers some characters from alphabet without any meaning. The aim is to create generic method for integrate syntactic and semantic structuring of music information. This structuring allows for optimized processing of music information described in different languages including Braille music notation and printed music notation. For people with good eyesight we bind Braille music notation with printed music notation in this study. The method is an extension of a likewise study in [START_REF] Homenda | Notes on automatic music conversions[END_REF].

Syntax

Syntactic structuring of music information is the first stage of the analysis process. We will utilize context-free grammars for syntactic structuring of Braille music notation and printed music notation. We refer to and will continue discussion of syntactic structuring outlined in [START_REF] Homenda | Notes on automatic music conversions[END_REF].

Let us recall that we use formal grammars, which are systems G = (V, T, P, S) where: V is a finite set of nonterminal symbols (nonterminals), T is a finite set of terminal symbols (terminals), P is a finite set of productions and S is the initial symbol of grammar, S ∈ V . In general productions can be seen as a finite binary relation

P ⊂ (V ∪ T ) + × (V ∪ T ) * ). A grammar G is context-free one (CFG) ⇐⇒ (∀p)(p ∈ P ⇒ p ∈ V × (V ∪ T ) * ).
Since there is no evidence that Braille music notation is a context-free language, we do not attempt to construct a context-free grammar generating the language of Braille music notation. Instead we use context-free grammars covering the language of Braille music notation. Such grammars will generate all constructions of Braille music notation and some others, which are not valid Braille music constructions. This approach cannot be used in generating Braille music scores or parts of scores or in checking their correctness. However, since we employ context-free grammars for processing scores, which are assumed to be correct, the approach is proven. A discussion on construction of context-free grammars covering printed and Braille music notations is outlined in [START_REF] Homenda | Notes on automatic music conversions[END_REF].

Lexicon

Lexicon is the space of language constructions, each of them supplemented with possible derivation trees, also known as parsing trees. Lexicon includes relations between items of this space. Such a tree satisfies the following rules:

-it is a subtree of the derivation tree of the whole score, -it is the minimal tree generating the given language construction, -the minimal tree can be extended by a part of the path from the root of this tree toward the root of the score derivation tree Due to the last condition, usually there are many trees for a given language construction. We do not recall the meaning of parsing tree in a context-free grammar, refer to [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF] for definition of it.

Different trees supplementing a given language construction describe different context of the language construction. For instance, if we consider a sequence of consecutive notes, the minimal derivation tree for these notes matches all such sequences in the whole score, if more than one is present. If the minimal tree is extended to the root of the derivation tree of the whole score, than it represents only this given sequence of notes, c.f. [START_REF] Homenda | Querying in Spaces of Music Information[END_REF] for details. The concept of the lexicon can be applied, for instance, for better understanding and better performing of structural operations, e.g. find operation.

The World: the Space of Hearing Sensation

Languages allows to describe a real world of things, sensations, thoughts, ideas etc. Braille music notation describes the space of hearing sensations, which can be outlined as the space B × D × P of triples (b, d, p). Each triple defines the performed sound, where b is beginning time, d is duration and p is pitch of this sound. In general, objects of the real world may be outlined with much reacher set of features, but this simple triples are sufficient for our discussion, c.f. [START_REF] Homenda | Notes on automatic music conversions[END_REF].

Above mentioned approach is very generic, refers to physical essence of a sound and has not any links to a particular notation. This structure can be used for any music notation, especially Braille music notation. This definition of the space of hearing sensation is also very useful in case of other structural operations, e.g. conversion, c.f. [START_REF] Homenda | Notes on automatic music conversions[END_REF].

The purpose of using the world of real objects is to tie meaning to syntactic structures, i.e. to tie meaning to lexicon elements of the Braille music notation. This assumption allows us to cast different descriptions music information and different formats representing music information onto the space of hearing sensation. In this way, it is possible to construct collaborating methods, which operate on these different descriptions and formats, c.f. [START_REF]Breaking accessibility barriers in information society. Braille Score -design and implementation of a computer program for processing music information for blind people, the reserach projectconducted in the Systems Research Institute[END_REF]. We apply the idea for formats used in a real processing of Braille music accomplished in frames of the Braille Score project, with the BMF format described in next sections as the space of music sensations.

Semantics

As mentioned in the previous section, descriptions of music notation expressed in different languages and representation of music notation in different formats are cast on the world of hearing sensations. Such casts are called semantics of descriptions and representations of music information. Formally, let B is the lexicon of Braille music notation and H is the space of hearing sensation. Semantics S is a relation:

S ⊂ B × H
The Braille music notation is tightly connected with objects in internal format. Here we consider the BMF format as the example. Every element of the Braille music notation (a character, a Braille cell) contains information about its owner -element from BMF. It is obvious that every Braille cell has such element, because:

-characters present in notation represent some data from BMF. Otherwise they are redundant and would be thrown away from notation, -characters in notation create some data in BMF. Otherwise they are redundant, caries no information and would be thrown away from notation Every element in notation has related element(s) in BMF, and every element in BMF has related element(s) in notation. This relation is many-to-many. One element from BMF may create many Braille cells and one Braille cell may create many elements from BMF. Nevertheless, one meaning is chosen, often not at once, but depending on neighboring Braille cells.

Formats Description

Musical data is stored as files or physical scores (manuscripts or printed ones -images/photos of scores). The files are written in different formats. Rough division enumerates formats that are printed score (e.g. MusicXML files), Braille score (files with Braille music) or pure sound (e.g. MIDI files) oriented.

When processing music data it is convenient to use more than one internal format. Internal formats should meet external formats of data or to make processing easier.

A set of the internal formats is presented in the Figure 1. These structures store musical information in varied way: external types, printed music oriented, Braille music oriented and Braille music files. Between the most of these types is available bidirectional conversion, except one way conversion BNMF → BN. There exist implicit conversions BN → ASCII → BNMF.

Bubble ,,ASCII" represents Braille music written as ASCII file. Bubbles ,,LONG" and ,,PAGE" indicate displayed notation in two manners: as infinite line or as broken line. These two bubbles do not handle structured data, in opposite to other bubbles. Each of the other bubbles from the Figure 1 is described in next paragraph.

External Source

This data source is used to create the main internal format called ,,MF". There is possibility to build MF from following sources: 2) is the main internal format. It is not tied with Braille notation. MF can be displayed and edited as printed music notation. MF consists of several abstract data types, the main are: struction can be misleading because of different naming convention: sometimes multiple staves is called measure; in Braille Score each measure contains one staff, many staves creates system) -Measure -contains VerticalEvents -VerticalEvent -elements that represents one particular event during given measure's time, contains voices slots and additional dynamic/ornamentation information; each voice slot may contain note/rest element This above description is general draft of MF structure. Mentioned elements are emblazoned by additional properties, such as ornamentation, articulation, dynamic symbols.

3.2 MF MF (Figure

BMF

BMF (Figure 3) is the main internal format in Braille music editor. It handles Braille music information encapsulated at high abstraction level. This format's structure is similar to ,,MF", but there are some differences in regard of Braille music notation. BMF consists of:

-Score -represents whole score, contains Staffs, Systems, time signature and many other information about page parameters and metadata (such as title, author, composer, interval reading direction) -Staff -contains Measures, instrument names 4) is simple format that represents Braille dots at high level abstraction with semantic attached. This format is organized as follows:

-Score -represents whole Braille music score, contains Staffs -Staff -contains Measures -Measure -contains BSymbols and ending Small Context -BSymbol -element that represents Braille dots -Small Context -set of elements, that allow to process notation more efficiently, will be described in the next paragraph Each BSymbol has information about protuberant dots of this cell. It has connection to element from BMF, which produces this Braille cell and gives the meaning to it.

This format was chosen to be the target of editing operations. Changes in Braille music notation are made in this format. Then, if necessary, changes are propagated in other formats. 5) is an intermediate layer, that contains both: Braille cells with semantics as an infinite line and Braille cells with semantics as a broken line. This format is an element, that can be displayed or written into the file in both manners: as an infinite line or as a broken line.

BN

BN (Figure

Context

Context is used when reading Braille music notation (e.g. from ASCII file or from BNMF format). It contains information about signs read previously which has influence on current sign.

Efficient Processing the Braille Music Notation

Very often editing operation changes only one measure, and that operation has small scope -single measure or a few measures in the neighborhood. There is no need to process whole score or staff. Using the Small Context, there is an ability to avoid expensive computing.

Draft

Thanks to Context construction, i.e. Small Context included in Context, notation can be faster processed. All changes are made on BNMF, because of presence of pure notation in this case, and operation touches directly notation.

Because of Lexicon construction (rejection from consideration some structures, e.g. slurs between staves), any of the staves can be process independently. Context is used during processing every measure of the score. Each measure remembers Small Context that occurred at the end of processing this measure. Small Context -because it is a subset of Context and contains all extern-measure data. Remembering of the ending (except beginning) Small Context because:

-for each measure k, except the first measure, the beginning context is the ending context of measure (k-1) -for measure number 0 the beginning context is new context -knowledge of ending state at the end of staff

Mechanism of Processing

Processing the Braille music notation occurs in two situations:

-processing a notation the first time -no knowledge about ending contexts for the measures -processing a notation again -knowledge about ending contexts for the measures because of previous processing The first case does not benefits from this method for efficient processing. Processing the whole notation is all and enough what can be done.

The second case allows to avoid processing whole notation. This situation occurs when notation has been changed; the changed measures are marked. We assume that change affects only one measure. In other case, we can treat multiple position change as multiple changes.

Algorithm 1 Algorithm for efficient score processing

Deferred Semantic Bounding

In paragraph 4.2 was made assumption, that each change is processed separately. That approach causes sometimes correct but inefficient processing.

There is a need to design a special mode which allows to defer semantic bounding. This mode prevents score processing till it become switched off. Just after that the score is processed and semantic is bounded too.

The mentioned above mode is useful when paired symbols included in Small Context are added, i.e. slurs or wedges beginnings and endings. It is worthwhile to process score after full symbol insertion, i.e. beginning and ending symbol.

Otherwise it causes instability at the end of measure where insertion occurs: Small Contexts are not equal to ctx. This instability is propagated from the changed measure to the end of the staff (in pessimistic situation). The insertion of the second of the paired symbol causes the same: processing remaining measures. The second phase reverts almost all changed ending Small Contexts to the state from before the first processing.

To sum up: -with deferred semantic bounding the processing affects a few required, changed measures without deferred semantic bounding the processing may affect whole staff twice in pessimistic case (insertion of paired symbols and processing them separately)

Deferred semantic bounding example This section presents example to illustrate deferred semantic bounding issue. Figure 6 shows editing operation that is aimed to add slur in the notation. This process is partitioned in three stages: before operation, after inserting beginning sign of the slur and after inserting ending sign of the slur. Each phase of the slur insertion is described in sequence by: general overview draft, printed music notation and Braille music notation. Correspondence between beginnings and endings of slurs in printed music and signs in Braille music is marked in Figure 6 by bold arrows. The initial score contains three slurs (first stage). In the second stage beginning of the slur is added to the first note. That makes the inserting slur to be opened from one of the ends. In terms of processing the Braille music it creates slur that never ends, that lasts till the score ends. Ending of the slur is inserted in the third stage. After this activity the slur is defined by beginning and ending. The score has four slurs. All changes touch one measure. It means that it is enough to process this particular measure. Efficient processing is performed in that case thanks to deferred semantic bounding.

Figure 7 illustrates inefficient processing. Slurs are marked in the same way as in the Figure 6 -by vertical, bold segments connected in pairs by dotted lines. At the end of each measure the number of opened slurs in marked.

The big arrow in the measure rectangle indicate processing this measure (bounding semantic). The big and dark arrow is connected with changed measure, which should be always processed because it contains the change and is the smallest item of syntactical and semantic sturcturing. The light arrow matches processing that occurs in the measure as a result of changes of small context (refer to algorithm 4.2, step 10). The light arrows appear because of absence of the deferred semantic bounding. In all that cases occur difference between number of opened slurs in first to second and second to third stages for respective measures.

Please notice that the light arrow processings are redundant because numbers of opened slurs in the third stage are the same as in the first stage. That means no final change in opened slurs in measures marked with light arrow.

The above conclusion brings as to deferred semantic bounding. This term means that notation is not processed. This implies no changes in small contexts. Finally, this implies no processing in measures, except one measure where editing operation was performed.

Correct processing is shown in the Figure 8. The dark arrow occurs once because of insertion the beginning sign for slur in deferred semantic bounding mode. There is no light arrows.

Conclusions

This paper is a description of the idea of efficient processing Braille music notation. Appropriate algorithm was proposed to show described method and illustrate additional consequences such as deferred semantic bounding. Efficient processing way can be used with other music languages, e.g. printed music notation. It demands only small context definition and smallest syntax and semantic structures selection.

Introduced method and deferred semantic bounding mode are implemented in Braille Score -application that allows to process music data. Nowadays deferred semantic bounding mode is activated manually, but we consider to automatize this feature.

Fig. 1 .

 1 Fig. 1. A typical data flow in Braille Score

Fig. 2 .

 2 Fig. 2. MF

Fig. 3 .

 3 Fig. 3. BMF

Fig. 4 .

 4 Fig. 4. BNMF

Fig. 5 .

 5 Fig. 5. BN Elements of Context have different scope. Arbitrary division itemizes intermeasure elements (33 units) and extern-measure elements (7 units). The first ones have scope limited to one measure, i.e. they have no influence on signs from other measures. Extern-measure elements have scope limited to one staff and will be called ,,Small Context". To sum up: Context consists of Small Context and inter-measure elements. Small Context contains following elements: -opened slurs count -opened wedges count -intervals reading direction -slurs numbering -short slurs error check -last read note (pitch and octave) -last read attributes (key and time signature) Small Context Equality Two Small Context are equal if and only if theirs respective fields are equal.

Fig. 6 .

 6 Fig. 6. General description of the editing activity.

Fig. 7 .

 7 Fig. 7. Inefficient processing during edition.

Fig. 8 .

 8 Fig. 8. Efficient processing during edition.

Acknowledgement

This work is supported by The National Center for Research and Development, Grant no. N R02 0019 06/2009.


Martin Augustynek
email: martin.augustynek@vsb.cz

Ondrej Adamec
email: ondrej.adamec@vsb.cz

David Micanik

Using a Differential Pressure Sensor as Spirometer

Keywords: Spirometry, lungs, function lungs parameters, digital communication, Matlab

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the past it was possible to perform spirometer only in medical facilities. Older spirometers are voluminous, have high maintenance and their measurement capabilities are very limited. After each patient had to be the instrument properly disinfected to prevent transmission of bacteria. Over time, the dimensions of the device and thus diminished their demands for service and maintenance. The coup came with the advent of pneumotachograph. They also want to specify multiple parameters of lung and especially sharply reduced the size of the device itself. Now, using simple instruments, measurements can be made in domestic environments. Measurement results are displayed on the LCD display device or on a computer screen [START_REF] Penhaker | Lékařské diagnostické přístroje : Učební texty. 1. vydání. Ostrava: VŠB -Technická univerzita Ostrava[END_REF].

This paper describes how to create a demonstration and simple devices for spirometer. It can find usage in a professional environment or in an education area in an university. Modern digital sensor was used with excellent high sensitivity, low power consumption and preprocessing options. It was also used Matlab programming options.

For spirometry is possible to use several different methods like water spirometer, dry-bellowed wedge spirometer or fully electronics spirometer, typically. Electronic spirometers have been developed that compute airflow rates in a channel without the need for fine meshes or moving parts. They operate by measuring the speed of the airflow with techniques such as ultrasonic transducers, or by measuring pressure difference in the tube [START_REF] Cerny | Wireless Body Sensor Network in Health Maintenance system[END_REF]. These spirometers have greater accuracy by the momentum and resistance errors associated with moving parts such as windmills or flow valves for flow measurement. They also allow improved hygiene between patients by allowing fully disposable air flow channels.

Measuring set

Principle of measuring a spirometry was chosen differential manometer. Spirometer body is made up of a biological filter HEPA Light. Electronics device includes a digital component to communicate with a computer. This solution enables the processing of measured data using specialized software without having to perform other calculations.

The sensor is a product of Swiss company Sensirion (see Tab. 1). The sensor output is digital, the I2C bus. Temperature calibration is automatically done by the sensor and electronics output is already linearized. Influence of initial offset aging of the material is given less than 0.1 Pa per year. The default sensitivity resolution of 12 bits (can be 9 to 16 bits) is given 0, 2 Pa . The sensor is recommended, inter alia, in health care. This sensor offers the best fit of desired parameters and especially its digital output, thus allowing easier processing in the computer.

The measurement is started by breathing into the spirometer. The digital signal is converted into comprehensible forms for serial communication. The computer information is drawn from the serial line and the measurement is complete interpretation of the measured values. Result can be interpreted as a graph or directly calculated values of lung parameters. The measurement block diagram is displayed in Fig 1.

Calibration

The value of the pressure difference p  is linearly dependent on the volume v q and size of air flow resistance R (see ( 1)).

21 v p p p R q      (1)
To calculate the correct flow of gas was needed to determine the value of air resistance. The gas flow is expressed first by equation ( 1) and from already adjusted equation ( 2) is calculated the gas flow value

v q . v v p q q   (2)
The value of pressure difference and flow rate were known during the calibration. Therefore equation ( 2) was modified into (3).

v p R q   (3)
The gas rate was simulated using a phantom of an air, in the range of 1 0,3 Ls   to 1 0,85 Ls   . Phantom of air was connected to the spirometer input and the differential pressure was sensed by a computer with a period of 10 s. Readout pressure was calculated by averaging the readings over one minute.

Next table (see Tab. 2) shows results from calibration. The average air resistance R was calculated as the mean of the measured resistance and is equal to 1 0, 2029 Pa s L   . This value was set as the resistance to air flow. Then it is easy to compute unknown air flow by (2) because p  is measured and R is known from previous computation.

Table 2. Computed resistance R. 1 v q L s       p Pa  1 R Pa s L     0,30
0,0325 0,14 0,35 0,0490 0,1083 0,40 0,0653 0,1632 0,45 0,0817 0,1816 0,50 0,0980 0,1960 0,55 0,1143 0,2078 0,60 0,1307 0,2178 0,65 0,1470 0,2262 0,70 0,2251 0,3216

Testing

Test was made for all functions of the device and measurement software. Readings from the program were compared with values measured on the spirometer made by ZAN. The spirometer ZAN100 (the principle of differential pressure) was used for testing. There have been several controlled test measurements. The next table (see Table 3) shows results from testing.

The difference of the reference level and minimum inspiration values is equal to the peak of inspiration flow (PIF) in liters per second. By integrating the volumetric flow across the interval of maximum inspiration is received a value of vital lung capacity in liters. See (4) where 1,2

t is start and end of inspiration, v q is volume flow and V is vital lung capacity. [START_REF]Become an expert in spirometry[END_REF][7] Next figure (see Fig. 3.) shows the record along breath made from one inspiration and expiration, and an intensive inspiration and expiration.

2 1 t v t V q dt   (4)

Conclusions

Method of measurement using differential manometer was chosen. Durability and reliability of the spirometer are improving by no moving parts are needed during the measurement. For compiling of the devices were used materials from health care, or materials wholesome. HEPA filter Light is used as the air resistance to the spirometer. It also serves as a barrier to the spread of bacteria. Spirometer is designed for easy using with the hygienic mouthpiece.

Electronic part of the device was selected for processing of signal on the computer. As differential sensor, the digital sensor SDP610 from the company Sensirion has been selected. With the compensation capabilities of this sensor is not necessary to further modify the signal. The signals from the sensor are transferred via serial communication line and then sent to a computer. In the computer was created software for processing.

Sensor SDP610 proved to be very suitable sensor with potential for use in medical applications.

Fig. 1 .

 1 Fig. 1. Measuring set.

Fig. 2 .

 2 Fig. 2. Software window.

Fig. 3 .

 3 Fig. 3. Air flow along breath and intensive breath.

Table 1 .

 1 Sensor parameters.

	Non-electric value is

Table 3 .

 3 Compare between SDP610 and ZAN100.

	Parameters	SDP610	ZAN100
	PEF	3,6	1 Ls  	3,8	1 Ls  
	PIF	3,4	1 Ls  	3,6	1 Ls  
	VC	5,2	L	5,5	L

Acknowledgements

The work and the contribution were supported by the project Student grant agency "Biomedical engineering systems VIII" and TACR TA01010632 "SCADA system for control and measurement of process in real time".

Has been elaborated in the framework of the IT4Innovations Centre of Excellence project, reg. no. CZ.1.05/1.1.00/02.0070 supported by Operational Programme 'Research and Development for Innovations' funded by Structural Funds of the European Union and state budget of the Czech Republic.