Aggregation In Wireless Networks Using Randomized Routing Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

With a widespread growth in the potential applications of Wireless Sensor Networks, the need for reliable security mechanisms for them has increased manifold. This paper proposes a scheme to secure data aggregation that relies on multilevel routing. We prepare aggregates or summary of information gathered and store it in the repository. The privacy factors have been identified and implemented. We also argue that wireless sensor network is very promising for police patrol applications.

Key words: WSN, encrypted aggregation, secure routing, location privacy

1 Introduction

Wireless Sensor Networks

A Wireless Sensor Network (WSN) consists of spatially distributed autonomous sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants.

A sensor network normally constitutes a wireless ad-hoc network that is each sensor supports a multi-hop routing algorithm where nodes function as forwarders, relaying data packets to a base station.

Unlike traditional wireless devices, wireless sensor nodes do not need to communicate directly with the nearest high-power control tower or base station, but only with their local peers. Instead, of relying on a pre-deployed infrastructure, each individual sensor or actuator becomes part of the overall infrastructure. Peer-to-peer networking protocols provide a mesh-like interconnect to shuttle data between the thousands of tiny embedded devices in a multi-hop fashion. Fig 1 depicts the basic sensor architecture. The flexible mesh architectures envisioned dynamically adapt to support introduction of new nodes or expand to cover a larger geographic region. Additionally, the system can automatically adapt to compensate for node failures.

Security in WSN

The resource-starved nature of sensor networks poses great challenges for security. However, in many applications the security aspects are as important as performance and low energy consumption.

a) Security challenges:

The broadcast nature of the wireless communication renders a WSN susceptible to link attacks ranging from passive eavesdropping to message replay and message distortion

The network deployment in hostile environments (e.g. battlefield, forest) with relatively poor physical protection

The limitations in energy, computational power and memory of the tiny sensors

The extremely large number of interacting devices in a sensor network

The dynamic nature of WSN (frequent changes in both its topology and its membership)

Fig 1: Basic sensor network architecture.

Routing in WSN

Wireless sensor networks are formed by small devices communicating over wireless links without using a fixed networked infrastructure. Because of limited transmission range, communication between any two devices requires collaborating intermediate forwarding network nodes, i.e. devices act as routers and end systems at the same time. Communication between any two nodes may be trivially based on simply flooding the entire network. However, more elaborate routing algorithms are essential for the applicability of such wireless networks, since energy has to be conserved in low powered devices and wireless communication always leads to increased energy consumption.

The first routing algorithms for wireless networks followed the traditional approach of topology-based routing, i.e. forwarding decisions are based on information about currently available links between network nodes. Early proposals are based on proactive routing strategies maintaining routing information about all available paths even when these paths are never used. Proactive routing does not scale well in dynamically changing network topologies, thus, reactive methods maintaining only these routes which are currently in use have been investigated further on.

Data Aggregation in WSN

Data aggregation is an important primitive in wireless sensor networks (WSN). Data aggregation is a process that collects data from different sources and expresses the data, based on specific variables, in a summarized format. By eliminating redundant or unnecessary information from transmitted data streams, data aggregation can drastically improve the communication efficiency of a sensor network. This is especially desirable in resource-constrained networks, such as WSN, where it has been shown that radio energy dominates total energy expenditure on a sensor.

A significant risk of data aggregation however is that a node that is captured by an adversary can report arbitrary values as its aggregation result, thereby corrupting not only its own measurements but also that of all the nodes in its entire aggregation sub-tree. As a consequence, an adversary who captures nodes selectively and strategically can corrupt the entire network aggregation process, while incurring minimal cost and effort. This is called the aggregation integrity problem.

2 Related Work

A thorough Literature Review of the available papers is done and some of the papers are listed along with the context in which the idea of the paper was studied for the inception of this project.


Cryptography is the basic encryption method used in implementing security. Cryptographic methods used in WSNs should meet the constraints of sensor nodes and be evaluated before choosing. It is feasible to apply public key cryptography to WSNs by choosing appropriate algorithms, parameters, etc., private key operations in asymmetric cryptography schemes are still too expensive in terms of computation and energy cost for sensor nodes, and still need further studies. In this section, we focus on cryptography evaluations and cryptography architectures

Cryptography Evaluations: To evaluate the computational overhead, Ganesan, et al. in [11] chose RC4, IDEA, RC5, MD5 and SHA1. RC4 is shown to outperform RC5 for the Motes Atmega platform contrary to the choice of RC5 for the Motes project [5], where a model was derived to allow the interpolation of performance for other architectures. Law et al. [21] compare several and conclude that Rijndael is the suitable cipher when considering security and energy efficiency for sensor networks, and MISTY1 is a good selection when considering storage and energy efficiency.

Secure Routing

WSNs use multi-hop routing and wireless communication to transfer data, thus incur more routing attacks. There are a lot of approaches to ease routing security. In this section, we review existing secure routing approaches.

Secure Routing Protocols for Ad Hoc Networks: Some secure AODV algorithms [1] that may be adapted in WSNs have some effects on defending against external attacks because they suggest secure routing information. An on-demand routing protocol for ad hoc to provide resilience to Byzantine failures, proposed by Awerbuch, et al. can be separated into three successive phases: route discovery with fault avoidance by using flooding and cryptographic primitives, and link weight management by multiplicatively increasing the malicious link weight. Their protocol avoids malicious links in the routing paths because the system uses an on-demand route discovery protocol that finds a least weight path to the destination.

Multi-Path Routing: Some approaches use multi-path routing and neighbour collaboration techniques, such as [8]. Multi-path routing, location disguise, and relocation methods can be used to protect base stations [8]. In the environment where the network only has a small number of compromised nodes, Multi-path schemes provide more reliable routing, though they introduce more communication overheads. However, in the environment where the network has a large number of compromised nodes, if the compromised can modify the routing data, system may involve more security issues.

Data Aggregation

Fang-Jing Wu and Yu-Chee Tseng[10] defined a data aggregation algorithm that focuses on less strict set of interference neighbours as the set of communication nodes is limited and the transmission directions are toward the sink. But how to schedule multiple tasks at the same time in an efficient way was not discussed.

A secure and fault-tolerant data collection scheme[20] with EBS group key management mechanism, termed as CRINet, was proposed. In CRINet, the encrypted data reports sent from the source group are relayed to the BS by a 3-way routing approach, for increasing data delivery rate and thus enhancing the fault-tolerant capability. But this increases the communication overhead. Mohanty, Sarma, Panigrahi, Satapathy investigated different possible attacks on the cluster base data gathering protocol and tried to give a symmetric key based security solution[12] to it. This security solution either eliminated or localized the attacks only within a smaller region.

3 System Design

Flaws in the Existing Methodologies

The existing techniques suffer from at least one of the major problems listed below:

No secrecy and privacy.

Encryption techniques are sometimes not implemented.

Redundant data exist.

Key management is not flexible.

XOR operations are performed for data aggregation.

Network is vulnerable to adversaries and hence attacks like Known-plaintext attack, Chosen-plaintext attack, and Man-in-the-middle attacks.

Hence security factor is not high.

Proposed Work

Our objective is to develop a system that performs data aggregation in wireless sensor networks focusing on security and routing to increase the efficiency and reduce the overhead. To solve the above described problems, our paper centres around a solution that constitutes of three phases. This approach integrates data aggregation technique with efficient randomized multi-path routing algorithm and cryptographic technique to ensure privacy, secrecy and less overhead. The three phases include:

Phase 1 - Encryption: Security must be ensured over the data sent via the network to preserve secrecy. Thus, we encrypt the data with efficient algorithm and send the cipher text to the aggregator, to avoid any adversary to eavesdrop on the content.

Phase 2 â€" Routing: It is apparent that, cipher texts can be broken down by the adversaries using cryptanalysis. Hence the process of routing plays an equal role in the process of security.

Phase 3 - Data Aggregation: The aggregators collect data from a subset of the network, aggregate the data using a suitable aggregation function and then transmit the aggregated result to an upper aggregator or to the querier who generates the query [Fig. 2].

Fig 2: Data aggregation in clustered WSN.

To reduce the transmission overhead, we concentrate on discarding the redundant data (i.e. forwarding only one copy of the data) and we provide algorithms to accomplish this purpose.


Our proposed architecture is illustrated in Fig. 3. The wireless sensors in the network are used to record some information. This data has to be forwarded it to the requesting node in the network in case of a query.

Fig 3: Architecture


Criteria to achieve privacy:

Trustworthiness: Systems must be technically reliable and instill confidence in users. This is achieved by registering in prior.

Appropriate timing: Feedback should be provided at a time when control is most likely to be required and effective. Here, the Police Commissioner responds timely to the police officers by reporting the crime.

Perceptibility: Feedback should be noticeable. The data sent to the police officer is identified using RFID.

Unobtrusiveness: Feedback should not distract or annoy. It should also be selective and relevant and should not overload the recipient with information.

Minimal intrusiveness: Feedback should not involve information which compromises the privacy of others. We implement mix zone model to achieve this.

Flexibility: What counts as private varies according to context and interpersonal relationships. Thus mechanisms of control over user and system behaviors may need to be tailorable to some extent by the individuals concerned.

Meaningfulness: Feedback and control must incorporate meaningful representations of information captured and meaningful actions to control it, not just raw data and unfamiliar actions. They should be sensitive to the context of data capture and also to the contexts in which information is presented and control exercised. Context summarization is realized here.

Low cost: Naturally, we wish to keep costs of design solutions down.


Radio Frequency Identification (RFID) Tags represent probably the most prominent ubicomp technology, at least when it comes to privacy issues. The privacy challenges of RFID tags are fourfold:

Automation: Reading an RFID tag typically does not require the help of the person carrying the tag, nor any manual intervention on behalf of the reader. Thus, simple reader gates can easily scan large numbers of tags, making data acquisition much easier.

Identification: The ability to identify individual items instead of only whole classes of items significantly improves the ability to identify an individual. This would facilitate, e.g., the creation of detailed consumer or citizen profiles.

Integration: Not only that the act of reading a tag can be completely hidden from the tag carrier (especially when operating at larger distances), also the fact that a tag is present in a particular product will be hard to ascertain for an individual without special detection equipment.

Authentication: The above points become especially critical given the increasing amount of sensitive information, e.g., health information, payment details, or biometric data that are stored on or linked to tags used in authentication systems.

These four attributes of RFID applications threaten two classes of individual privacy: data privacy and location privacy. The location privacy of a person is threatened if a tag ID that is associated with that person is spotted at a particular reader location.

Mix Zone Model:

In a mix zone, a mobile user is given a new pseudonym to help mix him or her with other users in the same zone as shown in the figures 4(a) and 4(b).

Fig 4: Mix Zone Model

4 Implementation

4.1 Knowledge Summarization:

Context aware systems define context as any information that is useful in describing the current situation or context of user. For pervasive computing environment, here, the context is police officer’s current location, activity, current time, schedule, etc. Our Summarization techniques try to identify the useful context information and keep the summarized context information in the knowledge repository for further use.

Context Summarization (CS) is a method of representing raw context information into summarized information so that it takes relatively less storage space and can successfully answer the queries for complete information with acceptable degree of confidence. Such a compact representation of information reduces required storage space. The techniques include:

4.1.1 Aggregation:

The aggregator performs its functionality in the data management layer. We used basic XOR function to perform the aggregation. As shown in Fig.5, when the aggregator receives the encrypted data from two or more nodes, it XORs the data received from the nodes by pairing them in twos.

a=E(m1) E(m2)

If the output of XOR is obtained as 0, it implies that the data from this pair of nodes are the same and only one copy of the data is forwarded to the sink. Otherwise it compares it with the next paired node and repeats the process exhaustively. Once all the nodes are compared, the non-redundant data are forwarded to the sink, which decrypts the messages to understand the data.

Fig 5: Aggregation model

4.1.2 Pattern Identification:

Context information can be summarized by identifying general patterns and later answering approximately to the queries using these patterns.

4.2 Encryption:

The system needs to be protected against adversaries who may eavesdrop or tamper with the message being passed around in the wireless sensor network. This is achieved by encrypting the message prior to sending it to the destination nodes.

AES is a block cipher, symmetric key algorithm. It has an initial round and 10, 12 or 14 standard rounds. The encryption process starts arranging the block in a matrix form termed State. The Rijndael algorithm is a symmetric key cipher implementing a substitution-permutation network.

The 4 major steps in this process are Substitute Bytes, Shift Rows, Mix Columns and Add Round Key.


4.3.1 Intra-node Routing:

The application layer generates the messages and takes care of the debugging. Sensor stores the data in a table (Fig. 6). Data Management does the required aggregation. Localization layer passes the messages to the neighboring layers. MAC layer reduces the end-to-end packet delay during transmission and also reduces the collisions by putting the data in a queue.

Fig 6: Layered architecture of each node

4.3.2 Randomized Routing:

Routing layer implements the randomized routing technique. This layer has the required routing information. At layer 0, when a sensor node wants to send a packet to the aggregator, it first breaks the packet into M shares, according to a (T, M)-threshold secret sharing algorithm. Each share is then transmitted to some randomly selected neighbour. That neighbour will continue to relay the share it has received to other randomly selected neighbours, and so on. In each share, there is a TTL field, whose initial value is set by the source node to control the total number of random relays. After each relay, the TTL field is reduced by 1. When the TTL value reaches 0, the last node to receive this share begins to route it toward the aggregator using min-hop routing. Once the aggregator collects at least T shares, it can reconstruct the original packet. No information can be recovered from less than T shares. It then checks for the redundancy of the data before forwarding it to the sink.

4.4 Simulation Results

Fig 7 shows the screenshot of the system taken into consideration, upon which the above described procedure was implemented. The system consists of a network with 50nodes and aggregator.

Fig 7: Screenshot

The performance analysis graph (fig. 8) shows us that randomized multilevel routing performs better at higher network load levels when compared to mere shortest path routing.

Fig 8: Performance analysis graph

5 Conclusion and Future Work

The overview of the research work carried out in the field of wireless sensor networks is described above and we have listed out the pros and cons of each concept involved.

The problem domain has been analyzed well and a clear outline of the solution has been developed. This paper performs the combination of encryption, routing and a basic aggregation technique in wireless sensor networks. From the implementation perspective, various encryption algorithms have been studied and implemented; for routing, randomized and multilevel routing are implemented to provide security and efficiency; XOR is used for aggregation, which eliminated the redundancy.

This system uses a lot of communication overhead because of the spitting a packet into shares and overhead is high at each node because of multiple levels. Also, a more efficient data aggregation technique must be designed which ensures equivalent privacy. The system can be further developed to work on a large set of nodes.