Modified Storage Placement In Wireless Sensor Network

Modified Storage Placement In Wireless Sensor Network

Sagar M. Mane MECSE, Department of Computer Science & Engg. Walchand Institute

of Technology, Solapur, India

Dr. Mrs. S. S. Apte

Professor, Department of Computer Science & Engg. Walchand

Institute of Technology,Solapur,India

ABSTRACT

In sensor network a large amount of data need to be collected for future information retrieval. The data centric storage has become an important issue in sensor network. Storage nodes are used in this paper to store and process the collected data. This paper considers the storage node placement problem aiming to place unlimited storage nodes in sensor network to minimize the total energy cost for collecting the raw data and replying queries at the storage nodes. In this paper a strong data access model for placing storage nodes in sensor network is presented. We consider an application in which sensor networks provide real time data services to user. The main aim of this paper is to reduce the cost for raw data transfer, query diffusion, query reply by defining the best location of storage nodes in sensor network.

Keywords

Wireless sensor network, data query, data storage, data reply

1. INTRODUCTION

   One of the key challenges in wireless sensor network is the storage and querying of useful sensor data. The wireless sensor network is built of nodes, where each node is connected to one or more sensors. Sensor networks deployed for different computing applications,.e.g.,sensing environmental or earth condition and monitoring peoples behaviors, generates a large amount of data over a long period of time. Storage is an essential factor of any data centric sensor network application. One of the main challenges in these applications is how to search and store the collected data. The collected data can either be stored in the network sensors, or transmitted back to the sink and stored there for future retrieval. This design is ideal since data are stored in a central place for permanent access. Placing unlimited storage nodes is related to the sensor network. Query is the most important part of sensor network since in aspect sensor network provides the information about environmental condition to the end user.Therefore, we aim to minimize the total energy cost and data query by accurately deploying the storage nodes in sensor network. In section 4 we discuss the data access model. In section 5, we present the conclusion and future work.

2. RELATED WORK

   There has been a lot of prior research work on data querying models in sensor network. In early models [1, 2, 3], query is spread to every sensor node by ooding messages. Sensors nodes

   send data back to the sink in the reverse direction of query messages. Those methods do not consider the storage concern in sensor networks.

   PRESTO [4] is a recent research works on storage architecture for wireless sensor networks. A proxy layer is introduced between sensor nodes and user terminals and proxy nodes can cache previous query responses. When a query arrives in a proxy node, it rst checks if the cached data can satisfy the query before forwarding the query to other nodes. Compared with the storage nodes in this paper, Nodes in PRESTO have no resource constraints in term of computation, power, storage and communication. It is a more familiar storage architecture that does not take the characteristics of data generation or query into consideration.

   Data-centric storage schemes [5, 6, 7] store data to different places in sensor networks according to different data types.

   In [6, 7], the authors propose a data-centric storage scheme for sensor networks, which inherits ideas from distributed hash table. The home site of a data is obtained by applying a hash function on the data type.

   LEACH [8] is a clustering based routing protocol, in which cluster heads can fuse the data collected from its neighbors to reduce communication cost to the sink. LEACH has a similar structure to our scheme, having cluster heads aggregate and forward data to the sink. However, LEACH aims to reduce data transmission by aggregating data; it does not address storage problem in sensor networks

3. Placing Unlimited Number of Storage nodes

   Algorithm1 finds the optimal placement of storage node for the

   case Rq Rd.Assume that n nodes in the tree T are labeled using the post order. A table e[1..n] is used to hold

   the minimum energy cost of all sub trees rooted at node i = 1, . . . , n. So at the end of the computation, e[n] will hold the

   minimum energy cost of T. we also maintain a second table ef[1..n] which records the energy cost of all sub trees when all nodes in each sub tree are forwarding nodes. In the algorithm, line 5-9 compute the e* and ef entries for all leaves and lines 10-19 compute the e* and ef entries for the remaining nodes.

   Let i be any node in the communication tree and Ti be the subtree rooted at i. We use |Ti | to denote the number of Nodes in Ti. We define E(i) to be the energy cost incurred at i per time unit, which consist, the cost for raw data transfer i to its parent if i is a forwarding node, the cost for query diffusion if i has storage nodes as its descendants, and the cost for query reply if i is a storage node or has a storage descendant. To define E(i) mathematically we need to consider several possible cases.

   1: make the root a storage node 2: if Rq Rd then

   3: make all non-root nodes forwarding nodes and return

   4: end if

   5: for all leaves i do 6::make i a storage node 7: e*[i]=RqSd

   8: ef[i]=RdSd

   9: end for

   10: for all remaining nodes i do 11: make i a storage node

   12: min1=Rq|Ti|Sd+BiRqSq+jci e*[j]

   13: min2=Rq|Ti|Sd+jci ef[j]

   14: e*[i]=min{min1,min2}

   15: ef[i]=|Ti|RdSd+jci ef[j] 16: if min1min2 then

   17: change each descendent of i that is a storage node to a forwarding node

   18: end if

   19: end for

   Algorithm.1: Placing unlimited storage nodes

   Case I: i is a forwarding node and there are no storage nodes in Ti . All raw data generated by the nodes in Ti have to be forwarded to the parent of i and there is no query diffusion cost. So E(i) = |Ti |Rd Sd .

   Case II: i is a storage node and there are no other storage nodes in Ti. The latest readings of all raw data generated by the nodes in Ti are processed at node i and the reduced reply

   Let E1 and E2 be the energy cost of the roots in the two trees, respectively. Therefore, e1 e2 = E1 E2 .

   We consider two cases. First, if both root have no storage descendants, then according to the four different case definition of energy cost (case I and II), we have

   E1-E2 = |Ti| Rd Sd -Rq |Ti|Sd

   = Ti| Sd(Rd-Rq)

   Second, if both roots have at least one storage descendant, then according to the four different case definition of energy cost (Cases III and IV), we have

   E1-E2 =((d1+1)RdSd+BiRqSq+Rqd2Sd) (Rq|Ti|Sd+BiRqSq)

   = (d1+1)Sd(Rd-Rq)

   From the above lemma, we can conclude that if Rq Rd

   then every node (except for the root/sink, which is always a storage node) in the sensor network must be a forwarding node to minimize the energy cost.

   The query diffusion cost can be eliminated if every subtrees of i has only forwarding nodes, i.e., E(i) = Rq ||Ti |Sd.(See Cases III and II in the four-case definition of E(i)) Thus, the minimum energy cost of the tree rooted at i should be derived from the

   better of these two scenarios.

   For a tree Ti rooted at i, let Ci be the set of children of i.Let e(i) be the minimum energy cost of Ti . If Ci is empty,

   i.e., i is a leaf, then i must be a storage node to achieve its

   size will be |Ti |sd. Node i sends the reply to its parent when queries arrive. So E(i) = Rq |Ti|Sd.

   minimum energy cost. So e(i) = Rq

   Sd

   . If Ci

   is not empty,

   Case III. i is a storage node and there is at least one other storage node in Ti. In addition to the cost for query reply as

   then for any j Ci , let ef (j) be the energy cost of Tj when

   all nodes in Tj are forwarding nodes. So

   defined in Case II, i also incurs a cost for query diffusion that is implemented by broadcasting to its children. So E(i) = Rq |Ti|Sd + Bi Rq Sq .

   e (i) = min {Rq |Ti |Sd + Bi Rq Sq +jci e(j) ,

   Case IV. i is a forwarding node and there is at least one Storage node in Ti. This is the case where all three types of cost (for query diffusion, raw data transfer, and query reply) are present. Among the |Ti | 1 descendants of i, let d1 be the number of forwarding descendants without any storage nodes on their paths to i and d2 be the number of storage descendants or forwarding descendants with at least one storage node on their paths to i . Obviously, d1 + d2 = |Ti | 1. So

   E(i) = (d1 + 1)Rd Sd + Bi Rq Sq + Rq d2 Sd .

   Our algorithm relies on following lemma.

   Lemma 1.Given a node i and its sub tree Ti. If RqRd, then i must be a forwarding node to minimize e(i).if RqRd, then i must be a storage node to minimize e(i).

   Proof: First we compare the two trees based on their energy cost, which are equivalent in every aspect except that the first trees root is a forwarding node and the second trees root is a storage node. Let e1 and e2 be the two trees based on their energy cost. Comparing the two trees using the energy cost of individual nodes, one by one, we observe that any two non- root nodes in the same position of the trees must have the similar energy cost. The only change is the energy cost of the roots.

   Rq |Ti| Sd +jci ef (j) }.

   From the design of the algorithm, we also observe that every node starts as a storage node and that once it is changed to a forwarding node, it will never be changed back. Therefore, all its descendants are replaced to forwarding nodes as well. it is impossible for a forwarding node to have a storage node descendant. Likewise, it is impossible for a storage node to have a forwarding node ancestor.

4. System Architecture:-

   In this paper, we consider an application in which sensor networks provide real-time data services to users. A sensor network is given with one defined sensor identified as the sink (or base station), access point and many normal sensors, each of which generates (or collects) data from its environment. Users or application program specify the data they need by submitting queries to the sink and they are usually interested in the latest readings generated by the sensors. To reply to queries, one typical solution, shown in fig.1, is the sinks have all the data.

   Figure 1: Data Access Model with Storage Nodes and Forwarding Nodes

   Figure 1: Data Access Model with Storage Nodes and Forwarding Nodes

   This requires each sensor to send its readings back to the access point immediately every time it produces new data. Transferring all raw data could be very expensive and is not always required. Alternatively, we allow sensors node to hold their raw data and to be aware of the different queries, then raw data can be managed to contain only the readings that users are interested in and the reduced reply size, instead of the whole raw data readings, can be send back to the sink. This design is illustrated in Fig. 1, where the black sensor nodes, called storage nodes, are allowed to hold raw data. The base station diffuses queries to the access point by broadcasting to the sensor network and then access point broadcast the queries to storage sensors and these storage sensors reply to the queries by sending the processed data back to the storage node. Compared to the earlier solution, this approach reduces cost of the raw data transfer because some raw data transmissions are replaced by query reply. On the other hand, this scheme incurs an extra query diffusion cost (as figured by the dashed arrows). In this paper, we are interested in vital designing a data access model to minimize energy cost associated with query diffusion, raw data transfers, and query replies.

   Access Point:When the user fires the query on the sink, sink forward the query Request to the access point. Access point broadcast the query to sensor nodes. When the query arrived at storage nodes they forward the raw data back to the access point and then access point obtain the result and forward the data to the sink..

   We first formally define two types of sensors (or nodes): Storage nodes: These types of nodes have much larger storage capacity than normal sensor nodes. In the data access model as shown in fig.1, they store all the data received from other nodes or generated by themselves. Storage node does not send anything until queries arrive. According to the query specification, they receive the results needed from the raw data they are holding and then return the results back to the base station. The base station itself is considered as a storage node.

   Forwarding nodes: These types of nodes are regular sensors and they always forward the data received from other nodes or generated by themselves along a path towards the sink. The outgoing data are kept intact and the forwarding operation continues until the data reach a nearest storage node. The raw data forwarding operation is independent of queries and there is no data processing at forwarding nodes.

5. CONCLUSION AND FUTURE WORK

   This paper considers the storage node placement problem in a sensor network. This paper introduces unlimited number of storage nodes in sensor network release the cost of sending all the raw data to a central place. In this paper, we examine how to place unlimited number of storage nodes to save energy for data collection and data query. This new model is much more simplified and implementable. We have tested it on different data sets available on internet using network simulator software. Our future work includes placement of limited number of storage nodes in sensor network to optimize query reply in a sensor network and to solve the storage node placement problem in terms of other performance metrics.

6. REFERENCES

1. C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th annual international conference on Mobile computing and networking, pages 5667, New York, NY, USA, 2000. ACM Press

2. C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva. Directed diffusion for wireless sensor networking. IEEE/ACM Trans. Netw., 11(1):216, 2003.

3. S. Madden, M. J. Franklin, J. M. Hellerstein,and W.Hong TAG: a tiny aggregation service for ad-hoc sensor networks.SIGOPS Opererating System Review, 36(SI):131146,2002

4. P. Desnoyers, D. Ganesan, H. Li, M. Li, and P. Shenoy. PRESTO: A predictive storage architecture for sensor networks. In Tenth Workshop on Hot Topics in Operating System, 2005.

5. J. Newsome and D. Song. GEM: graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of the 1st international conference on Embedded networked sensor systems, pages 7688, New York, NY, USA, 2003. ACM Press.

6. S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu.

   Data-centric storage in sensornets with GHT, a geographic hash table. Mobile Networks and Applications, 8(4):427442, 2003.

7. S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and

D. Estrin. Data-centric storage in sensornets. SIGCOMM Computer Communiction Review, 33(1):137142, 2003.

[8] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan.Energy-efficient Communication Protocols for Wireless Microsensor Networks. In

International Conference on System Sciences, Maui, HI, January 2000.

1. D. Ganesan, D. Estrin, and J. Heidemann. Dimensions: why do we need a new data handling architecture for sensor networks?SIGCOMM Comput. Commun. Rev., 33(1):143 148, 2003.

2. E. J. Duarte-Melo and M. Liu. Data-gathering wireless Sensor networks: organization and capacity . Computer Networks (COMNET), 43(4):519537, Nov. 2003.