Extending 3-bit Burst Error-Correction Codes With Quadruple Adjacent Error Correction

Extending 3-bit Burst Error-Correction Codes With Quadruple Adjacent Error Correction

ABSTRACT:

The use of error-correction codes (ECCs) with advanced correction capability is a common system-level strategy to harden the memory against multiple bit upsets (MBUs). Therefore, the construction of ECCs with advanced error correction and low redundancy has become an important problem, especially for adjacent ECCs. Existing codes for mitigating MBUs mainly focus on the correction of up to 3-bit burst errors. As the technology scales and cell interval distance decrease, the number of affected bits can easily extend to more than 3 bit. The previous methods are therefore not enough to satisfy the reliability requirement of the applications in harsh environments. In this paper, a technique to extend 3-bit burst error-correction (BEC) codes with quadruple adjacent error correction (QAEC) is presented. First, the design rules are specified and then a searching algorithm is developed to find the codes that comply with those rules. The H matrices of the 3-bit BEC with QAEC obtained are presented. They do not require additional parity check bits compared with a 3-bit BEC code. By applying the new algorithm to previous 3-bit BEC codes, the performance of 3-bit BEC is also remarkably improved. The encoding and decoding procedure of the proposed codes is illustrated with an example. Then, the encoders and decoders are implemented using a 65-nm library and the results show that our codes have moderate total area and delay overhead to achieve the correction ability extension.

SOFTWARE IMPLEMENTATION:

  • Modelsim
  • Xilinx 14.2

EXISTING SYSTEM:

Reliability is an important requirement for space applications. Memories as the data storing components play a significant role in the electronic systems. They are widely used in the system on a chip and application-specific integrated circuits. In these applications, memories

Fig. 1. Memory cell area of different technology (cell area shape is simplified to a square, and Length is the length of side

account for a large portion of the circuit area. This makes memories suffer more space radiation than other components. Therefore, the sensitivity to radiation of memories has become a critical issue to ensure the reliability of electronic systems. In modern static random access memories (SRAMs), radiation-induced soft errors in the form of the single event upset (SEU) and multiple bit upset (MBU) are two prominent single event effects. As semiconductor technology develops from the submicrometer technology to the ultradeep submicrometer (UDSM) technology, the size of memory cells is smaller and more cells are included in the radius affected by a particle as shown in Fig. 1.

When a particle from a cosmic ray hits the basic memory cell, it generates a radial distribution of electron–hole pairs along the transport track. These generated electron–hole pairs can cause soft errors by changing the values stored in the memory cell leading to data corruption and system failure. For the transistors with a large feature size, a radiation event just affects one memory cell, which means that only the SEU occurs. In this case, the use of single error-correction (SEC)- double error-detection (DED) codes  is enough to protect the memory from radiation effects

As the feature size enters into DSM range, the critical charge keeps decreasing and the area of the memory cell scales down for each successive technology node. This makes more memory cells affected by a particle hit as shown in Fig. 2. For the CMOS bulk technology, with the cell-to-cell spacing decreasing, the electron–hole pairs generated in the substrate can diffuse to nearby cells and induce MBUs .

Fig. 2. Schematic description of memory cells included in the radiation effect with variation of the technology node.

This compares with the FDSOI technology, which isolates transistors and limits the multicollection mechanism. Therefore, the multicollection mechanism is more prominent for a bulk technology, and the MBU probability is higher. Although multiple bit error-correction codes (ECCs) can correct multiple bit errors in any error patterns not limited to the adjacent bits, the complexity of the decoding process and the limitation of the code block size limit their use. Meanwhile, from the generation principle of MBUs , the type of the MBUs depends on the initial angle of incidence and scattering angle of the secondary particles. Based on this, adjacent bit errors are dominant error patterns among the multiple bit errors. Therefore, adjacent bits correction ECCs become popular in memory-hardened designs. Many codes are proposed, and the capability of adjacent bits correction mainly focuses on the double adjacent error correction (DAEC), triple adjacent error correction (TAEC), and 3-bit burst error correction (BEC). An alternative to codes that can correct adjacent errors is to use an SEC or SEC-DED code combined with an interleaving of the memory cells. Interleaving ensures that cells that belong to the same logical word are placed physically apart. This means that an error on multiple adjacent cells affects multiple words each having only one bit error that can be corrected by an SEC code. As noted in previous studies, interleaving makes the interconnections and routing of the memory more complex and it will lead to an increase area and power consumption or limitations in the aspect ratio. Therefore, whether it is better to use SEC plus interleaving or a code that can correct adjacent errors will be design-dependent and both alternatives are of interest

As the technology comes to the UDSM, the area of the memory cell keeps further decreasing and even memories having atomic-dimension transistors appear. The ionization range of ions with the order of magnitude in micrometer can include more memory cells in the word-line direction as shown in Fig. 2 than the three bits previously considered. This means that the SEC-DAEC-TAEC codes may not be effective to ensure the memory reliability. Codes with more advanced correction ability are demanded. For example, codes designed with low redundancy for SEC-DAEC-TAEC and 3-bit BEC are presented. Therefore, extending the correction ability to quadruple adjacent bit errors would be of interest, especially if it can be done without adding extra parity bits.

In this paper, we present an improvement of 3-bit BEC codes to also provide quadruple adjacent error correction (QAEC). The code design technique for the QAEC with low redundancy is specified from two aspects: 1) error space satisfiability; and 2) unique syndrome satisfiability. Codes with QAEC for 16, 32, and 64 data bits are presented. From the view of the integrated circuits design, two criteria have been used to optimize the decoder complexity and decoder delay at the ECCs level: 1) minimizing the total number of ones in the parity check matrix and 2) minimizing the number of ones in the heaviest row of the parity check matrix. Additionally, based on the traditional recursive backtracing algorithm, an algorithm with the function of weight restriction and recording the past procedure is developed. The new algorithm not only reduces the cost of program run time, but also remarkably improves the performance of previous 3-bit BEC codes. The encoders and decoders for the QAEC codes are implemented in Verilog hardware description language (HDL). Area overhead and delay overhead are obtained by using a TSMC bulk 65-nm library. Compared with the previous 3-bit BEC codes, the area and delay overhead is moderate to achieve the correction ability extension.

DISADVANTAGES:

  • Not reliable in operation
  • Performance of 3-bit BEC is not amended.

PROPOSED SYSTEM:

Searching algorithms and tool development 

In this section, an algorithm is proposed to solve the Boolean satisfiability problem based on the discussion in the former section. Based on the algorithm, a code optimization tool is developed to obtain the target H matrix with custom optimization restrictions. The introduction of the algorithm is divided into two subsections. In the basic part of the algorithm is introduced to find the solutions meeting the requirement of the Boolean satisfiability. Based on the basic part, the method with column weight restriction is designed to force the optimization process to use as few ones as possible, thus optimizing the total number of ones in the matrix and the number of ones in the heaviest row. This optimized version of the algorithm has been used to obtain all the codes presented in this paper.

Basic Part of Code Design Algorithm

 In order to construct the expected codes, the first step is to ensure the number of the check bits. The number of the check bits is seven for codes with 16 data bits, eight for codes with 32 data bits, and nine for codes with 64 data bits.

The main idea of the algorithm is based on the recursive backtracing algorithm. At first, an identity matrix with block size (n − k) is constructed as the initial matrix, and the corresponding syndromes of the error patterns are added to the syndrome set. Then, a column vector selected from Fig. 3. Flow of code design algorithm. the 2n−k − 1 column candidates is added to the right side of the initial matrix. This process is defined as columnadded action. Meanwhile, the new syndromes which belong to the new added column are calculated. If none of new syndromes is equal to the elements in a syndrome set, the column-added action is successful and the corresponding new syndromes are added into the syndrome set. The base-matrix is updated to the previous matrix with the added column. Otherwise, the column-added action fails and another new column from the candidates is selected. If all the candidates are tried and the column-added action still fails, one column from the right side of previous matrix and the corresponding syndromes are reduced from the base-matrix and the syndrome set, respectively. Then, the algorithm continues the columnadded action until the matrix dimension reaches the expected value. The code design algorithm flow is shown in Fig. 3.

Normally, the recursive backtracing algorithm demands a large amount of computing resources and computing time. In order to accelerate the computing speed of the algorithm operation, firstly, we adopt the decimal operation instead of the matrix operation by conversing the column vectors into decimal numbers. Even so, the algorithm completing the execution of all conditions is not possible. In general, if the code we expect exists, it is easy to obtain the first solution. With different optimization criteria, the algorithm can get better solutions. However, searching the best solution requires the complete result of the whole searching process, which is in most cases, unfeasible with today’s computing resources. Therefore, it is more practical to use the best result obtained in a reasonable computation time. To be consistent with , that time was set to one week for all the results presented in this paper. Fig. 4. Flow of algorithm with column weight restriction and past procedure record is shown below

it can be observed that the new algorithms are able to find better solutions than the existing algorithms such as the one used in . Therefore, they can be applied for the finding process of the QAEC codes. The solutions found for QAEC codes are presented  in the paper.

ADVANTAGES:

  • Reliable in operation
  • Performance of 3-bit BEC is improved.

 

REFERENCES:

Jiaqiang Li , Student Member, IEEE, Pedro Reviriego, Senior Member, IEEE, Liyi Xiao, Member, IEEE,Costas Argyrides, Senior Member, IEEE, and Jie Li, “Extending 3-bit Burst Error-Correction Codes WithQuadruple Adjacent Error Correction”, IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 26, NO. 2, FEBRUARY 2018.

Spatially Adaptive Block-Based Super-Resolution

Spatially Adaptive Block-Based Super-Resolution

ABSTRACT:

Super-resolution technology provides an effectiveway to increase image resolution by incorporating additionalinformation from successive input images or training samples.Various super-resolution algorithms have been proposed basedon different assumptions, and their relative performances candiffer in regions of different characteristics within a single image.Based on this observation, an adaptive algorithm is proposedin this paper to integrate a higher level image classificationtask and a lower level super-resolution process, in which weincorporate reconstruction-based super-resolution algorithms,single-image enhancement, and image/video classification intoa single comprehensive framework. The target high-resolutionimage plane is divided into adaptive-sized blocks, and differentsuitable super-resolution algorithms are automatically selected forthe blocks. Then, a deblocking process is applied to reduce blockedge artifacts. A new benchmark is also utilized to measure theperformance of super-resolution algorithms. Experimental resultswith real-life videos indicate encouraging improvements with ourmethod.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram :1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :MATLAB
  • Tool : MATLAB R2013A

REFERENCE:

Heng Su, Liang Tang, Ying Wu, Senior Member, IEEE, Daniel Tretter, and Jie Zhou, Senior Member, IEEE, “Spatially Adaptive Block-Based Super-Resolution”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 3, MARCH 2012.

Sparse Color Interest Points for Image Retrieval and Object Categorization

Sparse Color Interest Points for Image Retrieval and Object Categorization

ABSTRACT:

Interest point detection is an important research areain the field of image processing and computer vision. In particular,image retrieval and object categorization heavily rely on interestpoint detection from which local image descriptors are computedfor image matching. In general, interest points are based on luminance,and color has been largely ignored. However, the use of colorincreases the distinctiveness of interest points. The use of colormay therefore provide selective search reducing the total numberof interest points used for image matching. This paper proposescolor interest points for sparse image representation. To reduce thesensitivity to varying imaging conditions, light-invariant interestpoints are introduced. Color statistics based on occurrence probabilitylead to color boosted points, which are obtained throughsaliency-based feature selection. Furthermore, a principal componentanalysis-based scale selectionmethod is proposed, which givesa robust scale estimation per interest point. From large-scale experiments,it is shown that the proposed color interest point detectorhas higher repeatability than a luminance-based one. Furthermore,in the context of image retrieval, a reduced and predictablenumber of color features show an increase in performancecompared to state-of-the-art interest points. Finally, in the contextof object recognition, for the Pascal VOC 2007 challenge, ourmethod gives comparable performance to state-of-the-artmethodsusing only a small fraction of the features, reducing the computingtime considerably.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram :1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :
  • Tool : MATLAB R2013A

REFERENCE:

Julian Stöttinger, Allan Hanbury, Nicu Sebe, Senior Member, IEEE, and Theo Gevers, Member, IEEE, “Sparse Color Interest Points for ImageRetrieval and Object Categorization”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 5, MAY 2012.

Sharpness Enhancement of Stereo Images Using Binocular Just-Noticeable Difference

Sharpness Enhancement of Stereo Images Using Binocular Just-Noticeable Difference

ABSTRACT:

In this paper, we propose a new sharpness enhancementalgorithm for stereo images. Although the stereo image andits applications are becoming increasingly prevalent, there hasbeen very limited research on specialized image enhancementsolutions for stereo images. Recently, a binocular just-noticeable-difference (BJND) model that describes the sensitivity of thehuman visual system to luminance changes in stereo images hasbeen presented. We introduce a novel application of the BJNDmodel for the sharpness enhancement of stereo images. To thisend, an overenhancement problem in the sharpness enhancementof stereo images is newly addressed, and an efficient solution forreducing the overenhancement is proposed. The solution is foundwithin an optimization framework with additional constraintterms to suppress the unnecessary increase in luminance values.In addition, the reliability of the BJND model is taken into accountby estimating the accuracy of stereo matching. Experimentalresults demonstrate that the proposed algorithm can providesharpness-enhanced stereo images without producing excessivedistortion.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram : 1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :
  • Tool : MATLAB R2013A

REFERENCE:

Seung-Won Jung, Jae-Yun Jeong, and Sung-Jea Ko, Senior Member, IEEE, “Sharpness Enhancement of Stereo Images UsingBinocular Just-Noticeable Difference”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 3, MARCH 2012.

Semi-supervised Biased Maximum Margin Analysis for Interactive Image Retrieval

Semi-supervised Biased Maximum Margin Analysis for Interactive Image Retrieval

ABSTRACT:

With many potential practical applications, content-based image retrieval (CBIR) has attracted substantial attention during the past few years. A variety of relevance feedback (RF) schemes have been developed as a powerful tool to bridge the semantic gap between low-level visual features and high-level semantic concepts, and thus to improve the performance of CBIR systems. Among various RF approaches, support-vector-machine (SVM)-based RF is one of the most popular techniques in CBIR. Despite the success, directly using SVM as an RF scheme has two main drawbacks. First, it treats the positive and negative feedbacks equally, which is not appropriate since the two groups of training feedbacks have distinct properties. Second, most of the SVM-based RF techniques do not take into account the unlabeled samples, although they are very helpful in constructing a good classifier. To explore solutions to overcome these two drawbacks, in this paper, we propose a biased maximum margin analysis (BMMA) and a semisupervised BMMA (SemiBMMA) for integrating the distinct properties of feedbacks and utilizing the information of unlabeled samples for SVM-based RF schemes. The BMMA differentiates positive feedbacks from negative ones based on local analysis, whereas the SemiBMMA can effectively integrate information of unlabeled samples by introducing a Laplacian regularizer to the BMMA. We formally formulate this problem into a general subspace learning task and then propose an automatic approach of determining the dimensionality of the embedded subspace for RF. Extensive experiments on a large real-world image database demonstrate that the proposed scheme combined with the SVM RF can significantly improve the performance of CBIR systems.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

SYSTEM ARCHITECTURE:

EXISTING SYSTEM:

A variety of relevance feedback (RF) schemes have been developed as a powerful tool to bridge the semantic gap between low-level visual features and high-level semantic concepts, and thus to improve the performance of CBIR systems. Among various RF approaches, support-vector-machine (SVM)-based RF is one of the most popular techniques in CBIR.

DISADVANTAGES OF EXISTING SYSTEM:

Despite the success, directly using SVM as an RF scheme has two main drawbacks. First, it treats the positive and negative feedbacks equally, which is not appropriate since the two groups of training feedbacks have distinct properties. Second, most of the SVM-based RF techniques do not take into account the unlabeled samples, although they are very helpful in constructing a good classifier.

The low-level features captured from the images may not accurately characterize the high-level semantic concepts

PROPOSED SYSTEM:

The proposed scheme is mainly based on the following:

1) The effectiveness of treating positive examples and negative examples unequally

2) The significance of the optimal subspace or feature subset in interactive CBIR;

3) The success of graph embedding in characterizing intrinsic geometric properties of the data set in high-dimensional space

4) The convenience of the graph-embedding framework in constructing semi-supervised learning techniques.

ADVANTAGES OF PROPOSED SYSTEM:

To explore solutions to these two aforementioned problems in the current technology, we propose a biased maximum margin analysis (BMMA)and a semisupervised BMMA(SemiBMMA) for the traditional SVM RF schemes, based on the graph-embedding framework With the incorporation of BMMA, labeled positive feedbacks are mapped as close as possible, whereas labeled negative feedbacks are separated from labeled positive feedbacks by a maximum margin in the reduced subspace.

The traditional SVM combined with BMMA can better model the RF process and reduce the performance degradation caused by distinct properties of the two groups of feedbacks. The SemiBMMA can incorporate the information of unlabeled samples into the RF and effectively alleviate the over fitting problem caused by the small size of labeled training samples.

To show the effectiveness of the proposed scheme combined with the SVM RF, we will compare it with the traditional SVM RF and some other relevant existing techniques for RF on a real-world image collection.

Experimental results demonstrate that the proposed scheme can significantly improve the performance of the SVMRF for image retrieval.

MODULES:

  • Training and Indexing Module
  • Graph-Embedding Framework
  • Features Extraction Based on Different Methods
  • Visualization of the Retrieval Results
  • Experiments on a Large-Scale Image Database:
  • Experiments on a Small-Scale Image Database

MODULES DESCRIPTION:

Training and Indexing Module

In this module, we index and train the system. Indexing the whole set of images is done for making the search efficient and time consuming. If we don’t index the system, then it takes more time as it searches the whole disk space..Indexing is done using an implementation of the Document Builder Interface. A simple approach is to use the Document Builder Factory, which creates Document Builder instances for all available features as well as popular combinations of features (e.g. all JPEG features or all avail-able features).  In a content based image retrieval system, target images are sorted by feature similarities with respect to the query (CBIR).In this indexing, we propose to classification of feature set obtained from the CBIR.First, it randomly selects k of the objects, each of which initially represents a cluster mean or center. For each of the remaining objects, an object is assigned to the cluster to which it is the most similar, based on the distance between the object and the cluster mean. It then computes the new mean for each cluster.

Graph-Embedding Framework

In order to describe our proposed approach clearly, we first review the graph-embedding framework Generally, for a classification problem, the sample set can be represented as matrix , where indicates the total number of the samples and is the feature dimensionality. Let be an undirected similarity graph, which is called an intrinsic graph, with vertices set and similarity matrix. The similarity matrix is real and symmetric, and measures the similarity between a pair of vertices; can be formed using various similarity criteria. The corresponding diagonal matrix and the Laplacian matrix of graph can G. Graph embedding of graph is defined as an algorithm to determine the low-dimensional vector representations of the vertex set, where is lower than for dimensionality. The column vector is the embedding vector for vertex, which preserves the similarities between pairs of vertices in the original high-dimensional space. Then, in order to characterize the difference between pairs of vertices in the original high-dimensional space, a penalty graph is also defined, where vertices are the same as those of, but the edge weight matrix corresponds to the similarity characteristics that are to be suppressed in the low-dimensional feature space. For a dimensionality reduction problem, direct graph embedding requires an intrinsic graph, whereas a penalty graph is not a necessary input.

Features Extraction Based on Different Methods

Six experiments are conducted for comparing the BMMA with the traditional LDA, the BDA method, and a graph-embedding approach, i.e., MFA, in finding the most discriminative directions. We plot the directions that correspond to the largest Eigen value of the decomposed matrices for LDA, BDA, MFA, and BMMA, respectively. From these examples, we can clearly notice that LDA can find the best discriminative direction when the data from each class are distributed as Gaussian with similar covariance matrices Biased toward the positive samples, BDA can find the direction that the positive samples are well separated with the negative samples when the positive samples have a Gaussian distribution, but it may also confuse when the distribution of the positive samples is more complicated. Biased toward positive samples, the BMMA method can find the most discriminative direction for all the six experiments based on local analysis, since it does not make any assumptions on the distributions of the positive and negative samples. It should be noted that BMMA is a linear method, and therefore, we only gave the comparison results of the aforementioned linear methods.

Visualization of the Retrieval Results

In the previous subsections, we have presented some statistically quantitative results of the proposed scheme. Here, we show the visualization of retrieval results.

In experiments, we randomly select some images (e.g., bobsled, cloud, cat, and car) as the queries and perform the RF process based on the ground truth. For each query image, we do four RF iterations. For each RF iteration, we randomly select some relevant and irrelevant images as positive and negative feedbacks from the first screen, which contains 20 images in total. The number of selected positive and negative feedbacks is about 4, respectively. We choose them according to the ground truth of the images, i.e., whether they share the same concept with the query image or not. The query images are given as the first image of each row. We show the top one to ten images of initial results without feedback and Semi BMMA SVM after four feedback iterations, respectively, and incorrect results are highlighted by green boxes. From the results, we can notice that our proposed scheme can significantly improve the performance of the system. For the first, second, and fourth query images, our system produces ten relevant images out of the top ten retrieved images. For the third query image, our system produces nine relevant images out of the top ten retrieved images. Therefore, Semi BMMA SVM can effectively detect the homogeneous concept shared by the positive samples and hence improve the performance of the retrieval system.

Experiments on a Large-Scale Image Database:

Here, we evaluate the performance of the proposed scheme on a real-world image database. We use precision–scope curve, precision rate, and standard deviation to evaluate the effectiveness of the image retrieval algorithms. The scope is specified by number of top-ranked images presented to the user. The precision is the major evaluation criterion, which evaluates the effectiveness of the algorithms. The precision–scope curve describes the precision with various scopes and can give the overall performance evaluation of the approaches. The precision rate is the ratio of the number of relevant images retrieved to the top retrieved images, which emphasizes the precision at a particular value of scope. Standard deviation describes the stability of different algorithms. Therefore, the precision evaluates the effectiveness of a given algorithm, and the corresponding standard deviation evaluates the robustness of the algorithm. We designed a slightly different feedback scheme to model the real world retrieval process. In a real image retrieval system, a query image is usually not in the image database. To simulate such an environment, we use fivefold cross validation to evaluate the algorithms. More precisely, we divide the whole image database into five subsets of equal size. Thus, there are 20% images per category in each subset. At each run of cross validation, one subset is selected as the query set, and the other four subsets are used as the database for retrieval. Then, 400 query samples are randomly selected from the query subset, and the RF is automatically implemented by the system. For each query image, the system retrieves and ranks the images in the database, and nine RF iterations are automatically executed.

Experiments on a Small-Scale Image Database

In order to show how efficient the proposed BMMA combined with SVM is in dealing with the asymmetric properties of feedback samples, the first evaluation experiment is executed on a small-scale database, which includes 3899 images with 30 different categories. We use all 3899 images in 30 categories as queries. Some example categories used in experiments. To avoid the potential problem caused by the asymmetric amount of positive and negative feedbacks, we selected an equal number of positive and negative feedbacks here. In practice, the first five query-relevant images and first five irrelevant images in the top 20 retrieved images in the previous iterations were automatically selected as positive and negative feedbacks, respectively.

HARDWARE REQUIREMENTS

  • PROCESSOR :  PENTIUM 4 CPU 2.40GHZ
  • RAM :   128 MB
  • HARD DISK :    40 GB
  • KEYBOARD    :    STANDARD
  • MONITOR     :    15”

SOFTWARE REQUIREMENTS

  • FRONT END :     MATLAB
  • TOOL :  MATLAB TOOLBOX
  • OPERATING SYSTEM :   WINDOWS XP/7
  • DOCUMENTATION :   MS-OFFICE 2007

REFERENCE:

Lining Zhang, Student Member, IEEE, LipoWang, Senior Member, IEEE, and Weisi Lin, Senior Member, IEEE, “Semisupervised Biased Maximum Margin Analysis for Interactive Image Retrieval”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 4, APRIL 2012.

A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks

A Privacy-Preserving Location Monitoring System forWireless Sensor Networks

ABSTRACT:-

Monitoring personal locations with a potentially untrusted server poses privacy threats to the monitored individuals. Tothis end, we propose a privacy-preserving location monitoring system for wireless sensor networks. In our system, we design two innetworklocation anonymization algorithms, namely, resource- and quality-aware algorithms, that aim to enable the system to providehigh quality location monitoring services for system users, while preserving personal location privacy. Both algorithms rely on the wellestablished k-anonymity privacy concept, that is, a person is indistinguishable among k persons, to enable trusted sensor nodes to

provide the aggregate location information of monitored persons for our system. Each aggregate location is in a form of a monitoredarea A along with the number of monitored persons residing in A, where A contains at least k persons. The resource-aware algorithmaims to minimize communication and computational cost, while the quality-aware algorithm aims to maximize the accuracy of theaggregate locations by minimizing their monitored areas. To utilize the aggregate location information to provide location monitoringservices, we use a spatial histogram approach that estimates the distribution of the monitored persons based on the gathered aggregatelocation information. Then the estimated distribution is used to provide location monitoring services through answering range queries.

We evaluate our system through simulated experiments. The results show that our system provides high quality location monitoringservices for system users and guarantees the location privacy of the monitored persons.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

SYSTEM ARCHITECTURE

ALGORITHM

The Resource-Aware Algorithm

EXISTING SYSTEM

Existing locationmonitoring systems. In an identity-sensor location monitoring

System, since each sensor node reports the exactlocation information of each 0monitored object to theserver, the adversary can pinpoint each object’s exact location.On the other hand, in a counting-sensor locationmonitoring system, each sensor node reports the numberof objects in its sensing area to the server. The adversarycan map the monitored areas of the sensor nodes to thesystem layout. If the object count of a monitored area isvery small or equal to one,

PROPOSED SYSTEM

This paper proposes a privacy-preserving locationmonitoring system for wireless sensor networks to providemonitoring services. Our system relies on the wellestablished k-anonymity privacy concept, which requireseach person is indistinguishable among k persons. In oursystem, each sensor node blurs its sensing area into acloaked area, in which at least k persons are residing. Eachsensor node reports only aggregate location information,

We proposetwo in-network aggregate location anonymization algorithms, namely, resource- and quality-aware algorithms.Both algorithms require the sensor nodes to collaboratewith each other to blur their sensing areas into cloakedareas, such that each cloaked area contains at least kpersons to constitute a k-anonymous cloaked area. Theresource-aware algorithm aims to minimize communication

and computational cost, while the quality-awarealgorithm aims to minimize the size of the cloaked areas,in order to maximize the accuracy of the aggregatelocations reported to the server.

MODULES

  1. WSN Location Monitoring Module

The location monitoring system using identity sensors,the sensor nodes report the exact location information ofthe monitored persons to the server; thus using identitysensors immediately poses a major privacy breach. To tackle such a privacy breach, the concept of aggregatelocation information, that is, a collection of location datarelating to a group or category of persons from whichindividual identities have been removed , has beensuggested as an effective approach to preserve locationprivacy . Although the counting sensors by natureprovide aggregate location information, they wouldalso pose privacy breaches.

  1. Aggregate locations Module

We design two in-network location anonymization algorithms,namely, resource- and quality-aware algorithms that preserve personal location privacy, while enablingthe system to provide location monitoring services. Bothalgorithms rely on the well established k-anonymity privacyconcept that requires a person is indistinguishableamong k persons. In our system, sensor nodes executeour location anonymization algorithms to provide k-anonymous aggregate locations, in which each aggregatelocation is a cloaked area A

  1. Mapped Location monitoring Module

Sensor nodes.

Each sensor node is responsible for determining the number of objects in its sensing area, blurring its sensing area into a cloaked area A, which includes at least k objects, and reporting A with the number of objects located in A as aggregate location information to the server. We do not have any assumption about the network topology, as our system only requires a communication path from each sensor node to the server through a distributed tree . Each sensor node is also aware of its location and sensing area.

Server.

The server is responsible for collecting the aggregatelocations reported from the sensor nodes, usinga spatial histogram to estimate the distribution of themonitored objects, and answering range queries basedon the estimated object distribution. Furthermore, theadministrator can change the anonymized level k of thesystem at anytime by disseminating a message with anew value of k to all the sensor nodes.

System users.

Authenticated administrators and userscan issue range queries to our system through either theserver or the sensor nodes, as depicted in Above System Architecture figure. Theserver uses the spatial histogram to answer their queries.

  1. Minimum bounding rectangle (MBR)

We find the minimum bounding rectangle (MBR) of the sensing area of A. It is important to note that the sensing area can be in any polygon or irregular shape.

SOFTWARE REQUIREMENTS:

HARDWARE REQUIREMENT:

  • Minimum 1.1 GHz PROCESSOR should be on the computer.
  • 128 MB RAM.
  • 20 GB HDD.
  • 44 MB FDD.
  • 52x CD-ROM Drive.
  • MONITORS at 800×600 minimum resolution at 256 colors minimum.
  • I/O, One or two button mouse and standard 101-key keyboard.

SOFTWARE REQUIREMENT:

  • Operating System : Windows 95/98/2000/NT4.0.
  • Technology                    :  JAVA, JFC(Swing)
  • Development IDE           :  Eclipse 3.x

 

Data Leakage Detection

DATA LEAKAGE DETECTION

ABSTRACT:

A data distributor has given sensitive data to a set of supposedly trusted agents (third parties). Some of the data is leaked and found in an unauthorized place (e.g., on the web or somebody’s laptop). The distributor must assess the likelihood that the leaked data came from one or more agents, as opposed to having been independently gathered by other means. We propose data allocation strategies (across the agents) that improve the probability of identifying leakages. These methods do not rely on alterations of the released data (e.g., watermarks). In some cases we can also inject “realistic but fake” data records to further improve our chances of detecting leakage and identifying the guilty party.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

EXISTING SYSTEM:

  • Traditionally, leakage detection is handled by watermarking, e.g., a unique code is embedded in each distributed copy.
  • If that copy is later discovered in the hands of an unauthorized party, the leaker can be identified.
  • Disadvantages of Existing Systems:
  • Watermarks can be very useful in some cases, but again, involve some modification of the original data. Furthermore, watermarks can sometimes be destroyed if the data recipient is malicious. g. A hospital may give patient records to researchers who will devise new treatments.
  • Similarly, a company may have partnerships with other companies that require sharing customer data. Another enterprise may outsource its data processing, so data must be given to various other companies. We call the owner of the data the distributor and the supposedly trusted third parties the agents.

PROPOSED SYSTEM:

  • Our goal is to detect when the distributor’s sensitive data has been leaked by agents, and if possible to identify the agent that leaked the data.
  • Perturbation is a very useful technique where the data is modified and made “less sensitive” before being handed to agents.
  • We develop unobtrusive techniques for detecting leakage of a set of objects or records.
  • We develop a model for assessing the “guilt” of agents.
  • We also present algorithms for distributing objects to agents, in a way that improves our chances of identifying a leaker.
  • Finally, we also consider the option of adding “fake” objects to the distributed set. Such objects do not correspond to real entities but appear realistic to the agents.
  • In a sense, the fake objects acts as a type of watermark for the entire set, without modifying any individual members. If it turns out an agent was given one or more fake objects that were leaked, then the distributor can be more confident that agent was guilty.

Problem Setup and Notation:

A distributor owns a set T={t1,…,tm}of valuable data objects. The distributor wants to share some of the objects with a set of agents U1,U2,…Un, but does not wish the objects be leaked to other third parties. The objects in T could be of any type and size, e.g., they could be tuples in a relation, or relations in a database. An agent Ui receives a subset of objects, determined either by a sample request or an explicit request:

  1. Sample request
  2. Explicit request

Guilt Model Analysis:

Our model parameters interact and to check if the interactions match our intuition, in this section we study two simple scenarios as Impact of Probability p and Impact of Overlap between Ri and S. In each scenario we have a target that has obtained all the distributor’s objects, i.e., T = S.

MODULES:

  1. Data Allocation Module:

The main focus of our project is the data allocation problem as how can the distributor “intelligently” give data to agents in order to improve the chances of detecting a guilty agent.

  1. Fake Object Module:

Fake objects are objects generated by the distributor in order to increase the chances of detecting agents that leak data. The distributor may be able to add fake objects to the distributed data in order to improve his effectiveness in detecting guilty agents. Our use of fake objects is inspired by the use of “trace” records in mailing lists.

  1. Optimization Module:

The Optimization Module is the distributor’s data allocation to agents has one constraint and one objective. The distributor’s constraint is to satisfy agents’ requests, by providing them with the number of objects they request or with all available objects that satisfy their conditions. His objective is to be able to detect an agent who leaks any portion of his data.

  1. Data Distributor:

A data distributor has given sensitive data to a set of supposedly trusted agents (third parties). Some of the data is leaked and found in an unauthorized place (e.g., on the web or somebody’s laptop). The distributor must assess the likelihood that the leaked data came from one or more agents, as opposed to having been independently gathered by other means.

Hardware Required:

  • System : Pentium IV 2.4 GHz
  • Hard Disk : 40 GB
  • Floppy Drive : 44 MB
  • Monitor : 15 VGA colour
  • Mouse :Logitech
  • Keyboard : 110 keys enhanced.
  • RAM : 256 MB

Software Required:

  • O/S :         Windows XP.
  • Front End : JAVA/JSP
  • Data Base : MYSQL

REFERENCE:

Panagiotis Papadimitriou, and Hector Garcia-Molina, “Data Leakage Detection”, IEEE Transactions on Knowledge and Data Engineering, Vol. 23, NO.1, January 2011.

Supporting Efficient and Scalable Multicasting Over Mobile Ad Hoc Networks

Supporting Efficient and Scalable Multicasting Over Mobile Ad Hoc Networks

Abstract:-

Group communications are important in Mobile Ad hoc Networks (MANET). Multicast is an efficient method for implementing group communications. However, it is challenging to implement efficient and scalable multicast in MANET due to the difficulty in group membership management and multicast packet forwarding over a dynamic topology. We propose a novel Efficient Geographic Multicast Protocol (EGMP). EGMP uses a virtual-zone-based structure to implement scalable and efficient group membership management. A network-wide zone-based bi-directional tree is constructed to achieve more efficient membership management and multicast delivery. The position information is used to guide the zone structure building, multicast tree construction and multicast packet forwarding, which efficiently reduces the overhead for route searching and tree structure maintenance. Several strategies have been proposed to further improve the efficiency of the protocol, for example, introducing the concept of zone depth for building an optimal tree structure and integrating the location search of group members with the hierarchical group membership management. Finally, we design a scheme to handle empty zone problem faced by most routing protocols using a zone structure. The scalability and the efficiency of EGMP are evaluated through simulations and quantitative analysis. Our simulation results demonstrate that EGMP has high packet delivery ratio, and low control overhead and multicast group joining delay under all test scenarios, and is scalable to both group size and network size. Compared to Scalable Position-Based Multicast (SPBM), EGMP has significantly lower control overhead, data transmission overhead, and multicast group joining delay.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System:-

The existing geographic routing protocols generally assume mobile nodes are aware of their own positions through certain positioning system (e.g., GPS), and a source can obtain the destination position through some type of location service. In, an intermediate node makes its forwarding decisions based on the destination position inserted in the packet header by the source and the positions of its one-hop neighbors learned from the periodic beaconing of the neighbors. By default, the packets are greedily forwarded to the neighbor that allows for the greatest geographic progress to the destination. When no such a neighbor exists, perimeter forwarding is used to recover from the local void, where a packet traverses the face of the planarized local topology sub graph by applying the right-hand rule until the greedy forwarding can be resumed. 

Proposed System:-

ODMRP are proposed to enhance the robustness with the use of redundant paths between the source and the destination pair’s scalability due to the overhead incurred for route searching, group membership management, and creation and maintenance of the tree/mesh structure over the dynamic MANET.

For MANET uni-cast routing, geographic routing protocols have been proposed in recent years for more scalable and robust packet transmissions we proposed an efficient and robust geographic multicast protocol for MANET. In this paper, we further introduce zone-supported geographic forwarding to reduce the routing failure, and provide mechanism to handle zone partitioning. In addition, we introduce a path optimization process to handle multiple paths, and provide a detailed cost analysis to demonstrate the scalability of the proposed routing scheme.

MODULES:

  1. Efficient Geographic Multicast Protocol
  2. Multicast Tree Construction
  3. Multicast group join
  4. Packet sending from the source
  5. Multicast data forwarding
  6. Multicast Route Maintenance and Optimization

MODULE DESCRIPTION:-

  1. Efficient Geographic Multicast Protocol

 EGMP supports scalable and reliable membership management and multicast forwarding through a two-tier virtual zone- based structure. At the lower layer, in reference to a pre-determined virtual origin, the nodes in the network self-organize themselves into a set of zones, and a leader is elected in a zone to manage the local group membership. At the upper layer, the leader serves as a representative for its zone to join or leave a multicast group as required. As a result, a network-wide zone-based multicast tree is built. For efficient and reliable management and transmissions, location information will be integrated with the design and used to guide the zone construction, group membership management, multicast tree construction and maintenance, and packet forwarding.

  1. Multicast Tree Construction 

We present the multicast tree creation and maintenance schemes. In EGMP, instead of connecting each group member directly to the tree, the tree is formed in the granularity of zone with the guidance of location information, which significantly reduces the tree management overhead. With a destination location, a control message can be transmitted immediately without incurring a high overhead and delay to find the path first, which enables quick group joining and leaving.

  1. Multicast group join 

When a node M wants to join the multicast group G, if it is not a leader node, it sends a JOIN REQ(M; PosM; G; fMoldg) message to its zLdr, carrying its address, position, and group to join. The address of the old group leader Mold is an option used when there is a leader handoff and a new leader sends an updated JOIN REQ message to its upstream zone. If M did not receive the NEW SESSION message or it just joined the network,

  1. Packet sending from the source 

After the multicast tree is constructed, all the sources of the group could send packets to the tree and the packets will be forwarded along the tree. In most tree-based multicast protocols, a data source needs to send the packets initially to the root of the tree. If this scheme is used and node 5 in Fig. 1 is a source, node 5 needs to uni-cast the packets initially to root zone (2, 2). The sending of packets to the root would introduce extra delay especially when a source is far away from the root. Instead, EGMP assumes a bi-directional tree- based forwarding strategy, with which the multicast packets can flow not only from an upstream node/zone down to its downstream nodes/zones, but also from a downstream node/zone up to its upstream node/zone.

  1. Multicast data forwarding

Maintain the multicast table, and the member zones normally cannot be reached within one hop from the source. When a node N has a multicast

Packet to forward to a list of destinations (D1; D2; D3; :), it decides the next hop node towards each destination (for a zone, its center is used) using the geographic forwarding strategy. After deciding the next hop nodes, N inserts the list of next hop nodes and the destinations associated with each next hop node in the packet header. An example list is (N1: D1; D3; N2: D2; :), where N1 is the next hop node for the destinations D1 and D3, and N2 is the next hop node for D2. Then N broadcasts the packet promiscuously (for reliability and efficiency). Upon receiving the packet, a neighbor node will keep the packet if it is one of the next hop nodes or destinations, and drop the packet otherwise. When the node is associated with some downstream destinations, it will continue forwarding packets similarly as done by node N.

  1. Multicast Route Maintenance and Optimization 

In the zone structure, due to the movement of nodes between different zones, some zones may become empty. It is critical to handle the empty zone problem in a zone-based protocol. Compared to managing the connections of individual nodes, however, there is a much lower rate of zone membership change and hence a much lower overhead in maintaining the zone-based tree.

When a member node moves to a new zone, it must rejoin the multicast tree through the new leader. When a leader is moving away from its current zone, it must handover its multicast table to the new leader in the zone, so that all the downstream zones and nodes will remain connected to the multicast tree.

System Requirements:

     

Hardware Requirement:

  • Minimum 1.1 GHz PROCESSOR should be on the computer.
  • 128 MB RAM.
  • 20 GB HDD.
  • 44 MB FDD.
  • 52x CD-ROM Drive.
  • MONITORS at 800×600 minimum resolution at 256 colors minimum.
  • I/O, One or two button mouse and standard 101-key keyboard.

 Software Requirement:

  • Operating System :  Windows 95/98/2000/XP
  • Technology                            :  JAVA, JFC(Swing)
  • Development IDE           :  Eclipse 3.x

REFERENCE:

X.Xiang, X.Wang, and Y. Yang, “Supporting Efficient and Scalable Multicasting over Mobile Ad Hoc Networks”, IEEE Transactions on Mobile Computing, Vol. 10, No.4, April 2011.

ProgME: Towards Programmable Network Measurement

ProgME: Towards Programmable Network Measurement 

ABSTRACT:

We present ProgME, a Programmable MEasurement architecture based on a novel concept of flowset – arbitrary set of flows defined according to application requirements and/or traffic conditions. Through a simple flowset composition language, ProgME can incorporate application requirements, adapt itself to circumvent the challenges on scalability posed by the large number of flows, and achieve a better application-perceived accuracy. ProgME can analyze and adapt to traffic statistics in real-time. Using sequential hypothesis test, ProgME can achieve fast and scalable heavy hitter identification.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System:

Traffic measurements provide critical input for a wide range of network management applications, including traffic engineering, accounting, and security analysis. Existing measurement tools collect traffic statistics based on some predetermined, inflexible concept of “flows”. They do not have sufficient built-in intelligence to understand the application requirements or adapt to the traffic conditions. Consequently, they have limited scalability with respect to the number of flows and the heterogeneity of monitoring applications. 

Proposed System:

We present a Programmable MEasurement architecture (ProgME) that can adapt to application requirements and traffic conditions in real time. Below figure shows the major components of ProgME. Our first proposal is to use a versatile definition of flowset – arbitrary set of flows – as the base of traffic statistics collection. In other words, ProgME keeps one counter per flowset. Compared to per-flow traffic statistics, per-flowset statistics enables one to achieve multiple resolutions within a traffic profile. Since flowsets can be defined arbitrarily, they do not necessarily map to the same number of unique flows or traffic volume. Therefore, one can track higher resolution statistics to maintain the desired accuracy for a sub-population of network traffic, while collecting coarse-grained aggregate statistics for the remaining traffic (e.g., through a flowset that catches uninteresting traffic) to reduce total number of counters required. Furthermore, since a flowset can contain arbitrary set of flows, one can construct flowsets that directly reflect the interest of management applications.

Modules:

  1. Flow Set
  2. Collect and Report Statistics
  3. Scalable Flowset-Based Query Answering (FQAE)
  4. Accuracy of FQAE 

Modules Description: 

  1. Flow Set 

Definition of flowset – arbitrary set of flows – as the base of traffic statistics collection. In other words, ProgME keeps one counter per flowset. Compared to per-flow traffic statistics, per-flowset statistics enables one to achieve multiple resolutions within a traffic profile. Since flowsets can be defined arbitrarily, they do not necessarily map to the same number of unique flows or traffic volume. Therefore, one can track higher resolution statistics to maintain the desired accuracy for a sub-population of network traffic, while collecting coarse-grained aggregate statistics for the remaining traffic (e.g., through a flowset that catches uninteresting traffic) to reduce total number of counters required. Furthermore, since a flowset can contain arbitrary set of flows, one can construct flowsets that directly reflect the interest of management applications.

  1. Collect and Report Statistics:

During the measurement process, FQAE performs trafficaware optimization by sorting the order of candidates in the table of matching candidates based on the number of packets observed earlier (TrafficSort). Note that this seemingly simple optimization is possible only because FQAE make flowsets fully disjoint. If flowsets have non-empty intersections, finding the optimal order is NP-complete, and one will have to resolve to heuristics, as some have attempted in the context of packet  Filtering .

  1. Scalable Flowset-Based Query Answering (FQAE):

We propose a scalable Flowset-based Query Answering Engine (FQAE) to support arbitrary user queries. Used in conjunction with sampling,

FQAE can achieve the same accuracy for any given set of queries compared to an ideal flow-based measurement approach, while achieving orders of magnitude cost reduction in terms of memory requirements.

  1. Accuracy of FQAE:

The accuracy of measurement results is of paramount concern for every management application. Existing flow-based measurement tools use average per-flow error as the primary measure of accuracy. If there were no memory limitation and statistics could be maintained for every flow, per-flow statistics could achieve high per-query accuracy under any traffic condition. FQAE achieves the same effect by counting for each query directly.

System Configuration:-

H/W System Configuration:-

  • Processor                                          –    Pentium –III
  • Speed                                      –    1.1 Ghz
  • RAM                                       –    256  MB(min)
  • Hard Disk                                –   20 GB
  • Floppy Drive                           –    1.44 MB
  • Key Board                               –    Standard Windows Keyboard
  • Mouse                                     –    Two or Three Button Mouse
  • Monitor                                   –    SVGA

 S/W System Configuration:-

  • Operating System         :Windows95/98/2000/XP
  • Application Server         :   0/6.X
  • Front End :   HTML, Java, Jsp                            :
  • Server side Script :   Java Server Pages.
  • Database :   Ms-Access

REFERENCE:

Lihua Yuan, Chen-Nee Chuah, and Prasant Mohapatra, “ProgME: Towards Programmable Network Measurement”, IEEE/ACM Transactions on Networking, Vol. 19, No.1, February 2011.

Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks

Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks

Abstract: 

We analyze the delay performance of a multi-hop wireless network in which the routes between source-destination pairs are fixed. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multi-hop nature of the flows and their mutual sharing of the wireless medium. A general set based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample path delay optimal. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. The lower bound analysis provides useful insights into the design and analysis of optimal or nearly optimal scheduling policies.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System: 

A large number of studies on multi-hop wireless networks have been devoted to system stability while maximizing metrics like throughput or utility. These metrics measure the performance of a system over a long time-scale. For a large class of applications such as video or voice over IP, embedded network control and for system design; metrics like delay are of prime importance. The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with singlehop traffic were developed in. However, the analysis is not directly applicable to multi-hop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links. The metric of interest in this paper is the system-wide average delay of a packet from the source to its corresponding destination. We present a new, systematic methodology to obtain a fundamental lower bound on the average packet delay in the system under any scheduling policy. Furthermore, we re-engineer well known scheduling policies to achieve good delay performance viz-a-viz the lower bound. 

Proposed System:            

We analyze a multi-hop wireless network with multiple source-destination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination. For example, a multi-hop wireless network with three flows is shown in Fig. 1. The exogenous arrival processes AI (t), AII (t) and AIII (t) correspond to the number of packets injected in the system at time t. A packet is queued at each node in its path where it waits for an opportunity to be transmitted. Since the transmission medium is shared, concurrent transmissions can interfere with each others’ transmissions. The set of links that do not cause interference with each other can be scheduled simultaneously, and we call them activation vectors (matchings). We do not impose any a priori restriction on the set of allowed activation vectors, i.e., they can characterize any combinatorial interference model. For example, in a K-hop interference model, the links scheduled simultaneously are separated by at least K hops. In the example show in Fig. 1, each link has unit capacity; i.e., at most one packet can be transmitted in a slot. For the above example, we assume a 1-hop interference model.

The delay performance of any scheduling policy is primarily limited by the interference, which causes many bottlenecks to be formed in the network. We demonstrated the use of exclusive sets for the purpose of deriving lower bounds on delay for a wireless network with single hop traffic. We further generalize the typical notion of a bottleneck. In our terminology, we define a (K, X)-bottleneck to be a set of links X such that no more than K of them can simultaneously transmit. Figure 1 shows (1, X) bottlenecks for a network under the 1-hop interference model. In this paper, we develop new analytical techniques that focus on the queuing due to the (K, X)-bottlenecks. One of the techniques, which we call the “reduction technique”, simplifies the analysis of the queuing upstream of a (K, X)-bottleneck to the study of a single queue system with K servers as indicated in the figure. Furthermore, our analysis needs only the exogenous inputs to the system and thereby avoids the need to characterize departure processes on intermediate links in the network. For a large class of input traffic, the lower bound on the expected delay can be computed using only the statistics of the exogenous arrival processes and not their sample paths. To obtain a lower bound on the system wide average queuing delay, we analyze queuing in multiple bottlenecks by relaxing the interference constraints in the system. Our relaxation approach is novel and leads to nontrivial lower bounds.

Theorem:

              For a (K,X)-bottleneck in the system, at any time T ≥ 0, the sum of the queue lengths SX in X, under any scheduling policy is no smaller than that of the reduced system, i.e., QX(T) ≤ SX(T). Proof: We prove the above theorem using the principle of mathematical induction. Base Case: The theorem holds true for T = 0, since the system is initially empty. Induction hypothesis: Assume that the theorem holds at a

time T = t, i.e., QX(t) ≤ SX(t).

Induction Step: The following two cases arise.

Case 1: QX(t) ≥ K

QX(t + 1) = QX(t) − K + AX(t)

≤ SX(t) − K + AX(t)

≤ SX(t) − IX(t) + AX(t)

= SX(t + 1).

Case 2: QX(t) < K.

Using Eq. (III.11), we have the following,

QX(t + 1) = AX(t)

≤ SX(t) − IX(t) + AX(t)

= SX(t + 1).

Hence, the theorem is holds for T = t + 1.

Thus by the principle of mathematical induction, the theorem holds for all T.

Modules: 

1) Multi-hop wireless network module

2) Delay performance of wireless networks

3) Back-Pressure Policy

4) Delay Analysis technique module

5) Design of Delay Efficient Policies module 

Modules Description: 

1) Multi-hop wireless network module

Multi-hop wireless network with multiple source-destination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination.

2) Delay performance of wireless networks 

The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with single hop traffic were developed. However, the analysis is not directly applicable to multi-hop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links.

3) Back-Pressure Policy

The back-pressure policy may lead to large delays since the backlogs are progressively larger from the destination to the source. The packets are routed only from a longer queue to a shorter queue and certain links may have to remain idle until this condition is met. Hence, it is likely that all the queues upstream of a bottleneck will grow long leading to larger delays. A common observation of the optimal policies for the clique and the tandem network is that increasing the priority of packets which are close to the destination reduces the delay.

4) Delay Analysis technique module

The general research on the delay analysis of scheduling policies has progressed in the following main directions:

  • Heavy traffic regime using fluid models:

                                          Fluid models have typically been used to either establish the stability of the system or to study the workload process in the heavy traffic régime. The maximum-pressure policy (similar to the back-pressure policy) minimizes the workload process for a stochastic processing network in the heavy traffic regime when processor splitting is allowed.

  • Stochastic Bounds using Lyapunov drifts: 

This method is developed and is used to derive upper bounds on the average queue length for these systems. However, these results are order results and provide only a limited characterization of the delay of the system. For example, the maximal matching policies achieve O(1) delay for networks with single-hop traffic when the input load is in the reduced capacity region. This analysis however, has not been extended to the multi-hop traffic case, because of the lack of an analogous Lyapunov function for the back-pressure policy.

  • Large Deviations: Large deviation results for cellular and multi-hop systems with single hop traffic have been to estimate the decay rate of the queue-overflow probability. Similar analysis is much more difficult for the multi-hop wireless network considered here, due to the complex interactions between the arrival, service, and backlog process.

5) Design of Delay Efficient Policies module

A scheduler must satisfy the following properties.

  • Ensure high throughput: This is important because if the scheduling policy does not guarantee high throughput then the delay may become infinite under heavy loading.
  • Allocate resources equitably: The network resources must be shared among the flows so as not to starve some of the flows. Also, non-interfering links in the network have to be scheduled such that certain links are not starved for service. Starvation leads to an increase in the average delay in the system.

The above properties are difficult to achieve; given the dynamics of the network and the lack of apriori information of the packet arrival process. In the light of the previous work we choose to investigate the back-pressure policy with fixed routing. The back-pressure policy has been widely used to develop solutions for a variety of problems in the context of wireless networks and the importance of studying the trade-offs in stability, delay, and complexity of these solutions is now being realized by the research community. This policy tries to maintain the queues corresponding to each flow in decreasing order of size from the source to the destination. This is achieved by using the value of differential backlog (difference of backlogs at the two ends of a link) as the weight for the link and scheduling the matching with the highest weight. As a result, the policy is throughput optimal. Henceforth, we shall refer to this policy as only the back-pressure policy. We first study the delay optimal policy for a clique network.

System Requirements:

Hardware Requirements: 

  • System : Pentium IV 2.4 GHz.
  • Hard Disk : 40 GB.
  • Floppy Drive : 1.44 Mb.
  • Monitor : 15 VGA Colour.
  • Mouse : Logitech.
  • Ram : 512 Mb.

Software Requirements: 

  • Operating system : – Windows XP.
  • Coding Language : -JAVA, Swing, RMI, J2ME(Wireless Toolkit)
  • Tool Used : – Eclipse 3.3

REFERENCE:

Gagan Raj Gupta, Ness B. Shroff, “Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks”, IEEE/ACM Transactions on Networking, Vol. 19, No.1, Feb 2011.