(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 1 Multiple region Multiple Quality ROI Encoding using Wavelet Transform P.Rajkumar1 and Madhu Shandilya2 1,2Department of Electronics, Maulana Azad National Institute of Technology, Bhopal, India madhu_shandilya@yahoo.in Abstract: The Wavelet Transform, which was developed in the last two decades, provides a better time-frequency representation of the signal than any other existing transforms. It also supports region of interest (ROI) encoding. This allows different regions of interests to be encoded at different bit rats with different quality constraints, rather than encoding the entire image with single quality constraints. This feature is highly desirable in medical image processing. By keeping this in mind we propose multiple regions multiple quality (MRMQ) encoding technique which facilitates different ROIs according to the priority of enhancement. The paper utilizes the adaptive biorthogonal wavelet application to keep quality in the highest priority ROI, as they posses excellent reconstruction features. The paper also proposes bit saving by pruning the detail coefficients in the wavelet decompositions and truncating the approximation coefficients outside ROI by using space frequency quantization method. Simulation results obtained shows that, by proposed method the image quality can be kept high up to loss less in the ROI region while limiting the quality outside the ROIs. Keywords: Wavelet Transform, supports region of interest. 1. Introduction to medical imaging Medical images are now almost always gathered and stored in digital format for easy archiving, storage and transmission, and to allow digital processing to improve diagnostic interpretation. Recently, medical diagnostic data produced by hospitals increase exponentially. In an average-sized hospital, many tetra or 1015 bytes of digital data are generated each year, almost all of which have to be kept and archived. Furthermore, for telemedicine or tele browsing applications, transmitting a large amount of digital data through a bandwidth-limited channel becomes a heavy burden [1]. Three-dimensional data sets, such as medical volumetric data generated by computer tomography (CT) or magnetic resonance (MR), typically contain many image slices that require huge amounts of storage. A typical mammogram must be digitized at a resolution of about 4000 x 5000 pixels with 50 µm spot size and 12 bits, resulting in approximately 40Mb of digital data. Such high resolution is required in order to detect isolated clusters of micro calcifications that herald an early stage cancer. The processing or transmission time of such digital images could be quite long. Also, archiving the amount of data generated in any screening mammography program becomes an expensive and difficult challenge. [2] The storage requirement for digital coronary angiogram video is huge. A typical procedure of 5 minutes, taken at 30 frames per second for 512x512 pixel images results in approximately 2.5GB of raw data. [3] 2. Need for Image compression A digital compression technique can be used to solve both the storage and the transmission problems. An efficient lossy compression scheme to reduce digital data without significant degradation of medical image quality is needed. Compression methods are important in many medical applications to ensure fast interactivity during browsing through large sets of images (e.g. volumetric data sets, time sequences of images, image databases). In medical imaging, it is not acceptable to lose any information when storing or transmitting an image. There is a broad range of medical image sources, and for most of them discarding small image details might alter a diagnosis and cause severe human and legal consequences. [1] In addition to high compression efficiency, future moving image coding systems will require many other features. They include fidelity and resolution scalability, region of interest enhancement, random access decoding, and resilience to errors due to channel noise or packet loss, fast encoding/decoding speed, low computational and hardware complexity. Recent developments in pattern recognition (regions of interest segmentation) and image processing have advanced the state-of-the-art of image processing. During the past few years, we have applied some of these latest imageproceessin techniques on image enhancement classification and compression. 3. Region of interest (ROI) encoding Support of region of interest (ROI) access is a very interesting feature of image compression, in which an image sequence can be encoded only once and then the decoder can directly extract a subset of the bit stream to reconstruct a chosen ROI of required quality [4] The arbitrarily shaped regions inside an image will be encoded at different quality levels according to their importance or, as per diagnostic relevance. The whole image is transformed and coefficients associated to the ROI are coded at higher precision (up to lossless) than the background. Especially in medical imaging ROI coding help compression method s to focus on those regions that are important for diagnosis purpose. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 2For some applications, only a subsection of the image sequence is selected for analysis or diagnosis. Therefore, it is very important to have region of interest retrievability that can greatly save decoding time and transmission bandwidth. An important part of genetics analysis starts with researchers breaking down the nucleus of a human cell into a jumbled cluster of chromosomes that are then stained with dye so that they can be studied under a microscope. This jumble of stained chromosomes, which carry the genetic code of the host individual, is then photographed, creating a chromosome spread image (see Fig. 1 (a)). This image is subsequently subject to a procedure called chromosomekaryootypin analysis. The result of this procedure is a karyotype image (see Fig. 1 (b)), the standard form used to display chromosomes. In this configuration, the chromosomes are ordered by length from the largest (chromosome 1) to the smallest (chromosome 22 in humans), followed by the sex chromosomes. Karyotype images are used in clinical tests, such as amniocentesis, to determine if all the chromosomes appear normal and are present in the correct number. [5] Unlike some other types of medical imagery, chromosome images (see Fig. 1) have an important common characteristic: the regions of interest (ROIs) to cytogeneticists for evaluation and diagnosis are all well determined and segmented prior to image storage. The remaining background images, which may contain cell nuclei and stain debris, are kept as well in routine cytogenetics lab procedures for specimen reference rather than for diagnostic purposes. Since the chromosome ROIs are much more important than the rest of the image for karyotyping analysis, loss less compression for the former is required while lossy compression for the latter is acceptable. This calls for lossy and loss less region-of-interest (ROI) coding. In contrast, commercial chromosome karyotyping systems fail to utilize the ROI information by compressing entire chromosome spread or karyotype images. Figure. 1(a) A metaphase cell spread image[5] Figure. 1(b) A metaphase cell’s karyotype[5] In the karyotype, all chromosomes in the spread are rotated and copied onto an image with constant background and positioned according to their classes. The label annotation is drawn separately. 4. Wavelet transform Discrete cosine transform and Wavelet transform are more commonly used for compression. The popular JPEG & MPEG uses discrete cosines transform based compression; While JPEG 2000 uses Wavelet transform based compression. The DCT based compression; the algorithm breaks the image into 8x8 pixel blocks and performs a discrete cosine transform on each block. The result is an 8x8 block of spectral coefficients with most of the information is concentrated in relatively few coefficients. Quantization is performed, which approximates the larger coefficients; smaller coefficients become zero. These quantized coefficients are then reordered in a zig zag manner to group the largest values first, with long strings of zeroes at the end that can be efficiently represented. While this algorithm is very good for general purposes, it has some draw backs when applied to medical images .It degrades ungracefully at high compression ratios, producing prominent artifacts at block boundaries, and it can not take advantage of patterns larger than the8x8 blocks. Such artifacts could potentially be mistaken as being diagnostically significant. A wavelet approach was also suggested by Li who considered the problem of accessing still, medical image data, remotely over low bandwidth networks. This was accomplished using a region of interest (ROI) based approach that allocated additional bandwidth within a dynamically allocated ROI, whilst at the same time providing an embedded bit stream, which is useful for progressive image encoding.[3] Some of the key features of the wavelet transform which make it such a useful tool are: · Spatial-frequency localization, · Energy compaction, · Decaying magnitude of wavelet coefficients across sub-bands. Wavelet based compression schemes generally out perform JPEG compression in terms of image quality at a given compression ratio, and the improvement can be dramatic at high compression ratios. [9] The Wavelet Transform, which was developed in the last two decades, provides a better time-frequency representation of the signal than any other existing transforms. It supports ROI (region of interest) encoding. Multiple regions multiple qualities ROI encoding facilitates different ROIs according to the priority to be enhanced with different qualities (i.e. at different compression ratios, both by lossless and lossy methods), while limiting the bit size outside ROI by compressing heavily (lossy). This paper proposes the application of adaptive biorthogonal wavelets to keep quality in the highest priority ROI as they posses excellent reconstruction features. 4.1 Classification of wavelets We can classify wavelets into two classes: [7] (a) Orthogonal and (b) biorthogonal.Based on the application, either of them can be used. 4.1.1 Features of orthogonal wavelet filter banks The coefficients of orthogonal filters are real numbers. The filters are of the same length and are not symmetric. The low pass filter, G0 and the high pass filter, H0 are related to each other by (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 3 H0 (z) = z -N G0 (-z-1) (1) {Fi,j (t)Yi,j (t)} and {Φi,j(t) Ψ˜i,j(t)} are the biorthogonal basis functions[8]. a˜j,k and b˜j,k are the scaling and wavelet coefficients respectively; together they form the biorthogonal DWT coefficients of x(t). The DWT starts at some finest scale j = M and stops at some coarsest scale j = N. M -N is the number of levels of decomposition in the biorthogonal DWT of x (t). 4.1.3 Selection of wavelet from the biorthogonal family: Different wavelets will be suited for different types of images. One wavelet basis may produce highest coefficient for a picture, may not necessarily produce highest coefficients for all pictures for all images while decomposing the image using the wavelet transform. Keeping this in the mind, Adaptive wavelet basis function is additionally proposed. Amongst the all important biorthogonal wavelet basis functions, a particular wavelet basis function is chosen on the basis of comparison of the highest coefficients produced by all the different wavelet basis functions at the first level of the decomposition process. The proposed MRMQ Encoding uses the Discrete Wavelet Transform, chooses the right Biorthogonal basis function on the basis of the highest coefficient produced in the highest priority ROI amongst of all the ROIs. 5. Multiple Regions Multiple Quality ROI Encoding For certain applications, only specific regions in the volumetric data or video are of interest. For example, in MR imaging of the skull, the physician is mostly concerned about the features inherent in the brain region. In video conferencing, the speaker’s head and shoulders are of main interest and need to be coded at higher quality whereas the background can be either discarded or encoded at a much lower rate. High compression ratios can be achieved by allocating more bit rate for region(s) of interest (ROI) and less bit rate for the remaining regions, i.e. the background. Region-based image coding schemes using heterogeneous (multiple) quality constraints are especially attractive because they not only can well preserve the diagnostic features in region(s) of interest, but also meet the requirements of less storage and shorter transmission time for medical imaging applications and video transmission. A main advantage of the proposed technique is that it supports multiple-region multiple-quality (MRMQ) coding. By this method, total bit budget can be allocated among multiple ROIs and background depending on the quality constraints. Experimental results show that this technique offers reasonably well performance for coding multiple ROIs. To support region of interest (ROI) coding, it is necessary to identify the wavelet transform coefficients associated with the ROI. We have to keep track of the coefficients that are involved in the reconstruction of ROI through each stage of decomposition. 5.1 ROI Coding We use region mapping which trace the positions of pixels in an ROI in image domain back into transform domain by inverse DWT. The coefficients of greater importance are called ROI coefficients, the rest are called background coefficients. The coding algorithm, fig.2 needs to keep track of the locations of wavelet coefficients according to the shape of the ROI. To obtain the information about ROI coefficients, a mask image, which specifies the ROI, is decomposed by the wavelet decomposition of the image. In each decomposition stage, each subband of the decomposed mask contains information for specifying the ROI in that subband. By successively decomposing the approximation coefficients The two filters are alternated flip of each other. The alternating flip automatically gives double-shift orthogonality between the low pass and high pass filters, i.e., the scalar product of the filters, for a shift by two is zero i.e, åG [k] H [k-2l] = 0, where k,l εZ . Perfect reconstruction is possible with alternating flip. Also, for perfect reconstruction, the synthesis filters are identical to the analysis filters except for a time reversal. Orthogonal filters offer a high number of vanishing moments. This property is useful in many signal and image processing applications. They have regular structure, which leads to easy implementation and scalable architecture. 4.1.2 Features of biorthogonal wavelet filter banks In the case of the biorthogonal wavelet filters, the low pass and the high pass filters do not have the same length. The low pass filter is always symmetric, while the high pass filter could be either symmetric or anti-symmetric. The coefficients of the filters are either real numbers or integers. For perfect reconstruction, biorthogonal filter bank has all odd length or all even length filters. The two analysis filters can be symmetric with odd length or one symmetric and the other antisymmetric with even length. Also, the two sets of analysis and synthesis filters must be dual. The linear phase biorthogonal filters are the most popular filters for data compression applications The analysis and synthesis equations for the biorthogonal DWT of any x (t) ε L2(R) are Analysis ã j,k = ∫ x(t)2j/2f̃(2jt-k)dt (2) b̃j,k = ∫ x(t)2j/2ỹ(2jt-k)dt (3) Synthesis M-1 x(t)= 2 N/2S ãN,k f(2 Nt-k) + S 2j/2 k j=N S b̃j,k y(2 jt-k) (4) k (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 4(LL subband) for a number of decomposition levels, information about ROI coefficients is obtained. Figure 2. ROI Encoding using Wavelet Transform 5.2 Outside ROI Space –Frequency Quantization (SFQ) technique exploits both spatial and frequency compaction property of the wavelet transform through the use of two simple quantization modes. To exploit the spatial compaction property, a symbol is defined, that indicates that a spatial region of high frequency coefficients has zero value. Application of this symbol is referred to as zero-tree quantization. This is done in the first phase called Tree Pruning Algorithm. In the next phase called Predicting the tree, the relation between a spatial region in image and the tree-structured set of coefficients is exploited. Zero tree quantization can be viewed as a mechanism for pointing to the location where high frequency coefficients are clustered. Thus, this quantization mode directly exploits the spatial clustering of high frequency coefficients predicted. For coefficients that are not set to zero by zero tree quantization, a common uniform scalar quantization, independent of coefficient frequency band is applied. Uniform quantization followed by entropy coding provides nearly optimal coding efficiency. 6. Results In Fig. 3 an Image is taken showing the abdominal operation. In the above Image MRMQ ROI encoding is applied. The result is shown in fig. 4.Here the no. of ROIs are 2, as shown the area outside the ROI is heavily degraded .The PSNR of this image is 25dB.while the quality is lossless in the ROI. The PSNR vs. bits per pixel of the ROI enhanced Image at various compression points is plotted in fig.5. This shows that although the PSNR difference is less whiles the bits per pixel reduces from 1bpp to 0.5 bpp using Matlab® simulation. Fig. 6 an image of a newborn baby affected by sacrococcyged teratoma (before surgery) is taken. In fig. 7 the area outside the ROI is heavily degraded. In fig. 8, Outside the ROI is excluded for further reducing the bit size requirement. The PSNR vs. bits per pixel at various compression points are plotted in fig. 9. Figure 5. PSNR vs. bits per pixel of the ROI enhanced Image “abdomen” Note: ROI area is 17230pixels and Image is 448x336 pixels. Figure 6. Teratoma affected baby Figure 7. ROI enhanced Teratoma affected baby (Background degraded) Figure 8. ROI enhanced Trachoma affected baby (Background excluded) Figure 3. Original medical Image of abdominal operation (2.32bpp) Figure 4. ROI Enhanced medical image of fig. 3 Here no. of ROI =2(0.92bpp, PSNR =25.2db) Bits per pixel PSNR (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 5 Figure 9. PSNR vs. bpp of the ROI enhanced Teratoma affected baby 7. Conclusions The simulation results give bits per pixel with corresponding PSNR values for the proposed MRMQ ROI encoding. It has been observed that for still images, the bit size requirement was made less by degrading the image quality out side the ROI, while keeping the quality of image uncompromised in the ROI region. In the present paper, still image results are simulated with the biorthogonal wavelet transform family for the multiple region multiple quantization (MRMQ) ROI coding, therefore further analysis can be extended in the field of video processing. Also the present analysis is carried on the medical still images, which can be extended for the video processing with graphical and natural images. References [1] Shaou-Gang Miaou, Shih-Tse Chen, Shu-Nien Chao , Wavelet-Based Lossy-to-Lossless Medical Image Compression Using Dynamic VQ And SPIHT Coding, Biomedical Engineering applications, Basis &Communications. Pg 235-242 Vol. 15 No. 6 December 2003. [2] M´onica Penedo, William A. PearmanPablo G. Tahoces, Miguel Souto, Juan J. Vidal, EmbeddedWavelet Region-Based Coding Methods Applied To Digital Mammography IEEE International Conference on Image Processing, vol.3 Barcelona, Spain 2003. [3] David Gibson, Michael Spann, Sandra I. Woolley, A Wavelet-Based Region of Interest Encoder for the Compression of Angiogram Video Sequences, IEEE Transactions on Information Technology in Biomedicine 8(2): 103-113 (2004) [4] Kaibin Wang, B.Eng., M.Eng. Thesis: Region-Based Three-Dimensional Wavelet Transform Coding, Carleton University, Ottawa, Canada, May, 2005. [5] Zixiang Xiong, Qiang Wu and Kenneth R.,Castlemen, Enhancement, Classification And Compression Of Chromosome Images. Workshop on Genomic Signal Processing, 2002 , Cite seer. [6] Charilaos Christopoulos, Athanassios Skodras ,Touradj Ebrahimi -The JPEG2000 Still Image Coding System:An Overview , IEEE Transactions on Consumer Electronics, Vol. 46, No. 4, pp. 1103-1127, November 2000. [7] K.P.Soman and K.I.Ramachandran -Insight Into Wavelets –From Theory to Practice,PHI Publications. [8] Sonja Grgic, Mislav Grgic, and Branka Zovko-Cihlar, Performance Analysis of Image Compression Using Wavelets, IEEE Transactions on Industrial Electronics, vol.48, no. 3, June 2001. [9] Michael W. Marcellina, Margaret A. Lepleyb, Ali Bilgina, Thomas J. Flohrc, Troy T. Chinend, James H. Kasner, An overview of quantization in JPEG 2000 Signal Processing: Image Communication 17 (2002) 73– 84. Authors Profile P.Rajkuma received the M.Tech. Degree in Electronics Engineering from Maulana Azad National Institute of Tech.Bhopal, India in 2006.He is doing his research in the area of medical image processing. Madhu Shandilya received the M.Tech. and Ph.D. degrees in Electronics Engineering from Maulana Azad National Institute of Tech.Bhopal, India in 1994 and 2005, respectively. From last 22 years she is associated with Electronics Engineering from Maulana Azad National Institute of Tech.Bhopal. She has published/presented about 20 papers in various national and international journals /conferences. Her area of specialization is digital image processing. PSNR (db) Bits per pixel (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 62-Dimension Automatic Microscope Moving Stage Ovasit P.1 Adsavakulchai S.1,* Srinonghang W1., and Ueatrongchit, P. 1 1School of Engineering, University of the Thai Chamber of Commerce 126/1 Vibhavadi Rangsit Rd., Bangkok 10400 *Corresponding author, e-mail: suwannee_ads@utcc.ac.th Abstract: Currently, microscope stage has controllable by manual. In medical laboratory, the specimen slide examination system processes one at a time for microscopic examination. The main objective of this study is to develop a two-dimension automatic microscope moving stage. This equipment is designed by microcontroller PIC 16F874 using stepping motor as horizontal feed mechanism. There are three function modes, the first one is manual, the second is automatic scan specimen which transfers the specimen slide onto a microscope stage which has controllable X and Y axis positioning to move the specimen slide into the optical viewing field of the microscope and examination over the desired area of the specimen and the last one is to examine specimen slides may be automatically returned to the microscope stage for reexamination. The result of this study can be concluded that the accuracy of this equipment for reexamination the specimen slide is 86.03 % accuracy. Keywords: Microscope Automatic Moving Stage, microcontroller PIC16F874, stepping motor 1. Introduction The microscope is a conventional laboratory microscope with attached to actuate the stage and control is affected through manual [1] as shown in Figure 1. Figure 1. Microscope moving stage The basic principal for diagnostic in red blood cell is using microscope manually. In such cases, electronic systems may be used to automatically examine and analyze the optical images of the microscope [2]. Where electronics systems are used for rapid analysis of microscope specimen images it becomes desirable to automatically regularly and rapidly feed the specimens to the microscope optics. After analysis a specimen would be removed to make room for the next specimen and would be collected for either further examination, reference, record keeping or disposal. An automated slide system is disclosed which organizes microscope slides in cassettes, automatically and positioned each slide under the microscope as provided by the protocol, and after examination returns the slide to its proper cassette [3]. A slot configured for holding slides in spaced parallel configuration using the mechanism for removing and replacing a slide housed. A feed arm containing a longitudinal to draw-out spring wire surrounding an imaginary longitudinal axis having at the first end and a second end, the first and second end being bent orthogonal to one another and to the imaginary longitudinal axis of said draw-out spring wire, said longitudinal draw-out spring wire being positioned in said longitudinal channel in said feed arm such that bent ends protrude from the channel and wherein said longitudinal draw-out spring wire is operatively positioned in said longitudinal channel such that the draw-out spring wire is rotatable therein, allowing for each bent end to change orientation in respect to the feed arm. [1]. The main objective of this study is to develop an automatically returned to the microscope stage for reexamination. These technologies dramatically increased the accuracy of measurement results and contributed greatly to the modernization of testing and medical care (medical testing). 2. Materials and Methods Sample preparation: 2.1 To prepare the blood smear sample and set up the microscope working area at 1000x with 0.2 mm. dimension [2] as shown in Figure 2. In order to the area of the specimen slide is viewed during examination of the specimen without sliding it. Figure 2. Microscope working area 2.2 To set up the scope of microscope moving stage scanning area with 40 x 26 mm. as shown in Figure 3. About the specimen stage this opening in the specimen (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 7 stage is made as large as possible and exposes the full width of the specimen slide. Figure 3. Scanning area 2.3 The automatic sequential examination of a group of microscope specimen slides comprising: 2.3.1 Moving stage design: Apparatus comprised a substage directing serves to move stage in a horizontal plane and there is provided further positioning means supporting said translation means and operable for moving said stage with a specimen slide supported therein vertically as shown in Figure 4. Figure 4. Moving stage design 2.3.2 Digital Electronics Design: The digital electronics architecture has two main functional blocks, Master Board and Slave Board. ICP (Instrument Control Processor): used a PIC 16F873 processor to perform all instrument control and event processing functions as shown in Figure 5. The ICP will be responsible for the following tasks: processing commands; monitoring source and adjusting the LCD readout mode as required; calculating centroids and transmitting centroid positions [4],[5],[6]. Figure 5. Digital Electronics design Figure 5 is to illustrate the overall digital electronics using two microcontrollers with serial communication and synchronous Serial Peripheral Interface (SPI). 2.3.3 Microcontroller in Slave Board: 2.3.3.1 Encoder: using sequential logic to control moving stage. The characteristic of encoder 2 signal using microcontroller PIC 16F873 via RA0-RA3 port as shown in Figure 6. The signals moving stage is to set up into 3 statuses 1. No movement 2. Increase the distance and 3. Reduce distance as shown in Figure 7. Figure 6. The characteristic of encoder 2 signal Figure 7. Logical control 2.3.3.2 Stepping motor: control moving stage using microcontroller PIC 16F873 via RB0-RB7 port and working together with IC ULN2803 to control stepping motor as shown in Figure 8. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 8 Figure 8. Characteristics of stepping motor control 2.3.3.3 Serial Peripheral Interface: using Master Synchronous Serial Port in microcontroller PIC 16F873 using Microcontroller in Slave Board as shown in Figure 9. Figure 9. Serial Peripheral Interface (SPI) 2.3.4 Microcontroller in Mater Board 2.3.4.1 Input from keyboard using RB1-RB7 in term of matrix 4 x 3 2.3.4.2 Display result using RA0-RA5 for Liquid Crystal Display 2.3.4.3 Serial Peripheral Interface SCK port 2.3.4.5 Data communication using SPI as shown in table 1 Table 1 : Data communication using SPI To design main menu as shown in Figure 10 to control the microscopic stage. X 0000 #:Exit Y 0000 *:Stop Microscope Scan. Version 1.00 1:Home 2:Manual 3:Scan 4:Config X 0000 #:Exit Y 0000 *:Jump Home Please Wait. 1:Posit. #:Exit 2:Option Config 3 1 4 Wait 1:Start #:Exit 2:Final < Save X _000 #:Exit Y 0000 < Jump Wait Start. Please Wait. X 0000 #:Exit Y 0000 *:Scan * T: 0sec #:Exit S:>_unit Space 1: 0sec #:Exit 2: 0unit OptionStart 0000x0000y Final 0000x0000y T:>_sec #:Exit S: 0unit Time. 2 : S 1 1 : T 2 * : X :Y # : 1 or 2 # 2 # Figure 10. Main menu of control program 3. RESULTS AND DISCUSSION To test the points and the results is shown in table 2. The microscopic examination of the specimen slide can take place either visually or automatically. Motorized microscope components and accessories enable the investigator to automate live-cell image acquisition and are particularly useful for time-lapse experiments about 20 milliseconds [7],[8]. For this purpose the X and Y positioning systems can be controlled manually or automatically. Thus, the specimen slide carried by the stage may be moved to any desired location relative to the optical axis by actuation of the Y-axis drive 43 and the Xaxxi drive 44. For automatic examination the drives 43, 44 would be energized under scan or other program control. Finally, the specimen slide reexamination is automatically returned to the microscope stage for reexamination with very high accuracy. Table 2: Sample testing results Status 1a 1b 2a 2b Master Register SSPBUF Register SSPBUF Register SSPSR Register SSPSR Slave (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 9 4. Conclusion After the examination of a particular series of specimen slides has been completed any individual specimen slide that requires re-examination can by either operator signals or by predetermined control signals be fed automatically back into the microscope viewing optics for further examination [9]. Upon completion of the examination of a slide the horizontal positioning Y-axis drive returns the specimen slide on the stage to the position. It can be concluded that the accuracy of this equipment for reexamination the specimen slide is 86.03 % accuracy. Acknowledgements This project is supported by University of the Thai Chamber of Commerce grant. References [1] C.R.David, Microscopy and related methods from http://www.ruf.rice.edu/~bioslabs/methods/microscop y/microscopy.html [2] Robert H., et.al, Handbook of Hematologic Pathology, Marcel Dekker, Inc. (2000) [3] Qin Zhang et al., A Prototype Neural Network Supervised Control System for Bacillus thuringiensis Fermentations, Biotechnology and Bioengineering, vol. 43, pp. 483-489 (1994). [4] N. Armenise et al., High-speed particle tracking in nuclear emulsion by last generation automatic microscopes, accepted for publication on Nucl. Instr. Meth. A(2005). [5] Powell, Power and Perkins, The Study of Elementary Particles by the Photo-graphic Method, Pergamon Press (1959). [6] W.H. Barkas, Nuclear Research Emulsion, Academic Press Inc. (London) Ltd. (1963). [7] John F. Reid et al., A Vision-based System for Computer Control and Data Acquisition in fermentation Processes, 38th Food Technology Conference, 1992. [8] J.M. Shine, Jr., et al., Digital Image Analysis System for Determining Tissue-Blot Immunoassay Results for Ratoon Stunting Disease of Sugarcane, Plant Disease, vol. 77 No. 5, pp. 511-513, 1993. [9] Jinlian Ren et al., Knowledge-based Supervision and Control of Bioprocess with a Machine Vision-based Sensing System, Journal of Biotechnology 36 (1994) 25-34. Authors Profile Suwannee Adsavakulchai received the M.S. degrees in Computer Information Systems from Assumption University in 1994 and Doctoral of Technical Science from Asian Institute of Technology in 2000, respectively. She now works as lecturer in the department of Computer Engineering, School of Engineering, University of the Thai Chamber of Commerce. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 10 A Large Block Cipher Involving a Key Applied on Both the Sides of the Plain Text V. U. K. Sastry1, D. S. R. Murthy2, S. Durga Bhavani3 1Dept. of Computer Science & Engg., SNIST, Hyderabad, India, vuksastry@rediffmail.com 2Dept. of Information Technology, SNIST, Hyderabad, India, dsrmurthy.1406@gmail.com 3School of Information Technology, JNTUH, Hyderabad, India, sdurga.bhavani@gmail.com Abstract: In this paper, we have developed a block cipher by modifying the Hill cipher. In this, the plain text matrix P is multiplied on both the sides by the key matrix. Here, the size of the key is 512 bits and the size of the plain text is 2048 bits. As the procedure adopted here is an iterative one, and as no direct linear relation between the cipher text C and the plain text P can be obtained, the cipher cannot be broken by any cryptanalytic attack. Keywords: Block Cipher, Modular arithmetic inverse, Plain text, Cipher text, Key. 1. Introduction The study of the block ciphers, which was initiated several centuries back, gained considerable impetus in the last quarter of the last century. Noting that diffusion and confusion play a vital role in a block cipher, Feistel etal, [1] –[2] developed a block cipher, called Feistel cipher. In his analysis, he pointed out that, the strength of the cipher increases when the block size is more, the key size is more, and the number of rounds in the iteration is more. The popular cipher DES [3], developed in 1977, has a 56 bit key and a 64 bit plain text. The variants of the DES are double DES, and triple DES. In double DES, the size of the plain text block is 64 bits and the size of the key is 112 bits. In the triple DES, the key is of the length 168 bits and the plain text block is of the size is 64 bits. At the beginning of the century, noting that 64 bit block size is a drawback in DES, Joan Daemen and Vincent Rijmen, have developed a new block cipher called AES [4], wherein the block size of the plain text is 128 bits and key is of length 128, 192, or 256 bits. In the subsequent development, on modifying Hill cipher, several researchers [5]–[9], have developed various cryptographical algorithms wherein the length of the key and the size of the plain text block are quite significant. In the present paper, our objective is to develop a block cipher wherein the key size and the block size are significantly large. Here, we use Gauss reduction method for obtaining the modular arithmetic inverse of a matrix. In what follows, we present the plan of the paper. In section 2, we have discussed the development of the cipher. In section 3, we have illustrated the cipher by considering an example. In section 4, we have dealt with the cryptanalysis of the cipher. Finally, in section 5, we have presented the computations and arrived at the conclusions. 2. Development of the cipher Consider a plain text P which can be represented in the form of a square matrix given by P = [Pij], i = 1 to n, j = 1 to n, (2.1) where each Pij is a decimal number which lies between 0 and 255. Let us choose a key k consisting of a set of integers, which lie between 0 and 255. Let us generate a key matrix, denoted as K, given by K = [Kij], i = 1 to n, j = 1 to n, (2.2) where each Kij is also an integer in the interval [0 – 255]. Let C = [Cij], i = 1 to n, j = 1 to n (2.3) be the corresponding cipher text matrix. The process of encryption and the process of decryption applied in this analysis are given in Fig. 1. Figure 1. Schematic Diagram of the cipher Here r denotes the number of rounds. In the process of encryption, we have used an iterative procedure which includes the relations P = (K P K) mod 256, (2.4) (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 11 P = Mix (P), (2.5) and P = P Å K (2.6) The relation (2.4) causes diffusion, while (2.5) and (2.6) lead to confusion. Thus, these three relations enhance the strength of the cipher. Let us consider Mix (P). In this the decimal numbers in P are converted into their binary form. Then we have a matrix of size n x 8n, and this is given by Here, P111, P112, …, P118 are binary bits corresponding to P11. Similarly, Pij1, Pij2, …, Pij8 are the binary bits representing Pij. The above matrix can be considered as a single string in a row wise manner. As the length of the string is 8n2, it is divided into n2 substrings, wherein the length of each substring is 8 bits. If n2 is divisible by 8, we focus our attention on the first 8 substrings. We place the first bits of these 8 binary substrings, in order, at one place and form a new binary substring. Similarly, we assemble the second 8 bits and form the second binary substring. Following the same procedure, we can get six more binary substrings in the same manner. Continuing in the same way, we exhaust all the binary substrings obtained from the plain text. However, if n2 is not divisible by 8, then we consider the remnant of the string, and divide it into two halves. Then we mix these two halves by placing the first bit of the second half, just after the first bit of the first half, the second bit of the second half, next to the second bit of the first half, etc. Thus we get a new binary substring corresponding to the remaining string. This completes the process of mixing. In order to perform the exclusive or operation in P = P Å K, we write the matrices, both P and K, in their binary form, and carryout the XOR operation between the corresponding binary bits. In the process of decryption, the function IMix represents the reverse process of Mix. In what follows, we present the algorithms for encryption, and decryption. We also provide an algorithm for finding the modular arithmetic inverse of a square matrix. Algorithm for Encryption 1. Read n, P, K, r 2. for i = 1 to r { P = (K P K) mod 256 P = Mix (P) P = P Å K } 3. C = P 4. Write (C) Algorithm for Decryption 1. Read n, C, K, r 2. K–1 = Inverse (K) 3. for i = 1 to r { C = C Å K C = IMix (C) C = (K–1 C K–1) mod 256 } 4. P = C 5. Write (P) Algorithm for Inverse (K) //The arithmetic inverse (A–1), and the determinant of the matrix (D) are obtained by Gauss reduction method. 1. A = K, N = 256 2. A–1 = [Aji] /D, i = 1 to n, j = 1 to n //Aji are the cofactors of aij, where aij are elements of A, and D is the determinant of A 3. for i = 1 to n { if ((i D) mod N = 1) d = i; break; } 4. B = [d Aji] mod N //B is the modular arithmetic inverse of A 3. Illustration of the cipher Let us consider the following plain text. No country wants to bring in calamities to its own people. If the people do not have any respect for the country, then the Government has to take appropriate measures and take necessary action to keep the people in order. No country can excuse the erratic behaviour of the people, even though something undue happened to them in the past. Take the appropriate action in the light of this fact. Invite all the people to come into the fold of the Government. Try to persuade them as far as possible. Let us see!! (3.1) Let us focus our attention on the first 256 characters of the above plain text which is given by No country wants to bring in calamities to its own people. If the people do not have any respect for the country, then the Government has to take appropriate measures and take necessary action to keep the people in order. No country can excuse the erratic (3.2) On using EBCDIC code, we get 26 numbers, corresponding to 256 characters. Now on placing 16 numbers in each row, we get the plain text matrix P in the decimal form Obviously, here the length of the plain text block is 16 x 16 x 8 (2048) bits. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 12 Let us choose a key k consisting of 64 numbers. This can be written in the form of a matrix given by The length of the secret key (which is to be transmitted) is 512 bits. On using this key, we can generate a new key K in the form w here U = QT, in which T denotes the transpose of a matrix, and R and S are obtained from Q and U as follows. On interchanging the 1st row and the 8th row of Q, the 2nd row and the 7th row of Q, etc., we get R. Similarly, we obtain S from U. Thus, we have whose size is 16 x 16. On using the algorithm for modular arithmetic inverse (See Section 2), we get On using (3.6) and (3.7), it can be readily shown that K K–1 mod 256 = K–1K mod 256 = I. (3.8) On applying the encryption algorithm, described in Section 2, we get the cipher text C in the form On using (3.7) and (3.9), and applying the decryption algorithm presented in section 2, we get the Plain text P. This is the same as (3.3). Let us now find out the avalanche effect. To this end, we focus our attention on the plain text (3.2), and modify the 88th character ‘y’ to ‘z’. Then the plain text changes only in one binary bit as the EBCDIC code of y is 168 and that of z is 169. On using the encryption algorithm, we get the cipher text C corresponding to the modified plain text (wherein y is replaced by z) in the form On comparing (3.9) and (3.10), we find that the two cipher texts differ in 898 bits, out of 2048 bits, which is quite considerable. However, it may be mentioned here that, the impact of changing 1 bit is not that copious, as the size of the plain text is very large. Even then it is remarkable. Now let us change the key K given in (3.6) by one binary bit. To this end, we replace the 60th element 5 by 4. Then on using the original plain text given by (3.3), we get C in the form On comparing (3.9) and (3.11), we find that the cipher texts differ in 915 bits, out of 2048 bits. From the above analysis, we find that the avalanche effect is quite pronounced and shows very clearly that the cipher is a strong one. 4. Cryptanalysis In the literature of cryptography, it is well known that the different types of attacks for breaking a cipher are: (1) Cipher text only attack, (2) Known plain text attack, (3) Chosen plain text attack, (4) Chosen cipher text attack. In the first attack, the cipher text is known to us together with the algorithm. In this case, we can determine the plain text, only if the key can be found. As the key contains 64 decimal numbers, the key space is of size 2512 ~ (103)51.2 = 10153.6 which is very large. Hence, the cipher cannot be broken by applying the brute force approach. We know that, the Hill cipher [1] can be broken by the known plain text attack, as there is a direct linear relation between C and P. But in the present modification, as we have all nonlinear relations in the iterative scheme, the C can never be expressed in terms of P, thus P cannot be determined by any means in terms of other quantities. Hence, this cipher cannot be broken by the known plain text attack. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 13 As there are three relations, which are typical in nature, in the iterative process for finding C, no special choice of either the plain text or the cipher text or both can be conceived to break the cipher. 5. Conclusions In the present paper, we have developed a large block cipher by modifying the Hill cipher. In the case of the Hill cipher, it is governed by the single, linear relation C = (K P) mod 26, (5.1) while in the present case, the cipher is governed by an iterative scheme, which includes the relations P = (K P K) mod 256, (5.2) P = Mix (P), (5.3) and P = P Å K. (5.4) Further, it is followed by C = P. (5.5) In the case of the Hill cipher, we are able to break the cipher as there is a direct linear relation between C and P. On the other hand, in the case of the present cipher, as we cannot obtain a direct relation between C and P, this cipher cannot be broken by the known plain text attack. By decomposing the entire plain text given by (3.1) into blocks, wherein each block is of size 256 characters, the corresponding cipher text can be obtained in the decimal form. The first block is already presented in (3.9) and the rest of the cipher text is given by In this analysis, the length of the plain text block is 2048 bits and the length of the key is 512 bits. As the cryptanalysis clearly indicates, this cipher is a strong one and it cannot be broken by any cryptanalytic attack. This analysis can be extended to a block of any size by using the concept of interlacing [5]. References [1]. Feistel H, “Cryptography and Computer Privacy”, Scientific American, May 1973. [2]. Feistel H, Notz W, Smith J, “Some Cryptographic Techniques for Machine-to-Machine Data Communications”, Proceedings of the IEEE, Nov. 1975. [3]. William Stallings, Cryptography and Network Security, Principles and Practice, Third Edition, Pearson, 2003. [4]. Daemen J, Rijmen V, “Rijdael: The Advanced Encryption Standard”, Dr. Dobb’s Journal, March 2001. [5]. V. U. K. Sastry, V. Janaki, “On the Modular Arithmetic Inverse in the Cryptology of Hill Cipher”, Proceedings of North American Technology and Business Conference, Sep. 2005, Canada. [6]. V. U. K. Sastry, S. Udaya Kumar, A. Vinaya Babu, “A Large Block Cipher using Modular Arithmetic Inverse of a Key Matrix and Mixing of the Key Matrix and the Plaintext”, Journal of Computer Science 2 (9), 698 – 703, 2006. [7]. V. U. K. Sastry, V. Janaki, “A Block Cipher Using Linear Congruences”, Journal of Computer Science 3(7), 556 – 561, 2007. [8]. V. U. K. Sastry, V. Janaki, “A Modified Hill Cipher with Multiple Keys”, International Journal of Computational Science, Vol. 2, No. 6, 815 – 826, Dec. 2008. [9]. V. U. K. Sastry, D. S. R. Murthy, S. Durga Bhavani, “A Block Cipher Involving a Key Applied on Both the Sides of the Plain Text”, International Journal of Computer and Network Security (IJCNS), Vol. 1, No.1, pp. 27 – 30, Oct. 2009. Authors Profile Dr. V. U. K. Sastry is presently working as Professor in the Dept. of Computer Science and Engineering (CSE), Director (SCSI), Dean (R & D), SreeNidhi Institute of Science and Technology (SNIST), Hyderabad, India. He was Formerly Professor in IIT, Kharagpur, India and worked in IIT, Kharagpur during 1963 – 1998. He guided 12 PhDs, and published more than 40 research papers in various international journals. His research interests are Network Security & Cryptography, Image Processing, Data Mining and Genetic Algorithms. Dr. S. Durga Bhavani is presently working as Professor in School of Information Technology (SIT), JNTUH, Hyderabad, India. Her research interest is Image Processing. Mr. D. S. R. Murthy obtained B. E. (Electronics) from Bangalore University in 1982, M. Tech. (CSE) from Osmania University in 1985 and presently pursuing Ph.D. from JNTUH, Hyderabad since 2007. He is presently working as Professor in the Dept. of Information Technology (IT), SNIST since Oct. 2004. He earlier worked as Lecturer in CSE, NIT (formerly REC), Warangal, India during Sep. 1985 – Feb. 1993, as Assistant Professor in CSE, JNTUCE, Anantapur, India during Feb. 1993 – May 1998, as Academic Coordinator, ISM, Icfaian Foundation, Hyderabad, India during May 1998 – May 2001 and as Associate Professor in CSE, SNIST during May 2001 -Sept. 2004. He worked as Head of the Dept. of CSE, JNTUCE, Anantapur during Jan. 1996 – Jan 1998, Dept. of IT, SNIST during Apr. 2005 – May 2006, and Oct. 2007 – Feb. 2009. He is a Fellow of IE(I), Fellow of IETE, Senior Life Member of CSI, Life Member of ISTE, Life Member of SSI, DOEACC Expert member, and Chartered Engineer (IE(I) & IETE). He published a text book on C Programming & Data Structures. His research interests are Image Processing and Image Cryptography. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 14 Electrocardiogram Prediction Using Error Convergence-type Neuron Network System Shunsuke Kobayakawa1 and Hirokazu Yokoi1 1Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology 2-4 Hibikino, Wakamatsu-ku, Kitakyushu-shi, Fukuoka 808-0196, Japan {kobayakawa-shunsuke@edu., yokoi@}life.kyutech.ac.jp Abstract: The output error of a neuron network cannot converge at zero, even if training for the neuron network is iterated many times. “Error Convergence-type Neuron Network System” has been proposed to improve this problem. The output error of the proposed neuron network system is converged at zero by infinitely increasing the number of neuron networks in the system. A predictor was constructed using the system and applied to electrocardiogram prediction. The purpose of this paper is to prove the validity of the predictor for electrocardiogram. The neuron networks in the system were trained 30,000 cycles. As a result, averages of root mean square errors of the first neuron network was 2.60×10-2, and that of the second neuron network was 1.17×10-5. Prediction without error was attained by this predictor, so that its validity was confirmed. Keywords: Volterra neuron network, Predictor, Error free, Electrocardiogram. 1. Introduction A neuron network (NN) cannot be learned if there is not a correlation between input signals to each layer and teacher signals of it. Therefore, uncorrelated components between them cannot be learned when correlated and uncorrelated components intermingled between them. NN cannot learn completely correlated components between them when learning capability of NN is low. Elevating learning capability of NN as a means to learn completely these correlated components is thought. However, such NN has not existed. Various researches have been actively done to elevate output accuracy of NN up to now. Improvements on the I/O characteristics of a neuron [1-11,17], the structure of NN [13-23] and NN system [24] are effective as means of the output accuracy elevation. However, output errors of their NNs cannot converge at zero, even if trainings for their NNs are iterated many times. Therefore, usual NNs are used with output error in tolerance. However, it is insufficient when applying NN to predictive coding [10-12] and the flight control for an aircraft [18,19] and a spacecraft etc. which smaller output error is advisable. Then, NN system with a possibility which this problem can be solved even with NN which learning capability is low if it is used by plural has been proposed. As a result, “Error Convergence Method for Neuron Network System (ECMNNS)” which output error of single output NN system using NNs of multi-step converges and “Error Convergence Neuron Network System (ECNNS)” which is designed using it have been proposed by S. Kobayakawa [25]. The output error is theoretically converged at zero by infinitely increasing the number of NNs in ECNNS. However, it is necessary to devise ECNNS when it is used as plural outputs, for ECNNS is a single output. The highest output accuracy of NN system cannot be expected for even if ECMNNS is simply applied to BP network (BPN) [26], because the BPN has the mutual interference problem of learning between outputs [18-22]. Then “Error Convergence Parallel-type Neuron Network System (ECPNNS)” which ECNNS was applied to a parallel-type NN which does not have the above-mentioned problem and which outputs accuracies are high to deal with plural outputs has been designed. Furthermore, “Error Convergence-type Recurrent Neuron Network System (ECRNNS)” which ECNNS was applied and “Error Convergence Parallel-type Recurrent Neuron Network System (ECPRNNS)” which ECPNNS was applied also have been designed. It is theoretically shown that output accuracy of NN system is elevated by them. In general, BPN which learns a time series signal using a teacher signal and input signals is that two teacher signal values or more occasionally correspond to same values of input signals. In such a state, the BPN cannot be used for ECNNS because it cannot be learned. There are means using input-delay NN and Volterra NN (VNN) to eliminate this problem. These means are used for usual researches on compression for nonlinear signal using predictive coding [10,27]. Learning for a nonlinear predictor using NNs is easier by strengthening of causality between signals from past to present and a prediction signal. Therefore, Learning for NN at the first step in ECNNS is comparatively easy. However, learning for NN at high step in ECNNS is difficult because the causality weakens by rising of steps in ECNNS. Then, ECNNS is redesigned for improvement on learning capability. The redesigning is that NN at each step in ECNNS can be used as a predictor to strengthen causality between an input signal and a teacher signal of it. As a result, predictor using ECNNS [28] has been designed. This is called “Error Convergence-type Predictor (ECP)” The purpose of this paper is to prove the validity of ECP with rounding which is constructed of 2nd-order VNNs (2VNN) of two steps for a normal sinus rhythm electrocardiogram (ECG). This ECP is called “Error Convergence-type 2nd-order Volterra Predictor (EC2VP)”. As a result, prediction without error was attained by this predictor, so that its validity was confirmed. 2. Single Output Error Convergence-type Neuron Network System 2.1 Principle Here, it thinks about a single output NN which error of the output signal to a teacher signal does not converge at zero though it becomes smaller than one before training for the (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 15 NN under the result of executing until the training converges to all input signals with correlation between the teacher signal. The training is executed by this NN at the beginning. Next, other training is executed by another NN using an error signal obtained from an output signal and a teacher signal of the NN as a teacher signal. Thus it is thought that an error of an output signal to a teacher signal cannot be converged at zero, even if it is kept training an error signal obtained from training of previous NN one after another by another NN. That is, the error obtained from a difference between the sum of the output signals of all NNs and the teacher signal of the first NN does not converge at zero. This is shown in expressions from (1) to (4). i i i y z e = + ( ) 1, 2, , i n = L (1) 1 i iy e + = ( ) 1, 2, , 1 i n = - L (2) 1 1 n i n i y z e = = + å (3) lim 0 n n e ¬¥ ¹ (4) where y is the teacher signal, z is the output signal, ε is the output error, suffix of each sign is steps of NN. Moreover, trainings for error signals used as a teacher signal for NN at the second step or more become difficult because it is thought that error signals become small along with the number of steps. Error signals which are amplified are used for teacher signals to NN at the second step or more to improve this problem. As a result, these trainings become easy. An output error of NN after training is reduced when it is restored to signal level before the amplification, if the amplification factor is larger than 1. Moreover, it approaches zero when the amplification factor is very large. Here, an output error obtained from training under an amplification factor of an error signal which is a teacher signal to NN at the n step as An is assumed to be ε. Output error εn to a teacher signal given to a whole of NN system is shown like expression (5) and (6). Moreover, it is shown like expressions (7) and (8) when steps of NN are infinitely, and the output error converges at zero. Therefore, an error obtained from a difference between a sum of output signals after restoration of all NNs and the teacher signal given to the whole of NN system converges at zero from expressions (3) and (8) when the steps of NN are infinitely, and they become equal. This is shown in expression (9). Thus, this means to improve the above-mentioned problem is effective and necessary to obtain highly accurate output. This means is called ECMNNS, and NN system which applies this is called ECNNS. n n Ae e = (5) ne e < (6) lim n n A ¬¥ = ¥ (7) Training Extracting the error Gain tuning to the teacher signal Spreading the error Restoration to an output signal Sum of restored output signals Iteration until the error converges at zero + -Teacher signal to ECNNS Figure 1. Concept of processing for error convergence-type neuron network system lim 0 n n n Ae e ¬¥ = = (8) 1 lim n i n i y z ¬¥ = = å (9) 2.2 Single Output Neuron Network System Figure 1 shows a concept of processing for ECNNS. Figure 2 shows that ECNNS is designed based on this concept. Symbol NN in this figure also contains the state of a neuron. This ECNNS can be built in freely selected NN and the learning rule of the processible type for the I/O relation which internal each NN should be achieved. Here, the general I/O characteristics of ECNNS are discussed without touching concerning the I/O characteristic of NN concretely applied to ECNNS. ECNNS equips with amplifiers to tune amplitudes of input signals and a teacher signal to NN at each step, to execute the appropriate training. Furthermore, ECNNS also equips with amplifiers for restoration which amplification factor is a reciprocal of an amplification factor for amplification of the teacher signal to each NN on its output part, to restore its output signal level. The I/O characteristics of ECNNS are shown in expressions from (10) to (16). Moreover, the relation of their teacher signals is shown in expressions from (17) to (20). Here, conditions of the amplification factors used by expressions (16), (18) and (19) are expressions (21) and (22). ( ) in 1 2 , , , x n x x x = L (10) ( ) in in 1 2 , , , Ai i i in a a a = L ( ) 1, 2, , i n = L (11) Aij ij j x a x = ( ) in 1, 2, , ; 1,2, , i nj n = = L L (12) ( ) in 1 2 , , , i Ai Ai Ain x x x = x L ( ) 1, 2, , i n = L (13) ( ) x Ai i i z f = ( ) 1, 2, , i n = L (14) (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 16 --+ + -+ -+ ---11 n i i z -= å A2 1/A2 1/A3 A3 1/An An 1/A1 -+ A1 + ++ Ain2 Ain3 Ainn NNn x Ain1 1 x2 x3 xn x 1 e2 e3 en e 1 A z 1 A y 2 A z 3 A z An z 1 z 2 z 3 z 2 A y 3 A y n z An y yz ++ + + NN1 NN2 NN3 2 y 3 y n y 1 y Figure 2. Error convergence-type neuron network system 1 n i i z z = =å (15) Ai i i z z A = ( ) 1, 2, , i n = L (16) 1y y = (17) 1 1 1 A yAy = (18) 11 i Ai i j j y A y z -= æ ö = - ç ÷ è ø å ( ) 2,3, , i n = L (19) i Ai Ai y z e = - ( ) 1, 2, , i n = L (20) 0 i A¹ ( ) 1, 2, , i n = L (21) lim n n A ¬¥ = ¥ (22) where x is the input signal vector, x is the input signal, xAi is the input signal after amplification at the ith step, xi is the input signal vector after amplification at the ith step, Aini is the input signal amplification factor vector at the ith step, ai is the input signal amplification factor at the ith step, suffixes of x, xAi and ai are input signal numbers, zAi is the output signal of NN at the ith step, fi is a nin variables function which shows the I/O relation of NN at the ith step, y is the teacher signal to ECNNS, z is the output signal of ECNNS, yAi is the teacher signal to NN at the ith step after amplification, zi is the output signal to NN at the ith step after restoration, Ai is the teacher signal amplification factor for NN at the ith step, εi is the output error of NN at the ith step. x ECNNS1 ECNNS2 y1 z1 y2 z2 ECNNS3 y3 z3 ECNNSm ym zm Figure 3. Error convergence parallel-type neuron network system 3. Plural Outputs Error Convergence-type Neuron Network system 3.1 Principle ECNNSs are applied to the parallel-type NN when applying ECNNS to a plural outputs NN system, for ECNNS is a single output. NN system of this type is called ECPNNS. Moreover, it can be said a general type of ECNNS. Figure 3 shows ECPNNS. This is constructed of parallel units which apply ECNNS of the same number as the outputs. Therefore, it is thought that high output accuracy is obtained, because the mutual interference problem of learning between outputs of BPN is not caused either, for training for each output is executed independently by ECNNS. 3.2 Plural Outputs Neuron Network System I/O characteristics of ECPNNS are shown in expressions from (23) to (28). Moreover, relation of teacher signals is shown in expressions from (29) to (32). Here, conditions of amplification factors used by expressions (28), (30) and (31) are expressions (33) and (34). ( ) in in 1 2 , , , Aij ij ij ijn a a a = L ( ) 1, 2, , ; 1, 2, , i i m j n = = L L (23) Aijk ijk k x a x = in 1, 2, , ; 1,2, , 1, 2, , i i mj n k n = = æ ö ç ÷ =è ø L L L (24) ( ) in 1 2 , , , ij Aij Aij Aijn x x x = x L ( ) 1, 2, , ; 1, 2, , i i m j n = = L L (25) ( ) x Aij ij ij z f = ( ) 1, 2, , ; 1, 2, , i i mj n = = L L (26) 1 i n i ij j z z = =å ( ) 1, 2, , i m = L (27) Aij ij ij z z A = ( ) 1, 2, , ; 1, 2, , i i mj n = = L L (28) 1i i y y = ( ) 1, 2, , i m = L (29) 1 1 1 Ai i i y A y = ( ) 1, 2, , i m = L (30) (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 17 11 j Aij ij i ik k y A y z -= æ ö = - ç ÷ è ø å ( ) 1,2, , ; 2,3, , i i m j n = = L L (31) ij Aij Aij y z e = - ( ) 1,2, , ; 1, 2, , i i m j n = = L L (32) 0 ij A ¹ ( ) 1, 2, , ; 1,2, , i i mj n = = L L (33) lim in n A ¬¥ = ¥ ( ) 1, 2, , i m = L (34) where the first figure of suffix of each sign is the parallel unit number, the second figure of it is the step number in ECNNS, the third figure of it is the input signal number. However, xk is the kth input signal to ECNNS. 4. Applications 4.1 Simulator Here are two application network systems using ECNNS and ECPNNS. For example, control signals and state signals are necessary for input when achieving a simulator for nonlinear plant. Furthermore, the state signals output from the simulator every moment decided depending on the input signals are recurrently needed for the state input signals. When achieving the simulator with high accuracy, it is advisable that errors are not included in output of the simulator. Therefore, it is thought that the simulator which works by the specified significant figure obtains a highly accurate output by the plant model using ECNNS and a rounding to eliminate the output error. Concretely, the network system which the output signal of ECNNS recurs to the input through a rounding shown in Figure 4 is thought about the simulator in case of a state signal. This is called ECRNNS. Furthermore, the network system which output signal vector of ECPNNS recurs to the input through roundings as shown in Figure 5 is thought about the simulator in case of plural state signals. This is called ECPRNNS. In these figures, y is the teacher signal vector, and z is the output signal vector. 4.2 Nonlinear Predictor A nonlinear predictor used for predictive coding and its principle must be improved to obtain high accuracy. Here is a means for improvement on learning capability of NN at each step in ECNNS for a nonlinear predictor used for predictive coding. This is called ECP. Learning for a nonlinear predictor using NNs is easier by strengthening of causality between signals from past to present and a prediction signal. Therefore, learning for NN at the first step in ECNNS is comparatively easy. However, learning for NN at the high step is difficult because it is guessed that the causality weakens by rising of the steps. Then, NN at each step in ECNNS is used as a predictor to strengthen causality between input signals and a teacher signal of it. Moreover, learning capability of the NN can be elevated by increasing the number of input signals [29]. Figure 6 is redesigning of ECNNS in Figure 2 to realize it. Furthermore, expression (13) is changed to expressions from (35) to (38). Expression (37) shows initial conditions for NNs from the second step. I/O relations of NNs in ECP are shown in expression (39). An output signal of ECP is shown in expression (40). A teacher signal to ECP is shown in expression (41). ( ) ( ) ( ) ( ) ( ) in 1 11 12 1 , , , A A A n x x x t t t t = x L (35) ( ) ( ) ( ) ( ) ( ) ( ) in in 1 2 , , , , i i ij Ai Ai Ain Ae x x x x t t t t t = x L ( ) in 2,3, , ; 1,2, , i n j n = = L L (36) ( ) 0 ij x t = ( ) in 0; 2,3, , ; 1, 2, , i n j n t£ = = L L (37) ( ) ( ) ( ) 1 1 1 i ij j k k x x z t t t - - = = -å in 0 2,3, , 1, 2, , i n j n t > æ ö ç ÷ = ç ÷ ç ÷ = è ø LL (38) ( ) ( ) ( ) Ai i i z f t t = x ( ) 1, 2, , i n = L (39) ( ) ( ) 1 ˆ j z x t t+ = ( ) in 1, 2, , j n = L (40) ( ) ( ) 1 j y x t t+ = ( ) in 1, 2, , j n = L (41) where xij is the input error signal at the ith step to input signal xj to ECP, Aeini is an amplification factor of the input error signal at the ith step, Ai is an amplification factor of the teacher signal at the ith step, fi is the nin variables function when i is 1 or the nin + 1 variables function when i is 2 or more to show I/O relation of NN at the ith step, ˆx is the prediction. 5. Computer simulations 5.1 2nd-order Volterra Neuron Network Figure 7 shows 2nd-order Volterra neuron (2VN) in discretetiime I/O characteristics of 2VN are shown in expressions from (42) to (44). ( ) ( ) ( ) 1 n i i i u w x t t t = =å (42) ( ) ( ) ( ) 1 0 ( ) ( ) ( ) ( ) 2 0 ( ) ( , ) Q p p Q Q p q p q p s p upq u u h t t t t t t t s s - = - - = = =+ - ååå (43) ( ) ( ) () 1 ( ) tan ( ) z fs A s t t t - = = (44) where u is the input weighted sum, xi is the ith input signal, wi is the ith connection weight, s is the input sum, D is the delay, Q is the prediction order, σ1 is the prediction coefficient of the 1st-order term corresponding to the signal obtained from between from an input of the 1st delay to an output of the Qth delay, σ2 is the prediction coefficient of the 2nd-order term corresponding to the product of all combinations of two sig (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 18 yz x ECNNS Rounding Figure 4. Error convergence-type recurrent neuron network system yz x Roundings ECPNNS Figure 5. Error convergence parallel-type recurrent neuron network system ( ) 3t e NN1 NN2 --+ + -+ -+ ---( ) 11 n i i z t -= å A2 1/A2 1/A3 A3 1/An An 1/A1 -+ A1 + ++ NNn ( ) t x ( ) 1t e ( ) nt e ( ) 1 A z t ( ) 1 A y t ( ) 2 A z t ( ) 3 A z t ( ) An z t ( ) 1 z t ( ) 2 z t ( ) 3 z t ( ) 2 A y t ( ) 3 A y t ( ) n z t ( ) An y t ( ) y t ( ) z t ++ + + ( ) 2t e +-+ -+ -Ainn ( ) 1t x ( ) 2t x ( ) nt x D ( ) 1 1 z t - D ( ) 1 2 z t - D ( ) 1 3 z t - ( ) j x t Ain2Ain3 ( ) 3t x NN3 ( ) 2 j x t ( ) 3 j x t ( ) nj x t Ain1 Aein2 Aein3 Aeinn ( ) 2 y t ( ) 3 y t ( ) n y t ( ) 1 y t Figure 6. Predictor using error convergence-type neuron network system nals included in combinations of the same signal obtained from between from an input of the 1st delay to an output of the Qth delay, h is the threshold, z is the output signal, f is the output function, A is the output coefficient. wi , h, σ1 and σ2 are changed by training. Figure 8 shows a three-layer 2VNN of one input one output which is constructed of 2VNs. This 2VNN is used for ECP. 5.2 Method (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 19 + ++ M M M M M M + + -+( ) h t ( ) s t ( ) z t f(・) ( ) 1 (0) t s ( ) 1 (1) t s ( ) 1(2) t s ( ) 1( ) Q t s ( ) 2 (0, 0) t s ( ) 2 (0,1) t s ( ) 2 (0, 2) t s ( ) 2(0, ) Q t s ( ) 2 (1,1) t s ( ) 2 (1, 2) t s ( ) 2 (1, ) Q t s ( ) 2 (2, 2) t s ( ) 2 (2, ) Q t s ( ) 2( , ) Q Q t s D D D ( ) Q ut- ( ) 1 u t - ( ) 2 u t - ( ) u t ( ) 1 wt ( ) 2 wt ( ) n wt ( ) 1 x t ( ) 2 x t ( ) n x t Figure 7. 2nd-order Volterra neuron Input Output ( ) it x ( ) Ai z t 2VN 2VN Figure 8. 2nd-order Volterra neuron network In computer simulations, EC2VP constructed of 2VNNs of two steps shown in Figure 9 is trained using combinations of an input signal x( τ) and a teacher signal y( τ) = x( τ+1) in the time series pattern of one dimension in space direction. The teacher signal is shown in Figure 10. This is a normal sinus rhythm ECG signal of MIT-BIH No.16786. This ECG signal is that the sampling frequency is 128 Hz, the significant figure is four-digit, the quantization step size is 0.005 mV, and the number of data for the input signal without an initial input and the teacher signal is 640, respectively. Here, training for 2VNN at each step in EC2VP is completed sequentially from the first step. At the beginning, 2VNN at the first step (2VNN1) is trained using combinations of an input signal x( τ) and a teacher signal y1( τ)=x( τ+1) in the time series pattern of one dimension in space direction. Here, computer simulations for the training are executed as A1=a11=1/3.275 according to the following procedure from 1) to 4). 1) A pair of the input signal or signals and the teacher signal is given once after 1,580 initial data are inputted into the 2VNN at the training. This process is defined as one training cycle. 2) Table 1 shows conditions for computer simulations to valuate prediction accuracy for the 2VNN. Initial values of prediction coefficients of the 2VNN are decided by exponential smoothing, and the other initial values are Rounding 2VNN12VNN2 --+ A2 1/A2 1/A1 -+ A1 ( ) 1t e ( ) 1 A z t ( ) 1 A y t ( ) 2 A z t ( ) 1 z t ( ) 2 z t ( ) 2 A y t ( ) y t ( ) z t + + ( ) 2t e +-( ) 11 A x t ( ) 2 x t D ( ) 1 1 z t - ( ) x t a21 ( ) 21 x ta11 ( ) 2 y t ( ) 1 y t ( ) 2 A x t ( ) 21 A x t Aein2 Figure 9. Error convergence-type 2nd-order Volterra Predictor -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0 Time [s] Voltage [mV] 5 4 3 2 1 0 0 Figure 10. Teacher signal used for training for error convergence-type 2nd-order Volterra predictor decided by pseudo-random numbers at the training process a time. Gradient descent method is used for learning rule for the 2VNN. The number of middle layer elements and filter length of the 2VNN has been decided by studying experiences of ECG prediction using 2VNN. 3) The trainings for searches are executed as a parameter to set a condition for the computer simulations which is the learning reinforcement coefficient. 4) Averages of root mean square errors (RMSEs) obtained from the searches of three times are compared. 2VNN achieved the minimum average of RMSEs by the searches is NN at the first step in EC2VP. A part of training signals to 2VNN at the second step (2VNN2) in EC2VP is an error signal obtained from a difference between an output signal of 2VNN1 and a teacher signal to EC2VP. Next, 2VNN2 is trained using combinations of input signals x21( τ) and x( τ) in the time series pattern of two dimensions in space direction and a teacher signal y2( τ)=x21( τ+1) in the time series pattern of one dimension in space direction. A signal to which gain tuning which adjusts the maximum absolute value of error signal to 1 is performed are used for xA2( τ) and yA2(τ). Here, computer simulations for the training are executed as Aein2=A2 and a21=1/3.275 according to the above-mentioned procedure from 1) to 4). (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 20 Table 1: Conditions for computer simulations to train 2nd-order Volterra neuron network at each step 10-5~1 10 times 30,000 3 -0.3~0.3 -0.3~0.3 Prediction coefficents 0.7×0.3p Training cycles Learning reinforcement coefficients Range Processing times Connection weights Thresholds Gradient-based method Initial conditions Filter length Interval σ2 σ1 Momentum 0 Output coefficents 1 0.7×0.3p×0.7×0.3q Learning roule Learning roule for Volterra neuron network Number of middle layer elements Steps The 1st step The 2nd step 4 69 10 64 Time [s] Voltage [mV] ] 5 4 3 2 1 0 0 0.2 1.0 -0.2 ×10-1 0.4 0.6 0.8 -0.4 -0.6 -0.8 -1.0 -1.2 Figure 11. Teacher signal for 2nd-order Volterra neuron network at the second step Training cycles 2VNN1 10-6 10-9 10-3 1 0 10,000 20,000 30,000 Evaluation function value 2VNN2 Figure 13. Relation between training cycles and average evaluation function values at the minimum average of root mean square errors concerning 2nd-order Volterra neuron network at each step Learning reinforcement coefficent RMSE Minimum (1.17×10-5) 10-1 1 10-2 10-3 10-4 10-5 10-1 101 10-2 10-3 10-4 10-5 N2VNN1 Minimum (2.60×10-2) N2VNN2 10-6 Figure 12. Averages of root mean square errors and their standard deviations to learning reinforcement coefficient in gradient descent method term -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0 Time [s] Voltage [mV ] 系列1 系列2 5 4 3 2 1 0 2VNN1 2VNN2 0 Figure 14. Output signal of 2nd-order Volterra neuron network at each step (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 21 Then, 2VNN achieved the minimum average of RMSEs by the searches is NN at the second step in EC2VP. An output of the 2VNN2 is restored at a level of the teacher signal to EC2V. The restored output signal is added to the output of 2VNN1 at the same time as it. Finally, the fourth decimal place of the output after the addition is rounded off. The obtained output is an output of EC2VP as a result. Its prediction accuracy is evaluated. 5.3 Results Results of computer simulations are shown in figures from 11 to 14. A result of making training signal for 2VNN2 is shown in Figure 11. Averages of RMSEs and their standard deviations obtained by the computer simulations for 2VNN at each step are shown in Figure 12. Fig. 13 shows a relation between training cycles and average of evaluation function values of 2VNN at each step which is recorded before beginning to train and at the first time and every 100 times of the training cycle when the minimum average of RMSEs is obtained by searches of three times. This figure shows that prediction errors when training for 2VNN1 is saturated can be decreased more by using 2VNN2. Moreover, gradient of average evaluation function value of 2VNN2 at 30,000 cycles is surmisable like being able to train more. Figure 14 shows output signal of 2VNN at each step. An output signal of EC2VP which is obtained as a result of adding output signals of 2VNN1 and 2VNN2, and rounding it. This signal is error free at all, and is equal to the teacher signal. Thus, complete learning accomplishment capability of EC2VP could be demonstrated. An excellent learning capability and validity of EC2VP to normal sinus rhythm ECG can be confirmed. 6. Discussion 6.1 Accuracy Up for Output and Speed Up for Training It is thought that a highly accurate output is obtained by ECNNS at a few training cycles because its error is converged by plural NNs. Here, error signal of NN at previous step which NN at final step uses to train is a very small signal if steps of NN are set infinitely. That is, sum of output signals of all NNs becomes a very highly accurate output signal because output error of NN at final step becomes equal in nil compared with a teacher signal to a whole of ECNNS. The training cycle as the whole of ECNNS can be theoretically one time when thinking only one datum is trained under this condition. For example, when the probabilistic descent method is used for learning rule for NNs in ECNNS, it is expected that a steady output signal is obtained at any training cycles because the highly accurate training can be executed every one datum as shown in the above-mentioned. Moreover, a component ratio of output signal of NN at each step to the output signal of ECNNS to grow large at more former step as the training cycle increases is thought. It is thought that learning capability of ECNNS is remarkable as steps of NN increases and the output accuracy and the training speed elevate. 6.2 Improvement on Learning Capability Capability of discrete-time neuron network (DTNN) is improved if sampling frequency of signal processed with DTNN is upped. However, there is a limit in such means to improve the capability of DTNN because the limit of the sampling frequency is caused by restriction to operating frequency fordigital circuit, memory capacity and data processing time of it. Moreover, the lowest sampling frequency to process efficiently data is decided by the sampling theorem. However, training for DTNN must be executed in a state which the data are increased by upping the sampling frequency if excellent training for DTNN is not obtained by the data. As a result, data processing for DTNN becomes no efficiency. Here, it is thought that learning capability of DTNN can be improved without upping the sampling frequency by ECNNS. 6.3 Instability Instability of ECP is how to process components of random signals which are included in inputs signal and teacher signals of ECP. There is a means which the random signals are processed as noises. This means eliminates these noises by filtering an input signal and a teacher signal to ECP as the preprocessing. There are Fourier transform, Bayesian model and trend model etc. [30] as the means which can be used. However, there is also necessary information like signals of nature, vital and economy etc. in the random signals. This means must be performed with attention so as not to miss the information. 6.4 Validity It thinks about training for 2VNN at the second step in EC2VP. ECP is an improvement on its learning capability by using NN which makes the causal relation between input signal and teacher signal available as an internal predictor in ECP to enable trainings for NNs from the second step where the trainings becomes difficult. Furthermore, two input signals are used for strengthening unique concerning the output signal to the input signal. Actual training also is shown excellent results, and the effect concerning the abovementtione to make easily to train is seen. It is thought that this is because a relation between the input signals and the teacher signal is a correlation. These computer simulations are insufficient as a demonstration for a highly accurate predictor because generalization capability to unlearning signals is not confirmed, though it demonstrated the complete learning accomplishment capability of EC2VP. Therefore, demonstrations for the generalization capability using ECGs of arrhythmia etc. are necessary. 7. Conclusions In this study, it was shown to obtain a highly accurate output by improving the learning capability using single output NNs which an error of an output signal to a teacher signal does not converge at zero though it becomes smaller than one before training under a result of executing until the training converges to all input signals with correlation between the teacher signal and which the inputs are common in style connected with multi-steps. This is a method which the error to the teacher signal of a whole of (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 22 NN system can be converged at a small value by amplifying an error signal obtained from NN at each step and training it as a teacher signal of NN at the next step one after another. Moreover, an error to a teacher signal of NN at the first step converges at zero by infinitely setting steps of NN. This method is called ECMNNS. It explained ECNNS applied this method and means to use by ECPNNS which ECNNS is applied to the parallel-type NN for NN of plural outputs. Furthermore, it also explained ECRNNS and ECPRNNS which can be expected to use as the simulator for a nonlinear plant as applications using ECNNS and ECPNNS. Moreover, ECP improved learning difficulty when there is little causality between input signals and a teacher signal to NN at each step in ECNNS by structuring NN at each step in ECNNS as a predictor and strengthening causality between the input signals and the teacher signal was designed. Using 2VNN for NN at each step in ECP was proposed. Finally, computer simulations to train EC2VP constructed of 2VNNs of two steps were executed using a normal sinus rhythm ECG signal, and prediction accuracy of EC2VP was evaluated. As a result, learning capability obtained an output without error, that is, ECP having complete learning accomplishment capability was demonstrated. To be a validity which can use EC2VP as a highly accurate predictor by this demonstration was confirmed. It can be said that ECNNS will have an enough capability to be the leading system of means to construct NN in the future because of excelling theoretically concerning accuracy up for output, speed up for training and improvement on learning capability of DTNN. On the other hand, an enough demonstration as a highly accurate predictor has been not able to perform because generalization capability to unlearning signals is not confirmed. The future work is demonstrating the generalization capability of EC2VP using ECG of arrhythmia etc. Acknowledgments We wish to express our gratitude to members in our laboratory who cooperate always in the academic activity. References [1] C. L. Giles and T. Maxwell, “Learning, Invariance and Generalization in High Order Neural Networks,” Applied Optics, Vol.26, No.23, pp. 4972-4978, 1987. [2] K. J. Lang and G. E. Hinton, “A Time-Delay Neural Network Architecture for Speech Recognition,” Carnegie Mellon University Computer Science Technical Report, CMU-CS-88-152, pp. 1-37, 1988. [3] T. Possio and F. Girosi, “Networks for Approximation and Learning,” Proc. of the IEEE, Vol.78, No.9, pp. 1481-1497, 1990. [4] S. Iwamoto, T. Yoshida and H. Yokoi, “Basic Investigation Associated with Neural Control of Biped Walking Robot,” Technical Report of IEICE, MBE93 -106, pp. 23-30, 1994. [5] Y. Fujisue, E. Inohira and H. Yokoi, “Robotic Control by Volterra Network,” Technical Report of IEICE, NC2003-78, pp. 39-43, 2003. [6] S. Uota and H. Yokoi, “A Realization of Motion Diversity of the Robotic Hand by the Hierarchical Motion Schema,” Technical Report of IEICE, NC2003-75, pp. 25-28, 2003. [7] J. Miyoshi and H. Yokoi, “An Improvement of a Neural Network for Learning a Slip Angle of a Four-Wheel Steering Car,” Technical Report of IEICE, NC2004 -107, pp. 87-90, 2004. [8] S. Shigemura, T. Nishimura and H. Yokoi, “A Method of Removing Blink Artifacts from EEG Signals Using Neural Networks with Volterra Filters,” Technical Report of IEICE, MBE2004-87, pp. 57-60, 2005. [9] S. Suematsu and H. Yokoi, “A Motion Generating System for Multi-Fingered Myoelectric Hand,” International Congress Series 1291, pp. 257-260, 2006. [10] S. Kobayakawa, T. Fujii and H. Yokoi, “Evaluation of Nonlinear Prediction Capabilities of Neuron Networks for Electrocardiogram,” Proc. of the 20th Annual Meeting of Biomedical Fuzzy Systems Association, pp. 9-12, 2007. [11] S. Kobayakawa, T. Fujii and H. Yokoi, “Evaluation of Prediction Capabilities of Neuron Networks Used for Electrocardiogram,” Proc. of the 5th International Symp. on Management Engineering, Kitakyushu, Japan, pp. 156-161, 2008. [12] S. Kobayakawa, T. Fujii and H. Yokoi, “Nonlinear Prediction for ECG by 2nd-order Volterra Neuron Network,” Journal of Biomedical Fuzzy Systems Association, Vol.11, No.2, pp. 101-111, 2009. [13] A. G. Ivakhnenko, “The Group Method of Data Handling-A Rival of the Method of Stochastic Approximation,” Soviet Automatic Control, Vol.13 c/c of Avtomatika, 1, 3, pp. 43-55. 1968. [14] A. D. Back and A. C. Tsoi, “FIR and IIR Synapses, A New Neural Network Architecture for Time Series Modeling,” Neural Computations, Vol.3, pp. 375-385, 1991. [15] M. Hoshino, T. Kitamura, T. Masuda, M. Suzuki and J. Chao, “On Multilayer RBF Networks and a Novel Pyramid Network,” Proc. of the Society Conf. of IEICE, Nagoya, Japan, p. 28, 2000. [16] N. Kinoshita and K. Nakamura, “Two-D Spreading Associative Neural Network Recognizes the Shape and Position of An Object Presented in the Two-D Space,” Technical Report of IEICE, NC97-166, Vol.97, No.623-624, pp. 209-216, 1998. [17] S. Kobayakawa and H. Yokoi, “The Volterra Filter Built-in Neural Network for the Aircraft Pitch Attitude Control,” The Lecture Proc. of the 2005 Fiscal Year Electricity Relation Institute Kyushu Branch Association Convention, Fukuoka, Japan, p. 429, 2005. [18] S. Kobayakawa and H. Yokoi, “Application to Prediction Problem of Parallelized Neuron Networks in the Aircraft,” Technical Report of IEICE, SANE2006-119 -133, Vol.106, No.471, pp. 43-45, 2007. [19] S. Kobayakawa and H. Yokoi, “Evaluation for Prediction Capability of Parallelized Neuron Networks,” Proc. of the 8th SOFT Kyushu Chapter Annual Conf., Kitakyushu, Japan, pp. 3-6, 2006. [20] S. Kobayakawa and H. Yokoi, “Evaluation of the Learning Capability of a Parallel-type Neuron Network,” Proc. of the First International Symp. on (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 23 Information and Computer Elements 2007, Kitakyushu, Japan, pp. 43-47, 2007. [21] S. Kobayakawa and H. Yokoi, “Experimental Study for Dominance to Accuracy of Prediction Output of Parallel-type Neuron Network,” Technical Report of IEICE, NC2008-1-10, Vol.108, No.54, pp. 29-34, 2008. [22] S. Kobayakawa and H. Yokoi, “Evaluation for Prediction Accuracies of Parallel-type Neuron Network,” International MultiConf. of Engineers and Computer Scientists 2009 Proc., Hong Kong, China, Vol.I, pp. 156-161, 2009. [23] H. Yokoi and T. Kimoto, “Multilayered Neural Networks with Intermediate Elements,” Journal of Biomedical Fuzzy Systems Association, Vol.1, No.1, pp. 87-97, 1999. [24] H. Sori and T. Yasuno, “Several-Hours-Ahead Wind Speed Prediction System Using Hierarchical Neural Network,” Journal of Signal Processing, Vol.12, No.6, pp. 507-514, 2008. [25] S. Kobayakawa and H. Yokoi, “Proposal of Error Convergence-type Neuron Network System,” Presented Proc. to 2008 International Symp. on Intelligent Informatics, Kumamoto, Japan, pp. 1-10, 2008. [26] D.E. Rumelhart, G.E. Hinton and R.J. Williams, “Learning Representations by Back-propagating Errors,” Nature, Vol.323, No.6088, pp.533-536, 1986. [27] A. Chatterjee, A. Nait-Ali and P. Siarry, “An Inputdeela Neural-Network-Based Approach for Piecewise ECG Signal Compression,” IEEE Transactions on Biomedical Engineering, Vol.52, No.5, pp. 945-947, 2005. [28] S. Kobayakawa and H. Yokoi, “Proposal of Predictive Coding Using Error Convergence-type Neuron Network System,” The Proc. of the ISCA 22nd International Conf. on Computers and Their Applications in Industry and Engineering, San Francisco, USA, pp. 169-174, 2009. [29] S. Kobayakawa and H. Yokoi, “Evaluation of Learning Capabilities of BP Networks to Number of Input Signals,” Technical Report of IEICE, SANE2007-102-124, Vol.107, No.442, pp. 83-86, 2008. [30] M. Onodera, Y. Isu, U. Nagashima, H. Yoshida, H. Hosoya and Y. Nagakawa, “Noise Filtering Using FFT, Bayesian Model and Trend Model for Time Series Data,” The Journal of Chemical Software, Vol.5, No.3, pp. 113-127, 1999. Authors Profile Shunsuke KOBAYAKAWA received the B.Eng. degree in 1986, accomplished credits for the master's course in 1989 in electrical engineering from Okayama University, Okayama, Japan, completed auditor in faculty of engineering in 1995 and received the M.Sc. degree in biological functions and engineering in 2003 from Kyusyu Institute of Technology (KIT), Kitakyushu, Japan, respectively. He has been working as a part-time lecturer at Research Course of Telecommunication System, Subaru Professional College in 2006, a research assistant since 2006 and a teaching assistant in 2008 at Graduate School, KIT. He also obtained Associate Professional Engineer in electrical and electronics engineering, First-Class Technical Radio Operator for On-The-Ground Services, Class I Information Technology Engineer and Aerospace Products Inspector etc. as national qualifications in Japan. He is a student of doctoral program, Department of Biological Functions and Engineering, Graduate School of Life Science and Systems Engineering, KIT and a director of KOBAYAKAWA Design Office at present. His present research interests include control for aerospace vehicles using neuron networks. He is a member of Biomedical Fuzzy Systems Association, The Japan Society for Aeronautical and Space Sciences, Information Processing Society of Japan, The Institute of Electronics, Information and Communication Engineers, and The Institute of Electrical and Electronics Engineers. Hirokazu YOKOI received the B.Eng. degree in 1972, the M.Eng. degree in 1974 in electrical engineering from Nagoya University, Nagoya, Japan, the D.M.Sc. degree in medicine in 1985 and the D.Eng. degree in electronics in 1989 from The University of Tokyo, Tokyo, Japan, respectively. He works as a professor of Department of Biological Functions and Engineering, Graduate School of Life Science and Systems Engineering, Kyusyu Institute of Technology, Kitakyushu, Japan at present. His present research interests include development of ultra large-scale neurochips and their applications to biped walking robots, intelligent assistive devices as well as automatic driving, and modeling of human cognitive processes with application to human-centered information equipments. He is a member of Biomedical Fuzzy Systems Association, Japan Society for Fuzzy Theory and Intelligent Informatics, The Institute of Electronics, Information and Communication Engineers, and Human Interface Society. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 24 Segmentation Method Based On Circular Edge Magnitude for Classification of Textures 1 Dr. A. Nagaraja Rao , 2K. Lavanya, 3G. Aruna Kumari, 4M.N. Hima Bindu 1 Professor, Dept. of IT, Lakireddy BaliReddy College of Engg. Mylavaram, Krishna Dt., A.P., India. nagarajarao.a@lbrce.ac.in 2 Asst. Prof., Dept. of IT, Lakireddy BaliReddy College of Engg. Mylavaram, Krishna Dt., A.P., India. lavanya.kk2005@gmail.com 3 Associate Prof., Dept. of CSE, Vidya Jyothi Institute of Tech., Moinabad, RR Dist, A.P., India. arunagullipalli@yahoo.com 4 Asst. Prof. Dept. of IT, Lakireddy BaliReddy College of Engg. Mylavaram, Krishna Dt., A.P., India. bindu.nov5@gmail.com Abstract: Texture segmentation is one of the most important techniques for image analysis, understanding and interpretation. The task of texture segmentation is to partition the image into a number of regions such that each region has the same textural properties. The present paper proposes a new segmentation method which is an alternative to non-maximal suppression based on edge magnitude. The relative edge magnitudes are calculated by considering the spatial information of 5X5 mask with 3X3 circular neighborhood masks. The central pixel under consideration in 5X5 mask is whether an edge pixel or not, can be identified by manipulating all the edge magnitudes from circular neighboring masks. The proposed method is applied on various Brodatz textures and the experimental results shows effective segmentation which is useful in classification of textures. Keywords: Texture, Segmentation, Edge, Magnitude, Non-Maximal Suppression, Neighborhood, Circular Mask. 1. Introduction Texture is defined as a pattern that is repeated and is represented on the surface of an object. Segmentation is a fundamental low-level operation on images and to separate textures into a single texture type, first we need to preserve spatial information for each texture. A homogeneous region refers to a group of connected pixels in the image that share a common feature. This feature could be brightness, color, texture, motion etc. For instance, the manual grey level thresholding which does not provide the spatial information for each texture [12] could generate inappropriate segmentation result. Depending on the number of images is known in advance, the techniques for image segmentation can be classified as supervised [1-3] or unsupervised [4-6]. Since in most of real applications the number of images is generally unknown, the unsupervised approach is considered more useful. There are three main classes of image texture segmentation that belong to the above two techniques. They are cluster-based, edge-based and regionbaase methods [7]. The edge-based segmentation exploits spatial information by detecting the edges in an image, which correspond to discontinuities in the homogeneity criterion for segments. Edges in a given depth map are defined by the points where changes in the local surface properties exceed a given threshold. The local surface properties mostly used are surface normals, gradients, principal curvatures, or higher order derivatives. Edge detection techniques used on texture image could result in noisy and discontinuous edges and therefore segmentation process becomes more complicated [13]. As edge detection methods look for abrupt changes, they are very sensitive to the noise in the range data. Moreover, as only the measurements near the edges are used to make major decisions, the available information is not optimally utilized. In many situations the edges do not form closed boundary curves and it can be difficult to make correct grouping decisions there by resulting in over or under segmentation. Some of the typical variations on the edge-based segmentation techniques are reported by many researchers [8, 10, 11]. The organization of this paper as follows: Section 2 gives the related work and the proposed method and algorithm described in section 3. Experimental results of texture segmentation using the circular edge magnitude are shown in the section 4 and section 5 gives the conclusions. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 25 2. Related Work In the edge image, no zero value edge pixels are present, but small edge values correspond to non-significant grey level changes resulting from quantization noise, small lighting irregularities. Simple thresholding of an edge image can be applied to remove these small values based on an image of edge magnitudes [14]. A problem with simple detector is the thickening that is evident where there should only be a simple boundary. This can be partially rectified if edges carry directional information by performing some form of non-maximal suppression to suppress multiple responses in the neighborhood of single boundaries [15]. In the proposed method, the maximum edge magnitude in 8-connectivity is calculated leading to the edge direction. The pixel under consideration in 3X3 window is displayed only if its grey level value is greater than the maximum of the two adjacent pixels of the edge direction. 3. Proposed Segmentation Method Edge based segmentation is one of the common approaches to segment the image and it remains very important over period of time. All edge based segmentation methods depend on edges identified in an image by any edge detection techniques. Edge based segmentation techniques differ in strategies and the necessary priori information is incorporated into those methods. Since the edge detection is very difficult in texture images when compared to image segmentation, the present study proposes the new technique which is based on relative edge magnitude in 5X5 neighborhood using circular rotating masks and the procedure and algorithm is described as follows. A practical method that has chosen in the present approach is to determine whether a central pixel is an edge pixel or not depending on its neighboring rotating masks inside the running window, in horizontal, vertical, right diagonal and left diagonal directions. Note that, since the proposed method checks the relative Difference of Edge Magnitude (DEM) values of rotating masks using 5X5 window as shown in Fig.1 instead of 3X3 window as applied in other methods. This will eliminate some false edge pixels on seemingly smooth regions. If any one of the maximum or average or minimum of the adjacent masks of maximum DEM value of rotating masks is less than the central pixel grey level value, the pixel is identified as being not located for segmentation. The stated method is explained in the following algorithm. (a) (b) (c) (d) Figure 1. (a),(b),(c) and (d) represents the rotating 3x3 masks that contain central pixel of 5x5 window in Horizontal(H), Vertical(V),Right Diagonal(RD) and Left Diagonal (LD) Directions. Algorithm 1. BEGIN. Step 1: Read the 5x5 window from original image. Step 2: Select circular 3X3 masks that contain the central pixel of a 5X5 window of the image as shown in Fig.1. Step 3: The sum of the grey levels of the circular masks are calculated. Step 4: The difference between the two Right Diagonal, Left Diagonal, and Vertical and Horizontal direction’s circular rotating masks are computed Step 5: To find edge, Maximum of the above differences is obtained and Central Pixel of 5X5 window is replaced by 1 iff any one of the adjacent differentiating masks maximum/mean/minimum grey level is greater than or equal to Central Pixel of the current 5x5 mask, otherwise the Central Pixel is replaced by 0. Step 6: Repeat step 1 to step 5 by 5X5 running window throughout the image. Step 7: Display the resultant segmented image. END. 4. Experimental Results The Brodat’z Texture Images, Plastic Bubbles, Straw, Pig Skin and Raffia, are taken to apply the proposed algorithm and these Textures are shown in Fig.2. The segmented texture images are shown, when all suppression parameters like maximum, mean and minimum, in Fig.4, 5 and 6 respectively. In Fig. 3, the segmented texture images of nonmaxxima suppression on 3X3 neighborhood are shown. For any texture classification, feature extraction is most important step. The proposed algorithm segments the textures by extracting the linear, horizontal and vertical edge features. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 26 The edge boundaries are extracted by non-maximal suppression in 5X5 neighborhood using the proposed algorithm and the segmented results are shown in Fig.4. Similarly the parameters like non-average and nonminnimu are suppressed in 5X5 neighborhood for segmentation and the results are shown in Fig.5 and Fig.6 respectively. Only the strong edge features are extracted when non-average method is applied and over segmentation, i.e. decomposing into more inner regions, is achieved when non-minimal suppression is applied. (a) (b) (c) (d) Figure 2. Original Brodatz Textures (a) Plastic Bubbles (b) Straw (c) Pig Skin (d) Raffia (a) (b) (c) (d) Figure 3. Segmentation results when non-maximum is suppressed in 8-connectivity. (a) Plastic Bubbles (b) Straw (c) Pig Skin (d) Raffia. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 27 (a) (b) ( c) (d) Figure 4. Segmented Images when Non-Max is considered using proposed method. (a) Plastic Bubbles (b) Straw (c) Pig Skin (d) Raffia. (a) (b) (c) (d) Figure 5. Segmentation results when non-average is suppressed in 8-connectivity. (a) Plastic Bubbles (b) Straw (c) Pig Skin (d) Raffia (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 28 (a) (b) (c) (d) Figure 6. Segmented Images when non-minimum is suppressed (a) Plastic Bubbles (b) Straw (c) Pig Skin (d) Raffia. 5. Conclusions Detecting edges and then eliminating irrelevant ones and connecting (grouping) the others are the key to a successful edge-based segmentation. The segmentation scheme exploited spatial information by detecting edges in an image that correspond to discontinuities in the homogeneity criterion for segment. As the mask size increases in texture segmentation by non-maximum and average suppression, noise reduces and the borders are more exact. The proposed segmentation algorithm proposed, is simple to implement and shows better results than the existing non-maximal suppression algorithm. From the Fig.4 and 5, the segmented results clearly show the local boundaries in all textures. By the technique of rotating mask, local boundaries in all directions are made clearly visible. The segmentation with continuous boundaries are more visible in Fig.4 when compared to Fig.3, Fig.5 and Fig.6. The segmentation results of textures indicate the domination of linear, circular and horizontal patterns. By the above topological patterns, one can classify textures easily. With the proposed segmentation method the classification of the textures based on topological structures becomes more effective. 6. Acknowledgements We would like to express our gratitude to the management of LBR College of engineering for providing facilities in the college. We are thankful to the Director, Dr. L.S.S. Reddy, who has given motivation and constant encouragement to complete this paper. Also we would like to thank Dr. R. Chandrasekaran and Prof. C. Nagaraju for their invaluable suggestions to improve the quality of this paper. References [1] D.Dunn, W. E. Higgins and J. Wakeley, Texture segmentation using 2-D Gabor elementary functions, (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 29 IEEE Trans. Pattern Analysis Mach. Intell. 16(2), 130-149 , 1994. [2] Y. M. Zhu and R. Goutte, Analysis and comparision of space/spatial – frequency and multi scale methods for texture segmentation, Opt. Eng. 34(1), 269-282(1995). [3] M. Unser, Texture classification and segmentation using wavelet frames, IEEE Trans. Image Process. 4(11), 1549-1560, 1995. [4] J. Mao and A. K. Jain, Texture classification and segmentation using multiresolution simultaneous autogressive models, Pattern Recognition 25(2), 173-188,1992. [5] Y. Hu and T. J. Dennis, Textured image segmentation by context enhance clustering, IEEE Proc. Vis. Image Signal Process. 141(6), 413-421, 1994. [6] J. L. Chen and A. Kundu, Unsupervised texture segmentation using multichannel decomposition and hidden Markov models, IEEE Trans. Image Process. 4(5), 603-619,1995. [7] R.C. Gonzalez, and R.E.Wood,.. Digital Image Processing., Wesley Publishing Company, pp. 458-461,2002. [8] O.R.P.Bellon, A.I. Direne, and L. Silva, Edge detection to guide range image segmentation by clustering techniques. In: International Conference on Image Processing (ICIP ’99), Kobe, Japan, pp. 725–729, 1999. [9] X. Jiang, A. Hoover, G. Jean-Baptiste, D. Goldgof, K. Boywer, and H. Bunke, A methodology for evaluating edge detection techniques for range images. In: Proc. Asian Conf. Computer Vision, pp. 415–419, 1995. [10] A.D. Sappa, and M. Devy, Fast range image segmentation by an edge detection strategy. In: Third International Conference on 3-D Digital Imaging and Modeling, pp. 292–299, 2001. [11] M.A. Wani and H.R. Arabnia, Parallel edge-regionbaase segmentation algorithm targeted at reconfigurable multiring network. Journal of Supercomputing 25(1), pp. 43–62, 2003. [12] C.E. Honeycutt and R. Plotnick , Image analysis techniques and gray-level co-occurrence matrices (GLCM) for calculating bioturbation indices and characterizing biogenic sedimentary structures, Computers & Geosciences 34, pp. 1461-1472, 2008. [13] S. Zheng, J. Liu and J.W. Tian, A new efficient SVMbaase edge detection method, Pattern Recognition Letters 25, pp. 1143-1154, 2004. [14] A. Kundu, Mitra, A new algorithm for image edge extraction using a statistical classifier approach. IEEE Transactions on Pattern Analysis and machine Intelligence, 9(4): 569-577, 1987. [15] Milan Sonka, Vaclav Hlavac and Roger Boyle, Image Processing,Analysis and machine vision, Second Edition, Vikas publishing House,pp. 135-137,2001. Authors Profile Agastyaraju NagarajaRao received the M.Sc. (Computer Science) Degree from S.V. University in 1999. He received his Ph.D. degree in Computer Science from University of Mysore in 2009. He is having 10 years of teaching experience at graduate and postgraduate level. Present he has been working with LBR college of Engineering, Mylavarm, as a professor in Department of IT. He has published more than 6 international journal papers, 14 national and international conferences. His research interests include Image Processing, Pattern Recognition, Data Mining and Texture Segmentation. He is a life member for CSI and ISCA. K. Lavanya completed her B.Tech. (CSE) From JNT University. Now she is pursuing her M.Tech. (CSE) from JNT University, Hyderabad. Currently she is working as Assistant Professor in department of IT, LBR College of Engineering, Mylavaram. She has overall 5 years of teaching experience at graduate level. Presently she is doing her project in image processing. G.Aruna kumari received B.E. degree in Electronics and Communication Engineering from Andhra University in 1995, and also in 1999 she obtained M.Tech degree in Computer Science and Technology from the same university. She has 10 years of teaching experience at graduate and postgraduate level. She is pursuing Ph. D. (CS) from Jawaharlal Nehru Technological University, Hyderabad, in the field of image processing. Her research interests include of image processing and pattern recognition. M.N.Hima Bindu completed her B.Tech (CSIT) from JNT University,Hyderabad. She is Pursuing M.Tech. (SE) From JNT University, Kakinada. She has been working as Assistant Professor in department of IT, LBR College of Engineering, Mylavaram. She has 4 years of teaching experience at graduate level. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 30Design of a 3.3GHz Band Application LC VCO for Low Phase noise and Low power Using Current Mirror Namrata Prasad1, R. S. Gamad2 1Electronics & Instrumentation Engineering Department, SGSITS, 23, Park Road, Indore, M.P., India – 452003 namrata.prasad7@gmail.com 2 Electronics & Instrumentation Engineering Department, SGSITS, 23, Park Road, Indore, M.P., India – 452003 rsgamad@gmail.com Abstract: In this paper a novel methodology is used to implement an LC tank Voltage Controlled Oscillator (VCO) with low power consumption, low phase noise and low tuning range. Here a relationship between, the phase noise, power consumption and the bias current is fully analyzed to improve the performance of VCO. The present design architecture of VCO has employed two current mirrors one at the top and other at the bottom end of cross coupled VCO, to balance the impedance and gives exact replica of current in both the arm of current mirror circuit. The phase noise measured is -148.59dBc/Hz at 3.3GHz carrier frequency with offset voltage of 1V. It will consume power of 5.68mW and the bandwidth is 4.31GHz, It also has the tuning range of 1.82%. From the simulation results we have seen that the power consumption, phase noise has reduced with current mirror. Finally we have compared the results with the earlier published work and got improvement in the present results as given in table 1. Keywords: LC-VCO, current mirror, cadence, low power, low phase noise. 1. Introduction Voltage Controlled Oscillators (VCOs’) are used in wireless application. It is one of the most significant block for the Radio Frequency (RF) communication system because it define all the performance parameter of the system with the rapid development of RF communication application in the field of cellular telephony, codeless phone, wireless data networks, two way paging etc. the performance parameter Low phase noise, Low power consumption and wide tuning range are the basic requirement which are interrelated and for the better system performance a tradeoff has to be achieved among these crucial requirements [1].There are mainly two confurigation of cross coupled VCO. Here, complementary cross coupled VCO is used to achieve Low phase noise, in RF communication phase noise is reduced by the drawback of high power because it degrade the system integrity by reducing the signal integrity of the output of a transceiver. Therefore by proper analyzing the circuit with well controlled current flow a low phase noise and a Low power consumption is obtained [2]. The paper is described in following section 2. Briefly described the analysis and design of cross coupled VCO, section 3 describe the proposed VCO with the addition of current mirror at the top and bottom end of the VCO architecture. The result is presented in section 4. And finally the conclusion is presented in section 5. 2. Design and analysis of cross coupled VCO The core component of the VCO consists of cross coupled PMOS and NMOS that is (M1, M2) and (M0, M3) from VCO core to generate a negative resistance to cancel the loss in the LC tank. It consists of a tail current mirror to provide bias current in a design. A typical resonance frequency of cross coupled VCO is given by [5]: 1 2 osc F LC p = (1) Where, L is the inductor in Henry of LC tank and C is the capacitance. The passive element i.e. the on-chip spiral inductor L and the two capacitor forms the frequency tuning network and Vcon is the controlled voltage. In case of a single current mirror the impedance is unbalanced resulting in different currents in the mirror arms which increase the power consumption and also has a negative effect on the phase noise performance of the circuit. Figure 1 shows schematic view of the earlier VCO design without using current mirror [5]. To overcome this problem we have used current mirror in the proposed VCO design. Figure 1. Schematic view of the earlier VCO design 3. Proposed VCO Design (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 31 In order to reduce the power consumption, phase noise, tuning range because they are the key parameter for the performance of a transreceiver system. In the proposed VCO design the top and bottom current controlled architecture is employed i.e. current mirror which balance the impedance in both the arm of circuit and hence the current become the exact replica of the bias current. In this design a current controlled mechanism is used to reduce even harmonics in the drain current which has a direct impact on the phase noise component which results reduction in phase noise it also achieves the negative resistance from the active devices by drawing minimum amount of current from the supply and reducing the power consumed by the circuit. Here, novels current controlled architecture is used to shift the wave form and control shape of the output waveform by adjusting the transistor sizes for the current mirror. The new proposed design schematic is presented in fig. 2 . Figure 2. Schematic view of the present VCO design To reduce phase noise and power consumption, we have used current mirror architecture in our proposed design in cross coupled form. Phase noise is most important parameter in VCO design therefore; phase noise performance is optimized by using lessons’ formula [4]. 2 2 0 2 2 ( ) 10log [1 ( ) ](1 ) 2 2 c vco m m av f f KTRK fKT L FM fQ f P f m ì ü = + + + í ý î þ (2) Where, L (FM) phase noise in dBc/Hz, Fm is the frequency offset from the carrier in Hz, f0 is central frequency in Hz, fc is flicker noise corner frequency in Hz, Q is the loaded quality factor of the tuned circuit, F is noise factor, K is Boltzmann's constant in J/K, T is temperature in K, Pav is average power at oscillator output, R is the equivalent noise resistance of the varactor and Kvco is oscillator voltage gain in Hz/V. From equation (2), Kvco dominates the phase noise performance in the modified Lesson's formula, thus phase noise performance can be improved by reduction Kvco. Maximum d. c. power dissipation= (Vsupply ) x (Ibias ) (3) Tuning range can be determined as follows [5]: 0max 0min 0 % 100 W W Tunningrange x W- = (4) Where, W0max is the maximum frequency of operation, W0min is the minimum frequency of operation and W0 is the frequency of operation. 4. Simulation result and discussion This work is carried under the environment of cadence software and schematic editor is used for design entry. In this design we have used specter RF simulator for Simulation, by using TSMC 0.18µm technology. The design is simulated with different architecture i.e. without current mirror, with tail current, and with current mirror. The applied voltage is 2V at the center frequency of 3.3GHz, with the Bandwidth of 4.31GHz. We have compared our simulation results with earlier work done and got improvement in this reported results and are shown in the table 1. Simulated output voltage responses of the present design are presented in fig. 3 and 4. Phase noise is given in fig. 5. Figure 3. Simulation result of the output voltage (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 32 Figure 4. Simulation AC response of the output Voltage Figure 5. Results of the Phase noise Table 1: Comparison of present results with earlier Work done Parameters Ref. [6] With tail current mirror only [5] This design Without current mirror With current mirror Operating Voltage 2V 2V 2V 2V Technology (CMOS) 0.35µm (TSMC) 0.18µm (UMC) 0.18µm (UMC) 0.18µm (UMC) Power consumption (mW) 18 15.76 8.69 5.68 Operating Frequency 6GHz 3.3GHz 3.3GHz 3.3GHz Tuning Range 17% 3.207% 29.8% 1.82% Phase Noise (dBc/Hz) -94 -151 (mdB/Hz) 69.63 -148.59 Bandwidth (GHz) --1.611 4.31 5. Conclusion In this paper, we have presented a novel, low phase noise, low power Cross coupled VCO using 0.18µm UMC technology. The proposed VCO will consume 5.68mW of power at 2V supply and achieves the phase noise of -148.59dBc/Hz at 3.3GHz and the tuning range is 1.82%. The result shows that the power consumption is reduced by 10% as compared to the design with tail current. Here we have used the technique for balanced the impedance in the circuit for better result. Present VCO design will become more useful where the low phase noise and low power consumption are the main requirements. Finally present results are compared with the earlier reported work and got improvement in this reported results as given in table 1. Acknowledgment This work has been carried out in SMDP VLSI laboratory of the Electronics and Instrumentation Engineering department of Shri G. S. Institute of Technology and Science, Indore, India. This SMDP VLSI project is funded by Ministry of Information and Communication Technology, Ref. Technology (CMOS) Government of India. Authors are thankful to the Ministry for the facilities provided under this project. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 33 References [1] P. Dudulwar, K. shah, H. Le, J. Sing, “Design and Analysis of Low Power Low Phase Noise VCO”, International Conference Mixed Design 2006. [2] Lin Jia, Jian-Guo Ma, Kiat Seng Yeo, Manh Anh Do, “A Novel Methodology For The Design Of LC Tank VCO With Low Phase Noise”, IEEE International Symposium On circuit systems, Vol.1, 23-26 May 2005, pp. 376-379. [3] Maria del Mar Hershenson, Ali Hajimiri and Sunderarajan S. Mohan, Stephen P. Boyd, Thomas H. Lee, “Design and Optimization of LC oscillator”, 1999 IEEE/ACM International Conference on Digital Object Identifier,7-11 Nov. 1999 pp. 65-69. [4] R. M. Weng and J. Y. Lin, “A 2.4GHz Low Phase noise Voltage Controlled Oscillator”, Department of Electrical Engineering, National Dong Hwa University, Taiwan, R.O.C. PIERS Proceedings, Beijing, China, March 23-27, 2009. [5] Namrata Prasad, R. S. Gamad and C. B. kushwah, “Design of a 2.2-4.0 GHz Low Phase Noise and Low Power LC VCO”, International Journal of Computer and Network Security Vol.1, N0.3, 2009, pp. 15-18. [6] B. Razavi, “A study of phase noise in CMOS oscillator” IEEE Journal of Solid-State circuits Vol. 31. no.3, Mar.1996, pp. 331-343. Authors Profile Namrata Prasad received the B. E. Degree in Electronics and communication Engineering. From S.A.T.I. Vidisha in 2008 and pursuing M.Tech degree in Microelectronics and VLSI Design from S.G.S.I.T.S. Indore, India in 2008-2010. Recently she is working with a project on VCO design and analysis. R. S. Gamad received the B. E. in Electronics & Communication Engineering from V. University, India in 1995 and M.E. degrees in Digital Techniques & Instrumentation Engineering with honors from Rajiv Gandhi Technical University Bhopal, India in 2003. He has been working in teaching and research professions since 1996. He is now working as Asst. Prof. in Department of Electronics & Instru. Engineering of S. G. S. I. T. S. Indore, India. His interested field of research is Dynamic testing of A/D Converter, Design of an A/D converter and communication. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 34 New protocol to increase the reliability in WSNs Ali HosseinAlipour1, Habib Moti Ghader 2, Mojtaba GorbanAlizadeh3 1 Islamic Azad University-Tabriz Branch, Iran Ali.Hosseinalipour@yahoo.com 2 Islamic Azad University-Tabriz Branch – Young Research Club, Tabriz, Iran habib_moti@yahoo.com 3 Sama organization(offilated with Islamic Azad University)-khoy Branch, Iran Mojtaba.khoy@gmail.com Abstract: During the recent years we observe the use of wireless sensor networks in applications like phenomenon management, Battlefield Recognition, guardianship of borders and safe observing. Considering that all these distributions were randomly and data-based protocols work properly in these methods. In this article we have proposed new algorithms with automatic learning. As the results show in new algorithm networks lifetime increases and reliability increases as well. Keywords: Data-Centric protocol, Reliability, Network lifetime, Wireless Sensor Networks 1. Introduction Recent improvements in complex integrations (IC) have made a new generation of micro called Sensors. That from economical aspect they are commodious and also they are used in two military groups and non military [2, 3]. To consider having group of limitations such as battery life time, calculating and memory significantly they have been predicted as non recyclable and also they live until their powers fade away. So power is something rare for systems like sensor. During a special mission the correct consumption for sensors lifetime should be managed knowingly [1]. Considering the use of sensor networks, fault tolerance is something important for them. This importance especially in uses like military and nuclear laboratory is seen significantly. Whereas I such environments information are really vital, first it's necessary to deliver the information to destination. And the second is to deliver the correct information. Because deciding on the basis of incorrect information in worse than not to decide. the main focus of most researches in this field has been tend to fault tolerances which during them nodes are completely corrupted and less efforts have been done for incompatible errors. Data incompatibility errors happen due to changes in binary contents when it is processing. In this article we mix three protocols TinyLAP and FDDA. In a manner that we increased the lifetime of the network and reliability by TinyLAP and other automatic learner called FDDA. And also we corrected the incompatibility errors. In the next part done works are showed and in the third part proposed protocol has been explained and ultimately in parts 4 and 5 simulation and conclusion are mentioned. 2. Related works 2.1 TinyLAP protocol In this part TinyLAP protocol [7] which is based on our proposed protocol is going to be partly explained. In TinyLAP protocol we allocate a Learning Automata for each node. And they use this for routing the appropriate path with their own circumstance. TinyLAP protocol includes two levels, "Distribution" and "Routing and learning”. Distribution level starts by the node which has a data to be sent. The node makes a stack called FLOOD and sends it to its neighbor. This stack includes data attributes that is very low-sized .and Neighbors by receiving this stack send to their neighbors again. When the Base Station (Sink) receives the FLOOD stack, makes another stack called FEEDBACK and distributes it through the network. And when nodes receive this stack add the new path to their table and distribute it. This level finishes by approaching the FEEDBACK stack for all the nodes in the network. At the end of this level any node has diverse paths to the central station. Each potential node for choosing the path evaluates according to 1-2 relation. In this relation i h is the number of steps to Sink for the ith and ngh is the number of paths in the routing table. Each node is armed to a learning automata its actions is equal with amount of paths exist in that node to the base stationand possibility of choosing each action is equal with probability of choosing the opposite path by that action in the routing table. In fact, Learning Automata actions have one to one opposition with the paths in the routing table. å= - = ngh j j ih h i P 1 1 ) ( ) 2 -1( Routing and learning starts when the source node receives FEEDBACK stack. Source node chooses the path that has the maximum probability and sends the stacks with the chosen path. Middle nodes also do so and continue until delivering the stack to central station. Each node after sending the stack waits for the respond from the receiver node. If they received positive answer the path receives a reward. TinyLAP also uses Warn stack. Warn stack sends when the energy of the nod is lower than 70% (for the first time the primary energy is assumed) each I node if receives (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 35 Warn stack from j node and if j node is exist in routing table of I node, penalizes the same action in the route of j node. 2.2 FDDA protocol the main focus of most researches in this field has been tend to fault tolerances which during them nodes are completely corrupted and less efforts have been done for incompatible errors. Data incompatibility errors happen due to changes in binary contents when it is processing. This error is called soft error [5]. This error happens when the content of pkt d stack is received by the n node similar to content of pkt d stack which is not sent by the n node. The incompatibility error can happen in rode in the manner of temporarily or permanently. Internal problems in hardware components such as processor or memory units can appear incompatibility errors. In contrast with corruptions of energy resource, a node that has been involved with incompatibility errors still does its services correctly. But in doing some other services they encounter errors. From few efforts that have been done in the field of incompatibility fault tolerance is the protocol offered by Ssu et al and his colleagues [4]. The working procedure of this protocol that we call it FDDA is to first make two distinct routes between the source node and central node. And then the data in two copies and by the two routes is being sent. In the central node datum are compared with each other. And if they are similar they can be admitted. Else a new route (without any shared point with the rest routes) between source node and central node is being made and then data in three copies and from two previous route and new route is being sent. To recognize the correct data stack central node uses the quorum in vote. in FDDA protocol to recognize the corrupted node, the central node sends a message for all the routes of corrupted node(knowing that each node maintains returning route) that with this message the error amount of corrupted route increases and when a node gets errors more than threshold automatically becomes a corrupted node and has to be inactive. Central node sends a correcting message for the correct routes. And the scope of errors of this route becomes zero. Figure 1. data sending flow in FDDA protocol 2.3 Learning Automata A Learning automata is a conceptual mode that chooses randomly one of its actions and applies that to its environement.environement evaluates the chosen action by the automata and by a make up signal sends them to learning automata. Learning automata update its own internal situation by the chosen action and make signals. and then chooses the next action. Figure 2 shows the relation between learning automata and environment. [6] Figure 2. Learning automata connection with environment [6]. The environment shown by where } ,..., , { 2 1 r a a a a = is a set of inputs } ,..., , { 2 1 r b b b b = is a set of outputs and } ,..., , { 2 1 r c c c c = is penalty probabilities. Environment can be shown by three } , , { c E b a = and set of inputs } ,..., , { 2 1 r a a a a = is a set of outputs } ,..., , { 2 1 r b b b b = and } ,..., , { 2 1 r c c c c = set of penalty probabilities. Whenever b set has two members, environment is type P. in such an environment 1 1 = b is the penalty and 0 2 = b is considered as reward. In an environment type Q, β set has infinite members. And in an environment type S, β set has infinite members as well. ci Is the penalty probability of i a .learner automats are divided into two fixed and changing groups. 3. Proposed method TinyLAP has some problems: 1) in contrary to what designers of this protocol claim, what they call Learning automata is not a Learning automata. Instead of taking samples they use probabilities graph to choose the most probable. 2) This protocol uses Warn stack to adjust the energy consumption. That this job can be done with the responding stack. 3) In TinyLAP protocol according to the 1-2 relation, for the nodes using more than two routes to base stationthe sum of probabilities becomes more than one. (Relation 1 -3) in 1 -3, relation i h the number of steps to base stationfor the ith route and ngh is the number of routes to the routing table. Proposed protocol is mentioned in following part that solves these problems. 4) the reliability is not offered in this part. 1 ) 1 ( ) ( 11 1 1 1 - = - = - = åå å å å == = = = ngh hh ngh h h i P ngh j j ngh j j ngh i ngh j j i ngh i ) 3 -1( FDDA Protocol has its own problems such as sending datum from three random routes. And it can not be optimum. And the second problem is that in FDDA after comparing the first if they were not equal. Send from another three routes. Is main difficult this protocol no optimal sending path and choice randomize. Purpose of this protocol is to make balance in energy consumption in network nodes. This work happens by the learner automats. In fact, proposed protocols are combination of three methods. This method first finds all the routes like TinyLAP or EAR. Then like the FDDA method transmits the data with two routes finally these become compared in the Sinks. If they were equal, admits one of them as ultimate output. ) (n b Random Environment Learning Automata ) (n a (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 36 Figure 3. graph of proposed algorithm In proposed protocol each node has learning automata. And they act in this manner. Each node in each time by using the automata chooses one or two routes. If the chosen route is an appropriate route is gives reward. lese it should be punished. Purpose of this rewarding or punishing is to increase or decrease the choosing rate. Proposed protocol includes to levels “making routing tables” and “routing and learning". In level of making tables, the routing table of each node is being made. In level of routing and learning the source node starts to send the data from two or three diverse routes. The middle node does the same job. The data tables update according to their response stack. In this protocol each node has Learning automata with its routes to Sink (Sink). The route that is used to balance the energy. In following parts we will explain them in details. Making Routing Tables This level starts by Sink. This node makes FLOOD stack. And sends this stack to all it neighbors. This stack contains three fields. Number of nodes sender, count of steps to Sink, and energy stage of sender node. Before distribution the FLOOD stack by the Sink, changes the sender nodes number to its own number, changes the number steps to zero. Other nodes while receiving FLOOD stacks start to make routing tables that are like this: If a node received just one FLOOD, adds information of received stack to its own routing table and makes the routing table one. If a node received more than one FLOOD stack, puts all the information in its own routing table.(each record for one route). Choosing probability of each from this route is on the basis of relation 2-3. å å = = - + = £ " m i i i m i i i i l energylevel energyleve h numhop numhop h P m i i 1 1 ) 1 ( 1 1 ) 3 -2 ( In this relation, it is number of received stack. numhopi is the number of steps for ith stack. energyleveli is the amount of I stack and m is the number of received stacks. h is the amount of constant that is a number between 1 and 0. This parameter is the displayer of effective ratio of steps in front of energy of chosen node. The more parameter reaches to one, the more steps become effective. And as it reaches to Zero, energies effect will be more to all the probable routes. FLOOD stacks receiver, quantifies fields of the FLOOD stack and distributes them in the network. Quantifying is to introducing its own number as sender nodes number and puts its energy stage in that field. To give amount for the steps, adds one unit to the routing unit that has the least step number. Whenever considering to a routing table, one learning automata that its actions is equal by the number of its routing table. In fact, there is a one to one relation between actions of automata and routes of routing table. Probability of choosing each action is equal with probability of the same route in the table. Whenever learning automata chooses a practical node, the same route with that action goes to be chosen to be sent to the Sink. If chosen action is appropriate, the probability of selecting that increases. If not, selecting probability according to algorithm decreases. At the end of this level each node has one Learning automata and routing table to guide the data to Sink Routing and learning level In this level, each node that had a data to be sending sends data according to its routing table. By the help of learning automata chooses two different routes to send data stack. Data stack in addition to that data, includes primary source fields, final destination and sender node. The source node quantifies the data stacks fields and then sends the stacks on the chosen routes. Each node that sends a data stack, if it is not that destination, guides that stack to the Sink by the help of routing table and learning automata. This middle node prior to send the stack makes the receiver sources number same as its own number. Also this node makes another stack called ACK sends is to the node that is going to receive data stack. ACK stack includes sender's field and energy stage. ACK stacks sender node, changes receivers' numbers to senders numbers. To reduce the transmitted messages between two nodes and economizing in energy consumption, P parameter is being introduced. Each node by choosing each route sends P number of data on that route. Also, each node while receiving P numbers of data sends just one ACK stack to the sender node. This job avoids lots of ACK stacks and reduces energy consumption. Every node, by receiving an ACK stack rewards the route that ACK stack has navigated. If energy of on node that has sent the stack: Be lower than 50% from the average energy of first nodes in the route, choosing action gives penalty according to 3β that β is based on 3 -5 relation. More than 50% and less than 80% average of energy in contrast with first nodes; this action gives penalty by the relation of 3-3. b ) 3 . 0 5 . 0 1 ( - + = avgenergyl energyleve V i p ) 3 -3 ( In relation 3-3, avenergy is the energy of primary nodes and energyleveli is the energy stage of ACKs sender. And β is being selected by the 5-3 relation. 0/3 is the result of difference between 50% and 80%. The result of relation is between β and 2β. More than 80% and less than 100% from the average of primary nodes and route steps means that this action should be rewarded by a parameter. A is evaluated by relation 5-3. If it is more than the energy of other primary nodes, this action will be rewarded by parameter a. Sink Source (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 37 numhop l energyleve numhop numhop l energyleve i i max * ) (max * 1 1 + - + + = g g y l a (4-3) numhop avgenergy numhop l energyleve avgenergy i i max * ) ( 2 2 + + - + = g g y l b (5-3) In relation 5-3 and 4-3, energylevel and numhopi are energy level and ACK stack senders steps. Energylevel is the starting energy of node, maxnumhop the greatest number of steps from the receiver node, and avgenergy is the average of primary nodes energy. λ1 and λ2 are displayers of the least acceptable amount for rewarding and punishing parameters. Considering the difference in scale between steps (numhop) and remaining energy (energylevel) γ parameter is being selected in a way that balances the different scale. ψ1 and ψ2 are being selected in a way that they don’t let a and β parameters rise more than a specific boundary. And finally, to make sure that received data is correct in Sink they are being compared. If both of the data were the same, one of them is going to be selected as main received data. And throw away the other. If the data is not correct the Sink sends a FEEDBACK from both routes. As soon as receiving FEEDBACK message, the node sends the data by the third route. And when it receives them again, asks for majorities vote to accept them. To receive a third incorrect data happens rarely. In this way this algorithms continues until receiving the correct data. But we just send the data from 3 possible routes. 4. Simulation Results We stimulated a wireless sensor network in a 100*100 space and with an equal distribution of 100 sensors randomly by using MATLAB software. In this simulation the central node at the end of area with the co ordinations has been put. The primary energy of sensors is 0.5 j .duration of simulation is 1000 cycle and consumption energy is equal with table 1. Table 2: used Radio characteristics in our simulations Energy Dissipated Operation Eelec=50nJ/bit Transmitter/Receiver Electronics EDA=5nJ/bit/signal Data Aggregation Єƒs=10pJ/bit/m2 Transmit Amplifier if dmaxtoBS ≤ d0 єmp=0.0013pJ/bit/m4 Transmit Amplifier if dmaxtoBS ≥ d0 0 200000 400000 600000 800000 1000000 0 100 200 300 400 No Nodes No packdt Propose protocol tinyLAP FDDA Figure 4. Count of received data stacks by several protocol The results show that TinyLAP some times sends by three routes but has the same lifetime in network. Also there is fault tolerance in new method. Comparing with EAR acts better and the lifetime of network increases. As you see in the Figure 4, the numbers of sent stacks have been compared with the corrupted nodes. And also fault tolerance has been added to the method. In comparing with FDDA both methods get majority vote. But in this new method to send uses the least energy using routes. So in contrasting with FDDA the lifetime of network increases significantly. That Figure 5 shows this. 0 0.51 0 20 40 80 100 120 140 160 180 200 Failure node sc ale rece ive d irec t to sum all d ata FDDA Proposed protocol Figure 5: Comparison of delivered stacks in contrast with corrupted nodes in proposed protocol and FDDA 5. Conclusion and future works In this article one protocol that uses aware automats to find the appropriate routes to send the data stacks to balance the energy consumption and correct sending of datum among nodes proposed. The results of simulation showed that proposed protocol from balancing aspect among nodes and lifetime of network and reliability have the good performance than TinyLAP, EAR and FDDA. New protocol contrary to EAR protocols does not need local information. Reference [1]Gaurav Gupta, Mohamed Younis "Fault-Tolerant Clustering of Wireless Sensor Networks"2003 IEEE [2]Yongxuan Lai, Hong Chen "Energy-Efficient Fault-Tolerant Mechanism for Clustered Wireless Sensor Networks" 2007 IEEE.This work is supported by the National Natural Science Foundation of China under Grant. [3]Ameer Ahmed Abbasi,Mohamed Younis,Saudi Arabia"A survey on clustering algorithms for wireless sensor networks" Computer Communications30(2007)2826-2841 WWW.ScienceDirect.com [4]Chessa S. and Santi P., “Comparison-based system-level fault diagnosis in ad hoc networks”, in: Proceedings of 20th IEEE Symposium on Reliable Distributed Systems, pp. 257–266, 2001. [5]Ssu K. F., Chou C. H., Jiau H. C. and Hu W. T., “Detection and diagnosis of data inconsistency failures in wireless sensor networks”, in: Proceedings of the Computer Networks, Vol 50, Issue 9, Pages 1247-1260, 20 June 2006. [6] D. Chen and P. K. Varshney, "QoS support in wireless sensor networks: a survey", in Proc. of International Conference on Wireless Networks (ICWN '04), pp. 227-233, Las Vegas, Nev., USA, June 2004. [7] M. Ankit, M. Arpit, T. J Deepak, R. Venkateswarlu and D.Janakiram. “TinyLAP: A Scalable learning automatabaase energy aware routing protocol for sensor networks”.Communicated to IEEE Wireless and Communications and Networking Conference to be held in Las Vegas, NV USA. 2006. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 38New method to decrease probability of failure nodes in WSNs Ali HosseinAlipour 1, Davood KeyKhosravi 2, Abbas Mirzaei Somarin 3 1Islamic Azad University-Tabriz Branch, Iran Ali.Hosseinalipour@yahoo.com 2Islamic Azad University-Osku Branch Iran kaikhosravi2003@Yahoo.com 3 Islamic Azad University-Tabriz Branch, Iran A.Mirzaei@iaut.ac.ir Abstract: Clustering in wireless sensor networks is one of the crucial methods for increasing of network lifetime. There are many algorithms for clustering. One of the important cluster based algorithm in wireless sensor networks is LEACH algorithm. In this paper we proposed a new clustering method for increasing of network lifetime. We distribute several sensors with a high-energy for managing the cluster head and to decrease their responsibilities in network. The performance of the proposed algorithm via computer simulation was evaluated and compared with other clustering algorithms. The simulation results show the high performance of the proposed clustering algorithm. Keywords: Network Clustering, Nodes failure, Energy-Aware Communication, Wireless Sensor Networks 1. Introduction Recent improvements in integrated circuits (IC) have fostered the emergence of a new generation of tiny, called Sensors. That from economical aspect they are commodious and also they are used in non military (for instance environmental managing: temperature, pressure, tremor, etc) To consider having group of limitations such as battery life time, calculating and memory significantly they have been predicted as non recyclable and also they live until their powers fade away. So power is something rare for systems like sensor. During a special mission the correct consumption for sensors lifetime should be managed knowingly. The power of sensor can not support more than far connection. Therefore to transmit they need the architecture of multi sectional. A useful way to decrease the system lifetime is to divide them to diverse clusters [2]. Parts of a cluster-based network sensor are base stations and sensors. In this method sensors relay the data flow by head clusters. The central station always stays far from where sensors are expanded. In this manner saving the consumption energy and awareness of that to communicate with central station has various methods. Two methods of routing in articles have been proposed [5, 6]. These methods because of their route detecting and finding optimum steps in relation with central station have head load. In addition, they will have extra load on nodes that are located around central station, so most of the traffic will be from them. To avoid these overheads and unbalanced consumption of energy some high-energy nodes called “Gateways” are deployed in the network [2]. These sensors are used as head clusters due to decrease the failure probability of head clusters. And this increases the lifetime of the network. But since this method takes a lot of expenditure so in this article we just use these sensors as manager for a number of head clusters. In this manner each one becomes gatewayamong each head cluster. This method decreases both networks lifetime and failure probability. In the second part, the architecture of two networks and the relevant tasks will be explained. In the third part, the proposed protocol has been explained and in the fourth part the results of simulating and tests evaluation can be seen. The last part involves conclusion of the article and discussing about pattern of future researches. 2. Related works System architecture for clustered sensor networks has been shown in figure 1. There just two sorts of nodes, cluster joint sensors and head cluster with tolerance of energy shortcoming. Joint sensors and homogeneous head clusters with a same identity have been assumed as similar. All the connections are wireless. The connection of joint nodes with the main station is possible only with head cluster. For sending information schedule we use TDMA (Time-Division Multiple Access) protocol. During starting the process a unique ID, primary energy and TDMA scheduling are attributed for all the sensors and gateways. We suppose that the entire node are aware from others place by the GPS. In the beginning all of the connective bridges are assumed in connection area. as the energy consumption of GPS is high , it is On at the beginning of the clustering and on the other states it is in the sleep mode. Connection scheduling among connective bridges first appears with head cluster when it establishes. The central station always stays far from where the sensors are expanded. in this order, maintaining the consumption energy and being aware of that in relation with central station have different methods: such as LEACH (Low(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 39 energy Adaptive Clustering Hierarchy) [1] and SEP (Stable Election Protocol) [7] and also two other routing method have been explained in articles [5, 6].these methods due to detecting the path and finding the optimum steps in relation with command node have head load. In addition having extra load on nodes, which is located around central station, most of the traffics will be because of them. To avoid this head loads and unstable energy consumption some of nodes have been expanded through the networks by a high-energy that called gateway [2].these sensors act as gateway among clusters and central stations. And mage the entire network in cluster. Each sensor with a high-energy belongs just to one cluster. And the connection with the central station just takes place through cluster Gateway. In this method failure probability decreases and networks lifetime increases. Figure 1. network style with clustering 3. Proposed method These methods because of their route detecting and finding optimum steps in relation with central station have head load. In addition, they will have extra load on nodes that are located around central station, so most of the traffic will be from them. Figure 2. Multi-gateway clustered sensor network To avoid this extra load and unstable consumption of energy some of the nodes have been expanded with a high-energy called Gateway [2] sensors are used as head clusters due to decrease the failure probability of head clusters. And this increases the lifetime of the network but since this method takes a lot of expenditure so in this article we just use these sensors as manager for a number of head clusters. To do so, we expand some of nodes according to lifetime, space and number of exist sensors in network. While clustering we don’t need this work node. We can cluster the network with the algorithms like SEP, LEACH and TEEN (Threshold-sensitive Energy-Efficient sensor Network Protocol).afterward the clustering is done, each head cluster sends a signal to these sensors. And with these signals the sensors specify which cluster is appropriate to manage. And with the hypothesis of network they choose some of the cluster to in order to manage them. And each closer is being managed just by one of these sensors. After establishing the network the role of these sensors as gateways between head clusters and central stations, by the hypothesis network chooses some of clusters to manage. And each cluster is being controlled by just one of the sensors. After establishing the network, the sensors have the role of a gateway between central stations and head clusters. To be attentive that head clusters to transmit to central stations and data assembling and calculating in protocol consume a great deal of energy. All the responsibility of head cluster is given over to joint cluster sensors or Gateway. Then after receiving data from its joint nodes without any calculating delivers them to gateway. And its gateway that transmits them to base station after doing necessary works and calculations. This method can be used in two ways. One that we spread high-energy sensors beside other sensors. And another practical way is to put them between root station and head clusters. In both aspects both network lifetime increases and extra load eliminates from head clusters and also failure probability decreases. That other cluster heads don’t have connection with Sink station. And this connection is accomplished via Gateway and these nodes with high-energy contain the rule of Gateway. And these Gateways to lifetime termination managing same cluster heads. But similar to LEACH algorithm in any time period the cluster head is changing. When the cluster node is changing, the cluster head tell to gateway via a signal. This protocol is resumed to end of lifetime. 4. Simulation Results We stimulated a wireless sensor network in a 100*100 space and with an equal distribution of 100 sensors randomly by using MATLAB software. In this simulation the central node at the end of area with the co ordinations has been put. And we spread 4 sensors with high power in network. The primary energy of typical sensors is 0.5 J and sensors with high-energy are 1.0 J. we adjust the execution of the simulation for 1000 cycle and also consumption energy is evaluated based on table number 1. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 40 Table 1: used Radio characteristics in our simulations Energy Dissipated Operation Eelec=50nJ/bit Transmitter/Receiver Electronics EDA=5nJ/bit/signal Data Aggregation Єƒs=10pJ/bit/m2 Transmit Amplifier if dmaxtoBS ≤ d0 єmp=0.0013pJ/bit/m 4 Transmit Amplifier if dmaxtoBS ≥ d0 The results of simulation show that new method in comparison with LEACH and SEP acts better and also increases the networks lifetime significantly. We test this protocol and LEACH and SEP with different sensors (50,100,200,300,400,500) and as seen in figure 3 the results show that the new method is better than exist methods. And the lifetime of the network is more than the same lifetime in LEACH and SEP. both LEACH and SEP die with 100 sensors when they see the first sensor and live for another 200 time. While in the proposed protocol after observing the first died sensor that itself observes later than LEACH and then lives for another 300 times. Figure 3. Comparing proposed algorithm with others 5. Conclusion and future works The node of Gateway with a high-energy through the sensors is used as a central manager is just a step away from the central station. Ultimately after simulating we found out that proposed protocol plays an indispensable role in increasing network lifetime and could have been increased the lifetime in comparison with SEP and LEACH. In this article it is supposed that sensor nodes and gateways are fixed and motionless. On the other program we will research the mobile gateways. Reference [1] Kazem Sohraby, Daniel Minoli, Taieb Znati "Wireless Sensor Networks Technology, Protocols, and Applications" Published by John Wiley & Sons, Inc., Hoboken, New Jersey. Published simultaneously in Canada. 2007. [2] Gaurav Gupta, Mohamed Younis "Fault-Tolerant Clustering of Wireless Sensor Networks" 2003 IEEE [3] Yongxuan Lai, Hong Chen "Energy-Efficient Fault-Tolerant Mechanism for Clustered Wireless Sensor Networks". 2007 IEEE. This work is supported by the National Natural Science Foundation of China under Grant. [4] Ameer Ahmed Abbasi, Mohamed Younis, Saudi Arabia "A survey on clustering algorithms for wireless sensor networks" Computer Communications 30(2007)2826-2841 WWW.ScienceDirect.com [5]S. Singh, M. Woo and C. S. Raghavendra, "Power-Aware Routing in Mobile Ad Hoc Networks", Proc. of ACM MOBICOM'98, Dallas, Texas, October 1998 [6] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. "Scalable coordination in sensor networks" Proc. of ACM/IEEE MobiCom 1999, Seattle, Washington, August 1999. [7] Georgios Smaragdakis Ibrahim Matta Azer Bestavros” SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks” Technical Report BUCS-TR-2004 [8] Piraeus Tillapart, Sanguan Thammarojsakul, Thanachai Thumthawatworn, Pratit Santiprabhob”An Approach to Hybrid Clustering and Routing in Wireless Sensor Networks” 2005 IEEE. Author Profile Ali HosseinAlipour received the B.S. degrees in Computer Engineering from Islamic Azad University-Shabestar Branch in 1999 & 2002 and M.S. degrees in Computer architecture engineering from Islamic Azad University-Tabriz Branch in 2007 & 2010, respectively. My interests about researches include WSN and schedule into multiple processes. . 800 900 1000 1100 1200 1300 1400 10 100 200 300 400 500 ? Network Lifetime NEW Protocol SEP LEACH No.Nod(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 41 A New Clustering Algorithm for Increasing of Lifetime in sensor Networks Abbas Mirzaei Somarin1, Habib Motee Ghader2, Amir Masoud Rahmani 3 and Ali Ghafari4 1 Islamic Azad University-Ardabil Branch,Ardabil, Iran a.mirzaei@iaut.ac.ir 2 Islamic Azad University-Tabriz Branch-Young Research Club, Tabriz, Iran Habib_Moti@yahoo.com 3 Islamic Azad University-Oloom Tahgigat Branch-, Tehran, Iran Rahmani74@yahoo.com 4 Islamic Azad University-Tabriz Branch , Tabriz, Iran jane.doe@email.com Abstract: One of the crucial problems in sensor networks is limitation of energy, which affects in network lifetime. There are many algorithms for increasing network lifetime. One of the methods in this case, is network clustering. A good clustering increases the lifetime of network. In this paper a new clustering algorithm based on Learning Automata for increasing network lifetime is proposed. The proposed algorithm based on LEACH Protocol. Performance of proposed algorithm is compared with previous methods by implementing simulation. The obtained results from proposed algorithm is better than others. Results are indication of high efficiency of suggestion algorithm. Keywords: Network Clustering, Algorithm. 1. Introduction Wireless networks are networks, which are, consist of many little nodes by low facility. These nodes, which are called a sensor, can feel special feature such as wetness, temperature, and pressure in their environment and send this for their neighbors. In other words two major facilities of these sensors are the feeling of special parameter around environment is ability of connection. In some operations these nodes might be join to each other by connective cables, but in most cases a wireless network is completely wireless. In this network nodes are generally fixed or fixed limited motions. Despite of fixed networks and other wireless networks, which the quality of service is completely, clear in sensor networks there is no fixed recounting. Some of these recounting are network proper covering, amount of active nodes in per time, accuracy of received information in Sink (central node) and the time of transferring information to Sink. Some of these recounting such as proper covering and amount of active nodes in per time are depended to operation and others like accuracy of received information and time of transferring information Sink intended the feature of network. One of the sensor networks important features is probability of devastation in some nodes specially because of losing energy. For this reason there are so many nodes in wireless networks. In this case if some of these nodes has been destroyed others can replace them so some of these nodes should be active but others should be inactive in order not consume their energy. Therefore, quality of service can be recounting according to active nodes because in this case networks lifetime will be increased. One of the effective ways in increasing of networks lifetime is clustering. In sensor network clustering, sensor network divided into some branches and one of the nodes have been chosen as a top branch. Duty of top branch is receiving information from other branches and sends them to the Sink. In dynamic clustering network can be cluster just once and nodes of branches never transfer to others but network nodes can be the members of other branches. In this paper by using of learning automata we will change the LEACH algorithm that increases network lifetime. In the rest of this paper we will talk about learning automata in section 2. Then in section 3 LEACH algorithm will be explained. In section 4 suggested algorithm will be introduced and in section 5 the rest of dramatization had been shown. 2. Learning Automata Learning automata is an abstract model that chooses randomly an operation from a set of finite operations and then applies it on the environment to the selected operation environment is evaluated by learning automata and then informs the evaluated result by the help of a reinforcement signal to the learning automata. The learning automaton updates its interior situation by utilizing selected operation and reinforcement signal and selects the next operation afterwards. Interconnection between learning automata and the environment is shown in Fig.1 [1]. Figure 1. Learning automata connection with environment [2]. The environment shown by where } ,..., , { 2 1 r a a a a = is a set of inputs } ,..., , { 2 1 r b b b b = is a set of outputs and } ,..., , { 2 1 r c c c c = is penalty probabilities. When b is a set of binary, so the environment is a P type. In this kind of environment 1 1 = b is considered as penalty and 0 2 = b as ) (n a ) (n b Random Environment Learning Automata (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 42 reward. In Q type environment, b includes numerous finite members and in S type b has a number of infinite members. ci is a penalty probability of operation. Learning automata is divided into two groups as stable and unstable structure. Learning automata can be utilized in many different ways such as: routing in communication network, face recognize, programming processes in a computer network. queue theory, access control in asynchronous transmit network, partitioning objects and finding an optimal structure for nerve systems [2, 7-11]. 3. LEACH Protocol One of the first and famous presented hierarchical protocols to the sensor networks is LEACH protocol [3]. In this protocol, the time span of the nodes activity divides into some periods. At the beginning of each period some of the nodes be selected haphazardly as a cluster head (CH). To do this, each node produces a haphazard number between 0, 1. Where as this number from the amount of T (n) that results in by the use of formula (1), be less, the stated node be presented as cluster head. In formula 1, p is the correlation of the number of clusters to the total nodes of the networks, r is the number of period and G the number nodes that in the last period of 1/p are not selected as cluster head. ï ïî ï ïí ì Î ´ - = otherwise G n if p r P P n T , 0 , ) 1 mod ( 1 ) ( Relation 1. Random number generation between zero and one After determining the nodes of cluster head, the other nodes on the basis of the power of the received signal from each cluster, decide to be accepted as a member of which cluster. The cluster head node divides its responsibility glen in to some time slots (Figure 2). This time slots on the basis of TDMA mechanism are cooperated between the members of cluster. In each time slot, the cluster head connect with on of the members of the cluster and receives the information packs of that member. The cluster head in every some slots sends its received information from its members to the Sink. In order to the distribution of the load on different nodes after finishing of a period, to start a new period, the cluster head by the declared mechanism above are exchange. Figure 2. Period and Time Slice in LEACH protocol 4. Improved Protocol (LALEACH) As mentioned in the previous section LEACH algorithm do the act of clustering and is selected a cluster head to each cluster. And the responsibility of each cluster head is gatherings the information’s from the other nodes of the same cluster and sending of to the Sink. In LEACH protocol the cluster head never be changed. And because this reason the node that is considered as cluster head, consumes more energy. And this itself causes the declining of the life long of the network. In order to overcome this problem we can exchange dynamically the cluster head node between the members of cluster nodes. In suggested algorithm, we change the LEACH node in a way that the node of cluster head in each period exchange dynamically between the clusters nodes. The way of selecting the cluster head node between the nodes of a cluster forms by the learning automata. In suggested algorithm there is considered a learning automata for each cluster the number of the actions of automata equals with the number of clusters nodes. Each action by automata corresponds with a node from the cluster. In figure 3 a cluster and its corresponded automata are showed. Example of Sensor network and cluster Equivalence Learning automata for cluster (1) Figure 3. The assigning the cluster nodes to correspond learning automata The Way of choosing the clustering After clustering in LEACH protocol, turns to the selection of cluster head to each clusters. As it mentioned, for each of the clusters there is considered a learning automata that the number of its actions equals with the number the nodes of the some cluster. The learning automata between its actions choose an action that its number is more than the other. After choosing a node as a cluster head, in order to transfer the information of its clusters nodes by the TDMA mechanism connects with them and again the learning automata choose another node as the cluster. (It chooses the node as a cluster that the corresponding action that has more amount than the other actions). The amounts of automata in each time are exchange by the formula 2. i i i nn n de P = Relation 2. action value Relation N11 N6 N2 N1 N9 N10 N3 N4 N5 N8 N7 LA a1 a3 a4 a2 a5 N3 N4 N8 N7 N5 (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 43 In this formula: n : The number of cluster nodes. i n : The th i node. i n e : The remain energy of i n node. i n d : The average of distance of i n node with the other nodes of the same cluster. i n p : The amount of th i action of automata. In figure 4, period and the way of time slot in suggested protocol is showed. By comparing the figure 2 and 4 the way of exchanging the node of cluster head for a cluster is showed (clustering in each period is done and the exchange of the cluster head node is done inside the clusters). Figure 4. Period and Time slice in LELEACH protocol. Figure 5 shows a sensor network. At first this network by the LEACH algorithm is divided into three clusters. By the next period that a new algorithm will be occurs, the suggested algorithm will exchange the cluster head dynamically. Figure 5. an Example of clustered sensor network At first after clustering by the use of LEACH algorithm, the node of cluster head is appear. After connecting the cluster head node with the all of its clusters node and transferring their outputs to the Sink, turns to the exchange of cluster head node. The way of exchanging the clusters nodes of number (1) as the cluster head is occurs like this: First stage: in this stage by the information of the number (1) cluster the exists in figure of table 6, the number of actions of the cluster (1) automata is appeared. AUTOMATA ACTIONS VALUES Average Distance Remain Energy Node No 55 . 0 43 . 53 1 = = n p 34 . 5 3 8 6 2 1 = + + = d J en 3 1 = 1 n 83 . 0 65 2 = = n p 6 3 12 4 2 2 = + + = d J en 5 2 = 2 n 13 . 0 67 . 71 3 = = n p 67 . 7 3 3 12 8 3 = + + = d J en 1 3 = 3 n 46 . 0 3 . 42 4 = = n p 3 . 4 3 3 4 6 4 = + + = d J en 2 4 = 4 n Figure 6. The figure (5) network cluster number (1) nodes information. After determining the amount of the automata’s actions related to the cluster (1) as table of figure 6, now it is selected a node as a cluster head that its amount of action is more than the others, so it is selected as the cluster head node. After selecting the node of number (2) as a cluster head, it declares its being as cluster head to the all nodes exist in its cluster. The other cluster head contents of the table of figure 6m which are being up-to-date in selecting of cluster head are being selected. After connecting the node ( 2 n ) by all nodes of its cluster and transferring its information to the cluster head node, it makes up-to-date its remained energy in table (6). After getting up-to-date the information of the table, the node, which its amount of action is more than the others, is selected as cluster head. This process continues until the beginning of next stage. 5. The Result of Simulations In this section the result of suggested algorithms simulation is comparing and assessing with the result of previous algorithm. The results of suggested algorithm is compared and assessed in respect of lifetime by the algorithm of LEACH, HEED, Extended HEED clustering. In the tested simulation of the sensor environment is considered 150 150´ and the radio range of the sensor environment is considered 30 meters. The first energy of the nodes is considered 2J. Trials to some of the different sensor nodes is done by N={100, 150, 200, 250, 300, 350, 400, 450, 500} the shown results is the result of min of results gained from 10 performing different simulations. The results from different algorithms are compared with each other respects of lifetime that is one of the main standards of the quality of service in sensor networks. The results of assessing are showed in Figure (7) it is clear that the lifetime of network in the suggested algorithm is more than the other ways. N11 N6 N2 N1 N9 N10 N3 N4 N5 N8 N12 Cluster 1 Cluster 2 Cluster 3 2m 12m 6m 4m 3m 8m CH CH CH N19 N18 N16 N17 N13 N23 N20 N15 N22 N21 N14 N7 N25 N24 Cluster 4 Cluster 5 Cluster 6 CH CH CH (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 44 Figure 7. Comparison of suggested algorithm with others. 6. Conclusion In this paper a new algorithm based on LEACH algorithm is suggested. The goal of suggested algorithm is the increasing the lifetime of the sensor network. In LEACH algorithm the nodes of cluster head are selecting with out considering their remained energy and because the nodes of cluster head consume more energy than the other node, so LEACH algorithm in this respect that chooses haphazardly the nodes of cluster head causes decreasing the lifetime of the network. In suggested algorithm instead of selecting haphazardly the node of cluster head, it is selecting between the nodes their remained energy is more than the other nodes and also near to its neighbor nodes. So, by this way nodes with high energy are selecting as cluster head and increase the lifetime of network. The effectiveness of suggested algorithm compared with cleared clustering LEACH, HEED, Extended HEED algorithms has better results. Reference [1] D. Chen and P. K. Varshney, "QoS support in wireless sensor networks: a survey", in Proc. of International Conference on Wireless Networks (ICWN '04), pp. 227-233, Las Vegas, Nev., USA, June 2004. [2] H.MotieGhader, S..Parsa, M.Hossein Nejad, “Application of Learning Automata for DAG Scheduling on Homogeneous Networks", 17th Iranian Conference on Electrical Engineering, Iran University of Science and Technology, ICEE2009. [3] S. M. Abolhasani, M. Meybodi, “Usage of Learning Automata for Routing, Fault Tolerance and Topology Control in Wireless Sensor Network”, MSC Thesis, March 2008. [4] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless MicrosensorNetworks,” IEEE Transactions on Wireless Communications, vol.1 ,no.4 , pp.660 –670 , October2002 . [5] O. Younis and S. Fahmy, "Distributed Clustering in Adhho Sensor Networks: A Hybrid, Energy-Efficient Approach", In Proc. of IEEE INFOCOM, March 2004 . [6] M. Esnaashari, M. R. Meybodi1, “A novel clustering algorithm for wireless sensor networks using Irregular Cellular Learning Automata”, IEEE, 27-28 Aug. 2008. [7] Meybodi, M. R. and Beigy, H., New Class of Learning Automata Based Scheme for Adaptation of Backpropagation Algorithm Parameters, Proc. Of EUFIT-98, Sep. 7-10, Achen, Germany, pp. 339-344, 1998. [8] Oommen, B. J. and Ma, D. C. Y., Deterministic Learning Automata Solution to the Keyboard Optimization Problem, IEEE Trans. On Computers, Vol. 37, No. 1, pp. 2-3, 1988. [9] Beigy, H. and Meybodi, M. R., Optimization of Topology of neural Networks Using Learning Automata, Proc. Of 3th Annual Int. Computer Society of Iran Computer Conf. CSICC-98, Tehran, Iran, pp. 417-428, 1999. [10] Beigy, H. and Meybodi, M. R."Optimization of Topology of Neural Networks Using Learning Automata, Proc. Of 3th Annual Int. Computer Society of Iran Computer Conf. CSICC-98, Tehran, Iran, pp. 417-428, 1999. [11] Hashim, A.A., Amir, S.and Mars, p. Application of Learning Automata to Data Compression, In Adaptive and Learning Systems, K. S. Narendra (Ed), New York: Plenum Press, pp. 229-234, 1986. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 45 Securing Digital Information using Quasigroups Saibal K. Pal1 and Shivam Kapoor2 1Scientific Analysis Group, DRDO, Metcalfe House, Civil Lines, Delhi – 110 054, India skptech@yahoo.com 2Department of Computer Science, University of Delhi, Delhi – 110 007 India shivam.dumca@gmail.com Abstract: The non-associative property of quasigroups has been recently found to be useful in many information security applications. In particular, quasigroups have been used for ensuring confidentiality and integrity of the data transmitted over insecure public channels. Quasigroups operations are computationally simple and can be efficiently used for protection of voluminous media like images, audio, video and different forms of multimedia. They are also suitable for securing data transmitted from and to mobile and miniature resource-constrained devices with limited capability. We first describe schemes for construction of large sized quasigroups that can be used to ensure confidentiality without complicating the operations or increasing the processing of data by introducing additional rounds. These quasigroups are generated using isotopies, product of smaller quasigroups, affine and nonafffin mappings, theta-mappings, keyed permutations, Tfuncction etc. Using these concepts, design of fast encryption schemes for different media is presented. Ensuring data integrity is also of vital importance for many present day applications. Schemes for generation of highly non-associative quasigroups are described and their use for secure hashing of data is explained. Computer implementation of these schemes demonstrates their simplicity and power for efficiently securing digital information. Keywords: quasigroup, isotopy, non-associativity, encryption, hashing, digital media. 1. Introduction 1.1 Latin Square A Latin square [1], [2] of order n is an n x n square matrix whose entries consist of n symbols such that each symbol appears exactly once in each row and each column. Examples of a 4 x 4 and 5 x 5 Latin square are given below Order 4: c b a d b a d c a d c b d c b a This Latin square generated by using elements of the set {a, b, c, d} is called a reduced Latin square as the elements in the first row & the first column are in monotonically increasing order. Order 5: 3 1 4 5 2 2 3 5 1 4 1 5 2 4 3 4 2 1 3 5 5 4 3 2 1 This specific Latin square is not a reduced Latin square as the rows are not arranged in order. Number of Latin Squares: The total number of Latin squares N [3] of order n are computed using the formula: N(n, n) = n! (n-1)! L(n, n) (1) Table 1. The number of reduced Latin squares n L(n , n) 1 1 2 1 3 1 4 4 5 56 6 9408 7 16 942 080 8 535 281 401 856 9 377 597 570 964 258 816 Here, L(n, n) is the number of reduced Latin squares of order n. For large values of n, the number of reduced Latin squares is difficult to compute & hence the total number of Latin squares of high order is unknown. 1.2 Quasigroup (QG) 1.2.1 Definition: A quasigroup (Q,*) [4], [5] is a set Q of elements along with a binary operation ‘*’ having the following properties: (a) For all a, b є Q, a * b є Q (Q is closed under *) (b) For all a, b є Q, there exist unique x, y є Q so that a * x = b and y * a = b i.e. ( (Q, *) has unique solubility of equations). Because of the unique solubility of equations, each element will appear exactly once in each row and exactly once in each column of the multiplication table of (Q,*). That is, each row and column is a permutation of the elements of Q. If |Q| = n, then the interior of the Cayley table for (Q, *) forms an n x n Latin square. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 46 Examples of Quasigroups: · The set of Integers with the subtraction operation ( -) form a quasigroup. · The non-zero Rationals and non-zero Reals with division operation ( ÷ ) form a Quasigroup. · Let Q = Z6 = {0, 1, 2, 3, 4, 5} and let x * y = (x + y) mod 6. Then ( Q , *) is addition modulo 6 on Z6 and the Cayley table for ( Q ,* ) is given by 4 3 2 1 0 5 5 3 2 1 0 5 4 4 2 1 0 5 4 3 3 1 0 5 4 3 2 2 0 5 4 3 2 1 1 5 4 3 2 1 0 0 5 4 3 2 1 0 * Figure 1. Cayley table for (Q ,*) (Q,*) is a quasigroup because its interior is a 6 x 6 Latin square. This quasigroup is also a group. 1.2.2 Some Properties of QGs · Quasigroups have cancellation properties that is if ab = ac, then b = c. This follows from the uniqueness of left division of ab or ac by a. Similarly, if ba = ca then b = c. · Left and right multiplication: By definition of a quasigroup Q, the left and right multiplication operators are defined by L( x )y = xy R( x )y = yx (2) These are the bijections from Q to itself. The inverse maps are given in terms of left and right division by L( x ) ˉ¹ y = x\y R( x ) ˉ¹ y = y/x (3) · A quasigroup is not required to be associative, commutative, or to have an identity element. 1.2.3 Use of QGs in Coding & Cryptography Apart from their applications in many diverse areas, quasigroups have been recently used as cryptographic primitives in the design of encryption schemes, for pseudoranndo number generation, for construction of hash functions and for design of error-detecting codes. As the basic operations on quasigroups are very simple, it is possible to construct fast and efficient schemes for different applications. 1.2.4 Basic Encryption and Decryption Using QGs Suppose that we are given a quasigroup with the operation * as follows: 3 1 2 0 3 0 2 1 3 2 2 0 3 1 1 1 3 0 2 0 3 2 1 0 * Figure 2. Quasigroup used for Encryption The following convention is normally used: Leader -Any of the symbols of Quasigroup can act as a leader. Here we have four choices: 0, 1, 2, 3 for the leader. The leader decides which row would contribute to the encryption process. Key -The leader and the quasigroup itself (with the unique arrangements of elements) may be used as keys during the encryption process. The basic encryption scheme [6], [7] using a leader is as follows. 1.2.5 Encryption Scheme: Let the plain message be represented by M = (x1, x2,…..,xn). We choose a leader L and pass on this secret information as a key to the receiver. Assuming that the quasigroup generation mechanism is available to the receiver, encryption is performed as follows EL(x1, x2,…….,xn) = (y1, y2,……..,yn) where y1 = L * x1 and yi = yi-1 * xi (for all i > 1) (4) For example if M = (3 0 2 1 2 3 3 1), then x1 = 3, x2 = 0, x3 = 2 and so on. Then, with the Leader as L = 0, the quasigroup given in Figure 2, and the encryption formula given above, we have y1 = L * x1 = 0 * 3 = 1 y2 = y1 * x2 = 1 * 0 = 0 y3 = y2 * x3 = 1 * 2 = 0 and so on. Thus, the encrypted message EL(M) = (1 0 0 0 3 3 3 2). Since there are various options for choosing a leader, the encryption scheme can be made stronger by using different leaders for encryption of different blocks of the message. The Quasigroup can also be changed periodically by permuting its rows and columns to increase the complexity of encryption scheme. 1.2.6 Decryption Scheme: For each quasigroup operation ‘*’ we can associate a new quasigroup operation ‘o’ defined by: x o y = z iff x * z = y (5) The “dual” operation ‘o’ is used for decryption and the “inverse” quasigroup is generated using the above equation: 3 1 2 0 3 0 2 1 3 2 1 3 0 2 1 2 0 3 1 0 3 2 1 0 o Figure 3. Quasigroup used for Decryption Decryption is carried out with the following formula: DL(y1, y2,…….,yn) = (x1, x2,……..,xn) where x1 = L o y1 and xi = yi-1 o yi (for all i > 1) (6) (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 47 By performing calculations using (6) and the previous quasigroup, the encrypted message is converted back to the original plain message. DL(EL(M)) = (3 0 2 1 2 3 3 1) This scheme is computationally simple and is based on basic lookup operations on quasigroups. To make this scheme more powerful and practical, construction of large quasigroups is required and is reported in Section 2. 1.3 Non-Associativity of Quasigroups In addition to the requirement of constructing large and unstructured quasigroups for cryptographic purposes, it is also important to generate quasigroups with high degree of non-associativity. These find applications in the design of secure keyed hashing schemes or message authentication codes [8]. To measure the degree of non-associativity of quasigroups, Meyer [9] borrowed the concept based on measuring the non-commutativity of groups. For a group (G,o), the multiplication group is the subgroup generated by all the left and right multiplications of G. As the left and right multiplication by an element would be the same for a commutative group, the multiplication group would be smaller. In contrast, for a non-commutative group, the multiplication group would be larger. Therefore, the size of the multiplication group of a group indicates the degree of non-commutativity of the group. A similar approach can be used to measure the degree of non-associativity of a quasigroup (Q,o). Here also, a larger multiplication group indicates that the quasigroup has a higher degree of nonassociaativity 2. Generation of QGs Construction of large quasigroups [10], [11] from smaller ones is an important problem for many applications. In cryptography, larger the size of the Latin square, larger is the number of choices that can be made by the communicating party and higher levels of security can be provided. Moreover, generation of Latin squares based on key permutations [12] help to regenerate the Latin square used by the sender at the receiving end with minimal information exchange. We present below different schemes for generation of huge Latin squares. 2.1 Simple Product of Quasigroups The notion of simple product of quasigroups is important for cryptographic applications since, if two quasigroups are given, it permits to construct a quasigroup of the order equal to the product of the orders of these quasigroups. Let Q1 = < R , • >, Q2 = < S , ~ > be two arbitrary quasigroups. Let the elements of two quasigroups be given by R = {0, 1, 2, . . . , n1 − 1}, S = {0, 1, 2, . . . , n2 − 1} Then the simple product Q of these quasigroups is the algebraic system Q = Q1 × Q2 = < T , * > (7) where T = {0, 1, . . . , (n1n2) − 1} To define the operation * in the set T, let us first assume that: Tcp = R × S = {t0, t1, . . . , tn1n2-1} (8) which is the Cartesian Product (CP) of the sets R and S. Further, let ti = (ri, si), tk = (rk, sk), where i, k Î T; ri, rk Î R; si, sk Î S. Noting that the quasigroup with elements belongs to the set Tcp, Qcp = < Tcp , * > is the simple product of quasigroups, we can define the operation * as follows: ti * tk = (( ri • rk ), ( si ~ sk )) (9) But we want to represent the simple product of quasigroups as a quasigroup. To this end, we must convert the set Tcp into the set T. There are many ways of doing such a conversion. The mapping h : tx →X, where tx Î Tcp, X Î T defined by the function h(tx) = h(rx, sx) = n2rx + sx (10) gives one of the simplest solutions. 2.2 Generation using Linear Mapping Using this scheme, we generate two linear functions f and g and then elements associated with each function is stored in one dimensional array of size equal to size of the permutation. Now, in order to generate the ( i , j )th element of the huge Latin square, the ith element of the first function is added to the jth element of the second function and modulus operation w.r.t the size of the Latin square to be generated is applied to the addition of ith element of 1st function and jth element of 2nd function. In this way we get a huge Latin square with elements in the range 0 to the size of Latin square. Let Q = Zn = {0,1…, n-1} and let the group operation be addition modulo n. Then we can create a Quasigroup (Q , ±) from (Zn , +) by defining f(x) = px + a (11) g(x) = qx + b where p and q are relatively prime w.r.t. the order of the quasigroup and a, b are positive integers less than the size of quasigroup, and then further defining h( x , y ) = ( f( x ) + g( y ) ) % n (12) For example: Let Q = Z8 = {0, 1, 2, 3, 4, 5, 6, 7} and let the group operation be addition modulo 8. Then we can create a quasigroup (Q , ±) from (Z8 , +) by defining f(x) = 5x + 6 and g(x) = 3x + 7, where a = 4 & b = 1 and p = 3 & q = 5. Since we are creating (Q , ±) by linear mapping, we will define h(x, y) = (f(x) + g(y)) % 8. Then (Q , ±) is as shown below 5 2 7 4 1 6 3 0 7 0 5 2 7 4 1 6 3 6 3 0 5 2 7 4 1 6 5 6 3 0 5 2 7 4 1 4 1 6 3 0 5 2 7 4 3 4 1 6 3 0 5 2 7 2 7 4 1 6 3 0 5 2 1 2 7 4 1 6 3 0 5 0 7 6 5 4 3 2 1 0 ± Figure 4. Quasigroup using Linear Mapping We find that (Q , ±) is not associative, because h(h(0, 2), 4) = h(3, 4) = 0 but h(0, h(2, 4)) = h(0,3) = 6. It is not commutative, because h(0,1) = 0 but h(1,0) = 2. There is no identity element and hence no inverses. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 48 Limitations of the above method: The problem with this scheme is that (Q , ±) is still quite structured. The elements in each row always appear in the same order. Similarly, the elements in each column are also arranged in the same order. In addition, each row is a copy of the previous row, shifted one space to the right. Each column is a copy of the previous column, shifted one space down. As we see in above example: 1st and 2nd row are (5 2 7 4 1 6 3 0) and (0 5 2 7 4 1 6 3) respectively. Hence by determining any of the rows, one can guess the entire Latin square. 2.3 Generation using Keyed Permutation In the previous scheme, one row could be easily derived from the other row. We remove this problem by using nonlinnea mapping. In this scheme two random permutations [12] f and g are generated and then each permutation is stored in one dimensional array of size equal to size of permutation. Now, in order to generate the (i, j)th element of the huge Latin square, the ith element of the first permutation is added to the jth element of the second permutation and modulus operation with respect to the size of the Latin square to be generated is applied to the addition of ith element of 1st permutation and jth element of 2nd permutation. In this way we get a huge Latin square with elements in the range 0 to the size of Latin square. Let Q = Zn = {0, 1…., n-1} and let the group operation be addition modulo n. Then we can create a quasigroup (Q , ±) from (Zn , +) by supposing f(x) = any random permutation {6, 2, 8…} g(x) = any random permutation {5, 3, 9…} then defining h( x , y ) = ( f( x ) + g( y ) ) % n (13) In the example below, to generate a Latin square of order 8 first we will generate two permutation f and g and then apply h( x , y ) = ( f( x ) + g( y ) ) % 8 for x and y ranging from 0 to 7 X 0 1 2 3 4 5 6 7 f(x) 2 5 0 4 6 7 1 3 g(x) 7 4 3 2 1 0 6 5 Then the quasigroup (Q , ±) created from f and g by using the above equation is 0 1 3 4 5 6 7 2 7 6 7 1 2 3 4 5 0 6 4 5 7 0 1 2 3 6 5 3 4 6 7 0 1 2 5 4 1 2 4 5 6 7 0 3 3 5 6 0 1 2 3 4 7 2 2 3 5 6 7 0 1 4 1 7 0 2 3 4 5 6 1 0 7 6 5 4 3 2 1 0 ± Figure 5. Quasigroup using Keyed Permutation We find that (Q, ±) is not associative, because h(h(0, 2), 4) = h(5, 4) = 0 but h(0, h(2, 4)) = h(0, 1) = 6. It is not commutative, because h(0, 1) = 6 but h(1, 0) = 4. There is no identity element and hence no inverses. Unlike the previous case, all the rows are independent of each others. 2.4 Generation using T-Functions T-functions, proposed by Klimov and Shamir [13], [14] are a relatively new class of invertible mappings using a combination of arithmetical operations like addition, subtraction, multiplication and negation together with Boolean operations like OR, XOR and NOT. This helps to design cryptographic schemes resistant to many present day attacks. Example of such a mapping is ) 2 )(mod ( 2 n VC x x x + ® (14) where C is a constant and V represents the logical operation OR. This turns out to be a permutation of single cycle of length 2n given certain conditions. In general, a T-function is a mapping in which the ith bit of the output depends on 0, 1, … , ith input bits. Using a small number of such primitive operations over n-bit (32, 64 etc.) words, efficient cryptographic building blocks can be designed. It is interesting to note that composition of two Tfuncction will also be a T-function. Because we will be using T-functions to create a quasigroup, it is convenient to choose k = l, so that f takes as input and produces as output k many binary strings of length n. In order to use a T-function f to define a quasigroup operation, we will see that f needs to be a permutation. Therefore, we need to know which Tfuncction are invertible. Example: Let 32 32 32 * : z z z v ® be given by v(x , y) = x2y2 + 3(x V y) (15) here V represents the Boolean OR operation and addition and multiplication are defined for mod 23 = mod 8. Let c = < 1 , 0 , 1 > Î Z23. We define x o y = c + (x + y) + 2v(x , y) = 5 + x + y + 2x2y2 + 6(x V y) (16) Based on this, the quasigroup is created where the binary representatives of the quasigroup elements are used for ease of notation. o 0 1 2 3 4 5 6 7 0 5 4 3 2 1 0 7 6 1 4 7 2 5 0 3 6 1 2 3 2 5 4 7 6 1 0 3 2 5 4 7 6 1 0 3 4 1 0 7 6 5 4 3 2 5 0 3 6 1 4 7 2 5 6 7 6 1 0 3 2 5 4 7 6 1 0 3 2 5 4 7 Figure 6. The quasigroup created using a T-function v(x, y) One of the disadvantages of using a T-function in creating a quasigroup can be seen in the resulting structure present in the quasigroup. From the given example we observe that the entries in each row and column alternate between even and odd numbers in the quasigroup. That is, if x o y is even, then x o (y + 1) and (x + 1) o y will be odd and vice versa. It is evident that this property holds in any quasigroup created from a T-function. We notice that both x and y are either even or odd. Clearly, if x is even, then x + 1 is odd and vice versa. Since x o y = c + x + y + 2v(x, y) and x o (y + 1) = c + x + y + 1 + 2v(x , y + 1) (17) (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 49 Because 2v(. , .) is always even, the parity of xo(y+1) will be different than the parity of xoy. Other useful schemes for generation of quasigroups are based on isotopies and complete mappings. In addition, if we choose affine isotopies or affine complete mapping, the Quasigroup created has special properties. 2.5 Theta Mapping A quasigroup can also be created from a group using a special kind of mapping called a complete mapping [9]. Definition: Let (G, +) be a group and let i : G à G denote the identity map on G. Ө : G à G is a complete mapping if Ө is a bijection and i -Ө is a bijection where (i -Ө)(x) = x -Ө(x). Example: Let (G, +) = (Z9, + ) where Z9 = (0 , 1, 2, 3, 4, 5, 6, 7, 8) and addition is performed modulo 9. Then Ө(x) = 5x + 4 is a complete mapping as seen in Figure 7 because both Ө and i -Ө are bijections x 0 1 2 3 4 5 6 7 8 Ө(x) 4 0 5 1 6 2 7 3 8 i -Ө(x) 5 1 6 2 7 3 8 4 0 Figure 7. A complete mapping on Z9 Creating Quasigroups using Complete Map: Sade [15] suggested creating a quasigroup (Q, o) from an admissible group (Q, +) and a complete mapping Ө by defining x o y = Ө(x -y) + y , for x , y Î Q (18) Example Let (Q, +) = (Z23 , o ) and let Ө (< X2 , X1 , X0 >) is given as < X1 XOR 1, X0 , X2 > if X2 = 0 < X1 XOR 1 , X0 XOR 1, X2 > if X2 = 1 (19) Then Ө and (i XOR Ө) are permutations as shown in the following figure > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < > < 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 ) )( , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , x (iXORθ θ(x) x Figure 8. Ө and i XOR Ө on Z23 If the elements of (Z23 , XOR) are represented as integers corresponding to binary strings for ease of notation , then Ө and i -Ө are shown in Figure 9 and the quasigroup created by Ө(x XOR y) XOR y is shown in Figure 10. 6 5 0 3 1 2 7 4 ) )( ( 1 3 5 7 2 0 6 4 ) ( 7 6 5 4 3 2 1 0 x XOR i x xq q Figure 9. Values of Ө and i XOR Ө on integer corresponding to elements of Z23 5 6 3 0 2 1 4 7 7 7 4 1 2 0 3 5 6 6 2 1 7 4 6 5 0 3 5 3 0 5 6 4 7 2 1 4 0 3 6 5 7 4 1 2 3 2 1 4 7 5 6 3 0 2 4 7 2 1 3 0 5 6 1 6 5 0 3 1 2 7 4 0 7 6 5 4 3 2 1 0 o Figure 10. Quasigroup created using the complete map Ө 3. Generation of Non-associative QGs In Section 1.3, we explained the need for generation of highly non-associative quasigroups for cryptographic purposes and measurement of the non-associativity of a given quasigroup. We present schemes with examples for generation of such structures. Let g : Q à Q be a transposition on a cyclic group (Q , +). Then (Q , o) given by x o y = x + g(y) is a highly nonassocciativ quasigroup. Here Mult(Q) = Sym(Q), where Mult(Q) is the multiplication group of (Q , +) and Sym(Q) represent the symmetric group of (Q, +). Both f and g appear in Mult (Q) as (Q , o) is generated from isotopy from f = id and g. g is a permutation of order 2 as it is a transposition. In addition, if Lx , Rx denote the left and right multiplication by x ε Q and Lx and Rx are in Mult (Q) for all x € Q. Since for g(a)=a, we see that La Î Mult (Q) for a Î Q. This now implies that La is a cycle of length n = |Q|. g and La together generate the entire symmetric group of size n. Therefore, Sym(Q) = Mult(Q) and this implies that (Q , o) is highly non-associative. For example, let (Q , +) = (Z8 , +) and let g : Q → Q be a transposition such that g interchanges the elements 0 and 1. Then (Q , o) created by x o y = x + g(y) is a highly nonassocciativ quasigroup. Here, we have g(0) = 1 , g(1) = 0 ,and g(a) = a for a >1 xoy = (x + g(y)) mod 8 (20) So a structured highly non-associative quasigroup can be created as 6 5 4 3 2 1 7 0 7 5 4 3 2 1 0 6 7 6 4 3 2 1 0 7 5 6 5 3 2 1 0 7 6 4 5 4 2 1 0 7 6 5 3 4 3 1 0 7 6 5 4 2 3 2 0 7 6 5 4 3 1 2 1 7 6 5 4 3 2 0 1 0 7 6 5 4 3 2 1 0 o Figure 11. A Structured Non-associative Quasigroup This quasigroup is highly non-commutative and nonassociiative We can see from the above example that under the operation ‘o ’, For x = 0 and y = 1 x o y = 0 and y o x = 2 For x = 1 and y = 2 x o y = 3 and y o x = 2 (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 50 4. Application of QG to Encryption Quasigroups are suitable for designing efficient as well as secure encryption schemes due to simplicity of the basic operation. Moreover, large and unstructured quasigroups can be generated using one of the schemes explained in the previous sections. Use of such quasigroups helps to improve the security of the scheme. A basic encryption and decryption scheme based on table lookup has been described in Sections 1.2.4 to 1.2.6. In this scheme the leader L acts as a key to the encryption algorithm and has to be changed frequently. In addition to the leader, changing the quasigroup also helps to improve the security of the scheme. This can be practically made possible [11] without having to transmit much of information as the key to the receiver. The observations below is of (a) Original Tank Image (b) Encrypted Image using same quasigroup but 256 different leaders (one for encrypting each row) and (c) Encrypted image using different leaders and different Quasigroups. To do away with the effects of high levels of redundancy found in visual data, a new scheme has been proposed [12] using lookup and shift operations so that subsequent chunks of similar data in the plain image are mapped into different blocks using the same encryption function. Other efficient schemes using a combination of quasigroup operations together with basic cryptographic primitives are also under development. Figure 12. Original Tank Image Figure 13. Encrypted Image using same QG but 256 Leaders Figure 14. Encrypted Image using different Leaders and Quasigroups 5. Application of QGs to Hashing 5.1 Definitions A function H( ) is said to be One Way Hash Function (OWHF) if it maps an arbitrary length message M to a fixed length hash value H(M) and satisfies the following properties [17]: · No secret information is required for operation of H( ) and description of H( ) is publicly known. · It is easy to compute H(M) if M is known. · If H(M) is given in the range of H( ), it is hard to find a message M for given H(M), and given M and H(M), it is hard to find a message M’(≠ M) such that H(M’) = H(M). A function H( ) is said to be Collision Free Hash Function (CFHF) if it maps an arbitrary length message M to a fixed length hash value and satisfies the following property in addition to the above three properties · It is hard to find two distinct messages M and M’ that hash to the same result (H(M) = H(M’)). 5.2 Construction of Hash Function Based on QG For a quasigroup (Q, .), a hash function HQ( ) can be defined as ) ....). ). . ((...( ) ... ( 2 1 2 1 n n Q q q q a q q q H = (21) where ‘a’ is a fixed element of Q. The original multiplication table of a quasigroup may be modified using homotopy that permutes the rows and columns resulting in a different multiplication table. Q v u v u v u Î " = , )) ( ). ( ( . b a g (22) The above three permutations are generated and used for construction of new quasigroups for hashing. It is possible to calculate the results without storing the table, therefore, large quasigroups may be used for design of hash functions suitable for cryptographic applications. Other schemes based on generation of random quasigroups with multiple lookups have been successfully used for hashing. New quasigroups are constructed using non-linear transformations involving logical OR, XOR and circular shift operations. Computationally efficient hashing schemes based on these simple operations have been designed that also ensure collision & pre-image resistance. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 51 6. Design & Implementation Our design and implementation work includes the following: (1) Generating Orthogonal Latin Square for a given Latin Square. (2) Encryption and Decryption using Key-based Random Permutation. (3) Generation of Isotopes of a Latin Square. (4) Construction of a huge Latin Square using the Simple product of two Latin Squares, Affine Mapping, etc. (5) Encryption/Decryption using Latin Square and Lookuu Table method. (6) Generation of a non-associative Quasigroup with help of Cayley’s table and T-functions. (7) Improving the basic encryption scheme to handle redundancy in multimedia. These schemes have been implemented under the Microsoft VC++ and Matlab programming environment on a high-end stand-alone personal computer. 7. Conclusions Suitability of quasigroup based structures for encryption and hashing were established in this paper with examples, implementations and favorable observations and results. Construction of large and unstructured quasigroups is useful for design of encryption schemes with large key space. Similarly, highly non-associative quasigroups find application in the design of efficient hash functions. Modifications in the basic operations and combination with other cryptographic primitives in order to further improve the security would be taken up as our future work in this direction. References [1] R. Bose, B. Manvel, Introduction to Combinatorial Theory, John Wiley & Sons, 1984. [2] C.F. Laywine, G.L. Mullen, Discrete Mathematics using Latin Square, Wiley Interscience, 1998. [3] R. Alter, “How Many Latin Squares Are There?”, American Mathematical Monthly, 82, pp. 632-634, 1975. [4] S. Markovski, D. Gligoroski, V. Bakeva, “Quasigroup String Processing: Part 1”, Proc. of Maced. Acad. of Sci. and Arts for Math. and Tech. Sci., XX 1-2, pp. 13–28, 1999. [5] S. Markovski, V. Kusakatov, “Quasigroup String Processing: Part 2”, Proc. of Maced. Acad. of Sci. and Arts for Math. and Tech. Sci., XXI, 1-2, pp. 15–32, 2000. [6] S. Markovski, D. Gligoroski, S. Andova, “Using Quasigroups for One-one Secure Encoding”, Proc. VIII Conf. Logic and Computer Science, LIRA ’97, Novi Sad, pp. 157–162, 1997. [7] S. Markovski, D. Gligoroski, B. Stojˇcevska, “Secure Two-way On-line Communication by using Quasigroup Enciphering with Almost Public key”, Novi Sad Journal of Mathematics, 30, No 2, 2000. [8] B. Schneier, Applied Cryptography (Second Edition), John Wiley & Sons, 1996. [9] K.A. Meyer, “A New Message Authentication Code Based on the Non-associativity of Quasigroups”, Doctoral Dissertation, Iowa State University Ames, Iowa, 2006, [Online] Available: http://orion.math.iastate.edu/dept/thesisarchive/PHD/KMeyerPhDSp06.pdf [Accessed: Feb. 24, 2008]. [10] C.Z. Koscielny, “Generating Quasigroups for Cryptographic Applications”, International Journal of Applied Mathematics & Computer Science, Vol. 12, No. 4, pp. 559-569, 2002. [11] S.K. Pal, S. Kapoor, A. Arora, R. Chaudhary, J. Khurana, “Design of Strong Cryptography Schemes based on Latin Squares”, Proceedings of the Pre-ICM International Convention on Mathematical Sciences, New Delhi, 2008. [12]S.M. Hussain, N.M. Ajlouni, “Key Based Random Permutation”, Journal of Computer Science, Vol. 2, No. 5, pp. 419-421, 2006. [13] A. Klimov, A. Shamir, “A New Class of Invertible Mappings”, CHES, LNCS-2523, 2002. [14] A. Klimov, A. Shamir, “Cryptographic Applications of T-functions”, Selected Areas in Cryptography, SAC-2003, LNCS-3006, Springer Verlag, pp. 248-261, 2003. [15] A. Sade, “Quasigroupes Automorphes par le Groupe Cyclique”, Canadian Journal of Mathematics, 9, pp. 321-335, 1957. [16] S.K. Pal, Sumitra, “Development of Efficient Algorithms for Quasigroup Generation and Encryption”, Proceedings of the 2009 IEEE International Advance Computing Conference, pp. 2529-2534, 2009. [17] V. Snasel, A. Abraham, J. Dvorsky, P. Kromer, J. Platos, “Hash Function Based on Large Quasigroups”, International Conference on Computational Science (ICSS 2009), Lousiana, USA, LNCS 5544, pp. 521-529, 2009. [18] S. Markovski, D. Gligoroski, V. Bakeva, “Quasigroup and Hash Functions”, Discrete Mathematics & Applications, Proceedings of the 6th ICDMA, Bansko, pp. 43-50, 2001. [19] S. K. Pal, D. Bhardwaj, R. Kumar, V. Bhatia, “A New Cryptographic Hash Function based on Latin Squares and Non-Linear Transformation”, Proceedings of the 2009 IEEE International Advance Computing Conference, pp. 2529-2534, 2009. Authors Profile Saibal K. Pal received the M.S. degree in Computer Science from University of Allahabad in 1990 and PhD from University of Delhi in the area of Information Security. He is presently with DRDO, Delhi. His areas of interest include Cryptography, Information Hiding, Signal Processing and Soft Computing. Shivam Kapoor is presently pursuing his Masters degree in Computer Applications (MCA) from the Department of Computer Science, University of Delhi. His areas of interest include Discrete Mathematics & Combinatorics, Cryptography and Design of Algorithms. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 52 Column Vectorizing Algorithms for Support Vector Machines Chen ZhiYuan1, Dino Isa2 and Peter Blanchfield3 1University of Nottingham, School of Computer Science, Jalan Broga 43500 Semenyih Selangor Malaysia eyx6czy@nottingham.edu.my 2School of Electronic Engineering, University of Nottingham, Jalan Broga 43500 Semenyih Selangor Malaysia Dino.Isa@nottingham.edu.my 3School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, UK pxb@Cs.Nott.AC.UK Abstract: In this paper we present the vectorization method for support vector machines in a hybrid Data Mining and Case-Based Reasoning system which incorporates a vector model to help transfer textual information to numerical vector in order to make the real world information more adapted to the data mining engine. The main issue of implementing this approach is two algorithms; the discrete vectorization algorithm and continuous vectorization algorithm. The basic idea of the vectorization algorithm is to derive X value from the original column value and where the vector value is unavailable; the algorithm builds a vector table based on the X value by using appropriate functions. Subsequently, the vector model is classified using a support vector machine and retrieved from the case based reasoning cycle using a self organizing map. Keywords: Vectorization, Support Vector Machine, Data Mining, Artificial Intelligence, Case-Based Reasoning. 1. Introduction The problem faced by traditional database technology developer today is lack of intelligence support, while artificial intelligence techniques [1] were limited in their capacity to supply and maintain large amount of factual data. This paper provides a method to solve this problem. From a database point of view, there was an urgent need to address the problems caused by the limited intelligent capabilities of database systems, in particular relational database systems. Such limitations implied the impossibility of developing, in a pure database context, certain facilities for reasoning, problem solving, and question answering. From an artificial intelligence point of view, it was necessary to transcend the era of the operating on numerical signals to achieve the real information management system able to deal with large amounts of textual data. Our approach was explicitly designed to support efficient vectorization techniques by providing multiple number resources with minimum inter-dependencies and irregular constraints, yet under strict artificial intelligence considerations. It features a table in a relational database through two types of vectorizing functions, supporting to the construction of the support vector machine. The rest of this paper is organized as follows: Section 2 presents objectives and related techniques. Section 3 describes in detail the architecture of the hybrid system. Section 4 provides the procedure of vectorization. Section 5 explains the conducted experiments. The conclusion is discussed in section 6. 2. Objectives and Foundation Our research group works on the designing of flexible and adaptable user oriented hybrid systems which aims to combine database technology and artificial intelligence techniques. The preprocessing procedure related to data vectorization step of a classification process, going from low level data mining processes [2] to high level artificial intelligence techniques. Many domain specific system such as user modeling systems [3] or artificial intelligence hybrid systems have been described in literature [4] [5] [6]. Even when the applied strategies are designed as generic as possible, the illustration given for the system are limited to the text document and do not develop any vectorizing algorithm to quantitate the input raw textual data set into numeric data set. Actually, to the best of our knowledge, no such complete and generic vectorization process exists because of the necessity to have an excellent know-how in the implementation of a hybrid intelligent system. Many existed systems have been developed on the basis of using artificial intelligence techniques to provide semantic support to a database system, or database techniques to aid an artificial intelligence system to deal with large amounts of information. The key factors they concerned reside in the exploitation of the equivalence between database field and the knowledge representation system of artificial intelligence. In our hybrid system, vector is the unique representation of data considering the system consistency. On the other hand, for both data mining process and case-based reasoning cycle (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 53 [7], vectorization and consistency are crucial. The role of vectorization is to convert text table which stored in SQL server, into numerical vector form. Traditional vectorization method concentrates on image object into a raster vector or raw line fragments. While we focus on these table column features and describe how they can be vectorized by applied automatically approach using two kinds of vectorization functions. In order to describe the foundation of the vectorization, the framework of our hybrid system is simply described in the following section. 3. Hybrid System Architecture Overview The concepts of this project are as follows: · To develop a hybrid data mining and case-based reasoning user modeling system · To combine data mining technology and artificial intelligence pattern classifiers as a means to construct a Knowledge Base and to link this to the case-based reasoning cycle in order to provide domain specific user relevant information to the user in a timely manner. · To use the self organizing map [8] in the CBR cycle in order to retrieve the most relevant information for the user from the knowledge base. Based on these concepts the architecture has been designed which is illustrated in Figure 1. The hybrid system contains five main components: · Individual models, comparable to the blackboard containing the user information from the real world. · Domain database integrated the preselected domain information [9]. · A data mining engine which classified both user class and domain information vectors. · A knowledge base, containing the representation of classified user information and combined with interested domain knowledge. · A problem-solving life-cycle called case-based reasoning cycle, assisting in retrieve reuse revise and retain the knowledge base. Data Mining CBRHuman expert User Model Data mining engine SVM Vectorization User interface User Model Retrieved Case Knowledge Base Confirmed Solution Proposed Solution User ID Query SOM RETRIEVE RETAIN REVISE REUSE Domain Database Individual Model Figure 1. The architecture of the system 4. Vectorization As can be seen from the hybrid system architecture, in order to classify individual models and domain information into user model the support vector machine are applied. Individual models are user information which took table format and stored in the SQL server. Domain information in the database is also sorts of tables which stored the preselected user-preferred knowledge. The support vector machine [10] [11] is one of AI techniques which serve as classifier in the system. The main idea of a support vector machine is to construct a hyper plane as the decision surfaces in such a way that the margin of separation between positive and negative features is maximized. The vectorization step is the data preprocessing for the support vector machine which provides the numeric feature vector. 3.1 Feature Type For vectorization task to be as accurate as possible we predefined two type table columns or we called feature type; discrete columns (feature) and continuous columns (feature). Discrete feature contains discrete values, in that the data represents a finite, counted number of categories. The values in a discrete attribute column do not imply ordered data, even if the values are numeric; the distinct character is values are clearly separated. Telephone area code is a good example of discrete data that is numeric. Continuous feature contains values that represent a continuous set of numeric and measurement data, and it is possible for the data to contain an infinite number of fractional values. An income column is an example of a continuous column. The numeric value is not the vital factor to determine the feature type, but if the value is a word then it must be a discrete feature. 3.2 Vectorization algorithm From the technology point of view, vectorization is an approach modeling relationships between the data set and the vectorizing variable. We provide a more flexible approach by allowing some of the features (columns) to be independent and some of the features to be interdependent. Constructing two parallel algorithms to avoid time consuming and save a large amount of effort. The schema of the algorithm is specified in Figure 2 which derives the numeric vector by implementing different functions. The schema is not exhaustive and can evolve with new data, according to user need. Furthermore, once the type of the column has been determined, adding a new record is quite straightforward. These functions are also well suited to dealing with incomplete data. Instances with missing attributes can be handled by summing or integrating the values of other attribute. We represent each column as a data point in a dimensional space, where Z is the total number of attributes (columns). The algorithm computes the vectorizing value (or representation value) between each feature which was denoted by abscissa axis and the vector denoted by y-axis, and all the feature values determine its own vectorizing values. Once the vectorizing value list is obtained, the vector model will be classified based on the implementation of (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 54 support vector machine so that the core of the hybrid system the knowledge base will be constructed completely. Figure 2. The schema of the vectorization algorithm The detailed vectorization algorithms are described in the Table 1 and Table 2 according to discrete columns and continuous columns. Table 1. The discrete column vectorization algorithm 1: Let V be the representation of Vectors, D be the whole set of the vector model and d be the set of discrete columns. 2: FOR each data point Z DO 3: Select d Z , the discrete features of all data point, 4: Compute d V = ( dx V , dy V ), the corresponding value between Z and every vector, ( dx V , dy V ) D. 5: d dx n V = , dy V = d n n ´ 1 ; ] 1 , 0 [ Î dy V . 6: END FOR Table 2. The continuous column vectorization algorithm 1: Let V be the representation of Vectors, D be the set of vector model and c be the set of continuous columns. 2: FOR each data point Z DO 3: Select c Z , the continuous features of all data point, 4: Compute c V = ( ¢ cx V , ¢ cy V ), the corresponding value between Z and every vector, ( ¢ cx V , ¢ cy V ) D. 5: ¢ cx V = cx cx cx MaxV AvgV V ) ( - , x x x x cy e e e e V - - + - = ¢ , ]. 1 , 1 [ + - Î ¢ cy V 6: END FOR The key computation of these two algorithms is the vectorization value formula given in step 5 of the both table. Formula 1: d dx n V = dy V = d n n ´ 1 Formula 2: ¢ cx V = cx cx cx MaxV AvgV V ) ( - x x x x cy e e e e V - - + - = ¢ , ]. 1 , 1 [ + - Î ¢ cy V In Formula 1, n is the weight parameter associated with the discrete columns which is the sum of value type. dy V is a combination of the unit value ( n /1 ) multiply the sequence of the current value type ( d n ). This is a regression-like expression [12]. Regression is used to make predictions for numerical targets. By far the most widely used approach for numerical prediction is regression, a statistical methodology that was developed by Sir Frances Galeton [13]. Generally speaking Regression analysis methods include Linear Regression, Nonlinear Regression. Linear Regression is widely used, owing largely to its simplicity. By applying transformations to the variables, we can convert the nonlinear model (text table column information) into a linear one according to the requirement of the support vector machine. In order to get the negative X value and at the same time keep the same distance among original X value, in Formula 2 we minus average value to all x value and then get the proportion compare with the maximum original X value, after that get the new X value and by means of Hyperbolic Tangent function [14] to map these new value into (-1, +1) scale. In order to explain these algorithms clearly, we show the experiment procedure in the following section. 5. Experiments The vectorization algorithm was tested on the censusinccom data set extracted from the 1994 and 1995 current population surveys conducted by the U.S. Census Bureau. The data contains 41 demographic and employment related variables. In order to explain how to apply our approach clearly, we choose 8 discrete columns and 8 continuous columns which can be found in table 3 to explain the implementation in details. In Table 4 we list the n value of the discrete columns. For example the worker class n value, because there are 9 kinds of worker class, so n is equal to 9. Parts of the experiment results implemented the proposed algorithms which contain 27 records are shown in figure 3. The input for the algorithm was given 8 discrete features and 8 features and asked to give the vectorized value as output. The discrete attributes were decomposed into n equidistances, which yielded corresponded vector value scaling to the range of (0, 1). For the continuous attribute, firstly the raw attribute value was transferred into the whole x-axis, so that the new x value contain the negative value (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 55 and by using Hyperbolic Tangent function the vector value was calculated. The Hyperbolic Tangent function make sure the vector value to be projected into the (-1, 1) scale which is required by support vector machine. Figure 3. Part of the experiment results T The recommend vector value range is (0, 1) or (-1, 1) for support vector machine [15]. One reason for this is to avoid vector value in great numeric ranges dominates those in smaller numeric ranges. Another reason is to avoid the numerical difficulties during the calculation. Because kernel values usually depends on the inner products of feature vectors. For example the linear kernel and the polynomial kernel, large vector values may cause numerical problems [16]. Another reason why we proposed two kinds of algorithm to vectorize discrete columns and continuous columns is to preserve the character of the column for the sake of the later analysis. Table 3. Parameters for experiments Discrete columns Continuous columns class of worker* age* education* wage per hour marital stat capital gains sex capital losses reason for unemployment dividends from stocks family members under 18 person for employer live in this house 1 year ago weeks worked in year veterans benefits instance weight* Table 4. The discrete column n value Discrete columns n Value class of worker 9 education 17 marital stat 7 sex 2 reason for unemployment 6 family members under 18 5 live in this house 1 year ago 3 Veterans benefits 3 All the experiment results was created on PC computer, CPU Intel(R) Core(TM) Duo CPU T2250 @1.73GHz 4.6 2.3, 2GB RAM DDR2 667 MHz, with WinXP. Program was compiled with NetBeans 6.0. 6. Conclusions The proposed hybrid Data Mining and Case-Based Reasoning User modeling system is a multi purpose platform and is characterized by three major processes. The vectorization processing unit communicate through the raw data set the SQL table and the output is the numeric vector, such an approach avoid the data inconsistency usually met in classifying documents chain when implement artificial intelligence tools. In this paper we built vectorization model by applying two algorithms: The discrete vectorization algorithm and continuous vectorization algorithm. The advantage of using discrete algorithm is that each record in the whole table was assigned a vector value in an easily expression calculation. While for the continuous column we choose a relatively complicated formula that is the Hyperbolic Tangent function to achieve the vector value. In designing the algorithm, the key consideration is to bring up easy scientific numerical transformation. Therefore, the formulas in the algorithm are quite basic but the impressive part is it also provides a reasonable balance between a satisfactory result and reasonable processing time. Secondly due to the modular structure of the algorithm it can be adapted easily for application. The results of the algorithm in the experiments labeled clean and the vector points generated by our algorithm have a standard coverage (0, 1) and (-1, 1) which is useful in fulfilling the classification task by means of support vector machine for the hybrid system. References [1] S. J. Russell, P. Norvig, Artificial Intelligence A Modern Approach, Prentice-Hall International Inc, 1995. [2] U. Fayyad, G. Paitetsky-Shapiro, P. Smith, “knowledge discovery and data mining: Towards a unifying framework”, proceedings of the International Conference on Knowledge Discovery and Data Mining, 1996, pp. 82-22. [3] J. Vassileva, "A practical architecture for user modeling in a hypermedia-based information system", Proceedings of Fourth International Conference on User Modeling, Hyannis, MA, August 1994, pp 15-19. [4] I.V. Chepegin, L. Aroyo, P. D. Bra, “Ontology-driven User Modeling for Modular User Adaptive Systems”, LWA, 2004, pp.17-19. [5] I. Watson, Applying Case-Based Reasoning: Techniques for Enterprise Systems, Morgan Kaufmann Publishers, Inc., San Francisco, CA, 1997. [6] K. Sycara, “CADET: A cased-based synthesis tool for engineering design”, International Journal for Expert System, 4(2), 1992, pp.157-188. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 56[7] A. Aamodt, E. Plaza, “Case-based reasoning: foundational issues, Methodological variations, and system approaches”, AI communications, 7(1), 1994, pp. 39-59. [8] Kohonen, “self-organizing map using contiguityconsttraine clustering”, Pattern Recognition Letters, 1995, pp. 399–408. [9] B. Hjorland, H. Albrechtsen, “Toward A New Horizon in Information Science: Domain Analysis”, Journal of the American Society for Information Science, 1995, 46(6), 400-425. [10] E. Osuna, “Support Vector Machines: Training and Applications”, Ph.D thesis, Operations Research Center, MIT, 1998. [11] V.N. Vapink, Statistical Learning Theory, New York:Wiley. [12] D.V. Lindley, "Regression and correlation analysis," New Palgrave: A Dictionary of Economics, v. 4, 1987, pp. 120-23. [13] F. Galeton,“Typical laws of heredity", Nature 15,1877, pp. 492-495, 512-514, 532-533. [14] M.A. Abdou, A.A. Soliman, “Modified extended tanh-function method and its application on nonlinear physical equations”, Physics Letters A, Volume 353, Issue 6, 15 May 2006, pp. 487-492 [15] E. Osuna, R. Freund, F. Girosi, “Improved training algorithm for support vector machine”, IEEE Neural Networks in Signal Processing 97,1997. [16] C. Cortes, V. Vapnik, “Support-vector network”, Machine Learning , 1995, pp. 273–297. Authors Profile Chen ZhiYuan received the B.A. in Economics from University of HeiLongJiang in 2001 (China). During 2006-2010, she stayed in University of Nottingham, Malaysia Campus to do PhD research in imitate human experts (especially in manufacturing and medical field) to perceive the environment and to make decisions which maximize the chance of success. From 2007 to 2009, she stayed in Supercapacitor Research Laboratory (SRL), which is supported by Ministry of Science Technology and Inovation of Malaysia to study knowledge management system for manufacturing enviroment. Dino Isa is a Professor in the Department of Electrical Electronics Engineering, University of Nottingham Malaysian Campus. He obtained a BSEE (Hons) from the University of Tennessee, USA in 1986 and a PhD from the University of Nottingham, University Park Nottingham, UK in 1991.nnnThe main aim of his research is to formulate strategies which lead to the successful implementations of “Intelligent Systems” in various domains. Peter Blanchfield is a senior tutor in the School of Computer Science, University of Nottingham. From September 2005 to July 2009 he was Director of the IT Institute in the School, before which he was the Director of Computer Science and IT Division at the Malaysia Campus of the University of Nottingham. In that role he was involved in setting up the activities of the School there along with the activities of what has become the Engineering Faculty on that campus. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 57 Impact and Performance Analysis of Mobility Models on Stressful Mobile WiMax Environments N Vetrivelan1 Dr. A V Reddy2 1Research Scholar, NIT, Trichy, India,caz0307@nitt.edu Assistant Professor, Department of Computer Applications Periyar Maniammai University, Thanjavur, Tamilnadu, India nvetri@yahoo.com 2Professor, Department of Computer Applications National Institute of Technology, Trichy, India reddy@nitt.edu Abstract: In this study, we have used the design and implementation of a new medium access control protocol with WiMax, based on the IEEE 802.16. We have compared and analysed three different mobility models and the impact of mobility on mobile WiMax environments. We have chosen Gauss-Markov, Manhattan Grid and Random WayPoint Mobility models with DSR routing protocol in WiMax environments. The parameter metrics Packet Delivery Fraction, Routing load, Throughput and Latency have been taken into account. Our ns-2 simulation result shows that the functioning of mobility models will greatly influence the performance of WiMax environments. The result reveals that the throughput, latency and routing load are high in Gauss Markov Mobility model. It also shows that packet delivery fraction is high in Manhattan Grid model. Compared to Manhattan and Gauss Markov models the random waypoint models is stable. Keywords: Mobility, DSR, WiMax, MAC and Simulation 1. Introduction WiMax [3] is the short form of the Worldwide Interoperability for Microwave Access. Typically, fixed WiMax networks have a higher-gain directional antenna installed near the client which results in greatly increased range and throughput. Mobile WiMax networks are usually made of indoor customer premises equipments (CPE) such as desktop modems, compared to directional antennas but they are more portable. The mobility model [1] is designed to describe the movement pattern of mobile users, and how their location, velocity and acceleration change over time. Since mobility patterns plays a significant role in determining the protocol performance, it is desirable for mobility models to emulate the movement pattern of targeted real life applications in a reasonable way. We have provided a categorization for various mobility models onto several classes based on their specific mobility characteristics. For some mobility models, the movement of the WiMax node is likely to be affected by its movement history. The authors are aware that this performance comparison of mobility scenarios has not attempted in WiMax Environments or IEEE 802.16 module. That is why, the performance of mobility scenarios using DSR wireless Routing protocol in WiMax module has been chosen and compared. In Section 2, the related works have been discussed. Brief description of Mobile node and WiMax Module has been presented in Section 3. The Mobility models described in 4. Protocol description has been given in Section 5. The evaluation methodologies have been given in Section 6. In Section 7, the Simulation Parameters and Parameter Values of WiMax V2.03 have been described. Results and Discussion presented in Section 8. The conclusion has been presented in Section 9. 2. Related Work Tracy Camp, Jeff Boleng [1] surveyed the mobility models that are used in the simulations of Ad hoc networks. Authors described several mobility models that represent mobile nodes whose movements are independent of each other (i.e, entity mobility models) and several mobility models that represent mobile nodes whose movements are dependent on each other ( i.e. group mobility models.) This paper presents a number of mobility models in order to offer researchers more informed choices when they are deciding upon a mobility model to use in their performance evaluations. Illustrated how the performance results of an ad hoc network protocol drastically change as a result of changing the mobility model simulated. Per Johansson, Tony Larsson compared three routing protocols for wireless mobile ad hoc network. They have done simulation on a scenario where nodes move randomly. Furthermore, three realistic scenarios were introduced to test the protocols in more specialized contexts. In most simulations the reactive protocols (AODV,DSR) performed significantly better than DSDV. At moderate traffic load DSR performed better than AODV for all tested mobility values, while AODV performed better than DSR at higher traffic loads. Leonardo Betancur [5] performed experiments for WiMax Channel-Phy Model in ns-2. Their work has been on a novel proposal for PHY layer and propagation model that allowed faster and more detailed the link level execution. They described the development process for model and the (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 58 implementation details in ns-2 for PMP topologies. They described the development of physical layer model based on the IEEE 802.16 standard also known as WiMax using ns-2. Their work presented a statistical equivalent model for ns-2, which consider the channel effects in WiMax networks for upper layer simulations. Through simulation they reached the conclusion that their model reduced computational effort in link level simulations, without using complex bit-bit simulations also it is necessary to analyze the performance of WiMax networks and found more realistic coverage areas. Jenhui Chen, Chih-Chieh Wang, [4] presented detailed design and implementation of WiMax module based on the IEEE 802.16 broadband wireless access networks (BWANs) or WiMax module with the point-to-multipoint (PMP) mode for the ns-2. They implemented modules comprised fundamental functions of the service-specific convergence sub layer (CS), the MAC Common part sub layer (CPS), and the PHY layer. A simple call admission control (CAC) mechanism and the scheduler have also been included in this module. Figure 1. Conversion of Mobile node in to WiMax node Network Interface Propagatio n Model Queue Link Layer ARP Channel Application Routing Agent PKT Sent MAC decides OK ? Not ok ok Traffic Generating Agent Link Layer Queue PROPOSED WIMAX Network Interface Radio Propagation Model Channel (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 59 3. Conversion of Mobile Node in to WiMax Node Each mobile node has made use of a routing agent for the purpose of calculating routes to other nodes in the ad-hoc network. Packets were sent from the application and were received by the routing agent. The agent decided a path that the packet must travel in order to reach its destination and stamped it with this information. It then sent the packet down to the link layer. The link layer level used an Address Resolution Protocol to decide the hardware addresses of neighboring nodes and map IP addresses to their correct interfaces. When this information was known, the packet was sent down to the interface queue and awaited a signal from the Multiple Access Control (MAC) protocol. When the MAC layer decided it was ok to send it on to the channel. The propagation model used the transmit and received stamps to determine the power with which the interface would receive the packet. A mobile node has been converted to WiMax node as discussed subsequently. The 802.16 based WiMax module [3][4] consisted of Mac 802_16, Common and Queue have been in accordance with the specifications of the IEEE 802.16-2004 standard and based on the ns-2 version 2.29. An Object oriented programming language C++ were developed for classes. The relationship between WiMax module and ns-2 modules was represented in the stack of the ns-2 is as shown in Fig.1. It consists of the type of objects for the traffic generating agent (TGA), the link layer (LL), the interface queue (IFQ), the designed MAC layer (WiMax module), and the PHY layer (Channel). The implemented module comprised fundamental function of the servicespeccifi convergence sublayer (CS), the MAC Common part sublayer (CPS) and the PHY layer. A simple call admission control mechanism and the scheduler have also been included in this module 4. Mobility Models 4.1 Gauss Markov Model This model [1] was designed to adapt to different levels of randomness. Initially each node is assigned a current speed and direction. At fixed intervals of time, movement occurs by updating the speed and direction of each node. Specifically, the value of speed and direction at the nth instance is calculated based upon the value of speed and direction at the (n-1)th instance. The main advantages of this model are that it eliminates the sudden stops, sharp turns present in Random way point mobility model and is close to being realistic. 4.2 Manhattan Mobility Model The Manhattan model [1] is used to emulate the movement pattern of mobile nodes on streets defined by maps. The Maps are used in this model too. The map is composed of a number of horizontal and vertical streets. Each street has two lanes for each direction (North and South direction for vertical streets, East and West for horizontal streets). The WiMax node is allowed to move along the grid of horizontal and vertical streets on the map. At an intersection of a horizontal and vertical street, the WiMax node can turn left, right or go straight. This choice is probabilistic: the probability of moving on the same street is 0.5, the probability of turning left is 0.25 and probability of turning right is 0.25. The velocity of a mobile node at a time slot is dependent on its velocity at the previous time slot. Also, a node’s velocity is restricted by the velocity of the node preceding it on the same lane of the street. 4.3 Random Way Point The Random Waypoint Mobility model includes pause times between changes in direction and/or speed. An WiMax [3] node begins by staying in one location for a certain period of time (i.e pause time) Once this time expires, the WiMax node chooses a random destination in the simulation area and speed that is uniformly distributed between minimum and maximum speed. The node then travels toward the newly chosen destination at the selected speed. Upon arrival, the node pauses for a specified time period before starting the process again. This is a memorylees mobility pattern because it retains no knowledge concerning its past locations and speed values. The current speed and direction of a node is independent of its past speed and direction. This characteristic can generate unrealistic movements such as sudden stops and sharp turns. 5. Protocol description 5.1 Dynamic Source Routing The key distinguishing feature of DSR [10] is the use of source routing. That is, the sender knows the complete hopbbyhop route to the destination. These routes are stored in a route cache. The data packets carry the source route in the packet header. When a node in the ad hoc network attempts to send a data packet to a destination for which it does not already know the route, it uses a route discovery process to dynamically determine such a route. Route discovery works by flooding the network with route request (RREQ) packets. Each node receiving an RREQ rebroadcasts it, unless it is the destination or it has a route to the destination in its route cache. Such a node replies to the RREQ with a route reply (RREP) packet that is routed back to the original source. RREQ and RREP packets are also source routed. The RREQ builds up the path traversed across the network. The RREP routes itself back to the source by traversing this path backward. The route carried back by the RREP packet is cached at the source for future use. If any link on a source route is broken, the source node is notified using a route error (RERR) packet. The source removes any route using this link form its cache. A new route discovery process must be initiated by the source if this route is still needed. DSR makes very aggressive use of source routing and route caching. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 60 6. Evaluation Methodology To evaluate the three mobility models in WiMax, we used four performance metrics to compare and analyse the realistic movements 6.1 Packet Delivery Fraction The ratio of number of data packets successfully delivered to the destination, generated by CBR Sources. PDF=(Received Packets/Sent Packets)*100 6.2 Routing Overhead It is an important metric for measuring scalability of a protocol. The number of routing packet transmitted per data packet delivered at destination. Each hop wise transmission of a routing packet is counted as one transmission. Routing load = Packets sent/Received packet 6.3 Throughput These are the number of packets sent from the source and the number of packets received at the destination 6.4 Latency The time, it takes for a packet to cross a network connection from sender to receiver 7. Simulation parameters Table 1: Simulation Parameter Values Routing Protocol DSR MAC Layer IEEE 802.16 Number of Mobile WiMax Nodes 100,200,300,400 Mobility Model Gauss Markov Manhattan Grid Random Waypoint Transmission Bandwidth of each line 20 Simulation time 300Secs Traffic Type Constant Bit Rate Antenna Type Omni Antenna Table 2 : Important Parameter Values of WiMax V2.03 Bandwidth 20MHz Service flow Scheduling Type 11.13.11 SS_MAC_Address 48 Transaction_ID 16 Downlink frequency 32 Uplink channel_ID 8 7.1 Simulation Model In this section, the network simulation was implemented using the NS-2 simulation tool. The Network Simulator NS-2 was a discrete event simulator. For simulation Scenario and network topology creation it used OTCL (Object Tool Command Language). To create new objects, protocols and routing algorithm or to modify them in NS-2, C++ source code used. The WiMax module consisted of the type of objects for the traffic generating agent (TGA), the link layer (LL), the interface queue (IFQ), the designed MAC layer (WiMax module), and the PHY layer. The simulations were conducted on Due Core processor at speed 3.0 GHz, 1 GB RAM running Gygwin Environment. Simulation Mobility Model Table 3 : Simulation Parameter of Mobility Models Gauss Markov Manhattan Grid Random waypoint x=1000.0 x=1000.0 x=1000.0 y=1000.0 y=1000.0 y=1000.0 Duration =300.0 Duration =300.0 Duration =300.0 Update Frequency=2. 5 Update Dist=5.0 Dim=3 Maxspeed=4. 0 TurnProb =0.5 Minspeed =1.0 AngleStdDev 0.39269909 SpeedChang eProb=0.2 Maxspeed =4.0 SpeedStdDev =0.5 MinSpeed =1.0 Maxpause =60.0 MeanSpeed =1.0 SpeedStd Dev=0.2 8. Results and Discussion We have used ns-2 with WiMax to compare the performance of the mobility models. Four sets of results have been presented vide 100,200,300 and 400 WiMax nodes. In all stressful situations with communication channel 2,4,6,8 and 10 have been chosen. The routes of packets are accomplished with the DSR. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 61 Figure 2. Mobility Models – PDF (%) with varied communication channel in 100 WiMax Environments Figure 3. Mobility Models – PDF (%) with varied communication channel in 200 WiMax Environments Figure 4. Mobility Models – PDF (%) with varied communication channel in 300 WiMax Environments Figure 5. Mobility Models -PDF (%) with varied communication channel in 400 WiMax Environments As shown in the Figures 2,3,4,5, with respect to the PDF, of all 100,200,300 and 400 WiMax nodes situation Manhattan Grid Model out performs where as in the Random waypoint there is decreasing trend. In the Manhattan Grid Model the nodes have been chosen at a random destination either in the horizontal or vertical directions. Due to the more restricted movement of the nodes in the network which leads to slightly lesser number of broken links and subsequently lower the chance of getting a stray route error message. At the same time it is found out that Gauss Markov model shows steadiness in performance. Figure 6. Mobility Models -Routing Load (packets) with varied Communication channel in 100 WiMax Environments Figure 7. Mobility Models -Routing Load (packets) with varied communication channel in 200 WiMax Environments 100 Nodes 0 10 20 30 40 50 2 4 6 8 10 Communication Channel PDF GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 200 Nodes 05 10 15 20 2 4 6 8 10 Communication Channel PDF GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 300 Nodes 05 10 15 20 2 4 6 8 10 Communication channel PDF GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 0 10 20 30 2 4 6 8 10 R o u t in g L o a d Communication Channel 100 Nodes GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 0 10 20 30 2 4 6 8 10 PD F Communication Channel 400 Nodes GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 200 Nodes 05 10 15 20 25 30 35 2 4 6 8 10 Communication Channel Routing Load GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 62 Figure 8. Mobility Models -Routing Load (packets) with varied communication channel in 300 WiMax Environments Figure 9. Mobility Models -Routing Load (packets) with varied communication channel in 400 WiMax Environment As shown in the Figures 6,7,8,9, in all the four WiMax situations, as far as the routing load is concerned the Manhattan model outperforms compared to other two models. It is more likely for the route error messages to be dropped by some intermediate nodes before they actually reach the intended source node. So, the source node, which is unaware of the loss of route error messages, attributes any genuine timeouts due to broken links. This mobility model is choosing random destination either in the horizontal or vertical directions and also more restricted movement of the nodes. Figure 10. Mobility Models – Throughput (packet) with varied Communication channel in 100 WiMax Environments Figure 11. Mobility Models -Throughput (packets) with varied communication channel in 200 WiMax Environments Figure 12. Mobility Models – Throughput (packets) with varied communication channel in 300 WiMax Environments Figure 13. Mobility Models – Throughput (packets) with varied Communication channel in 400 WiMax Environments As shown in the Figures 10,11,12,13, in all 100,200,300 and 400 WiMax nodes Gauss Markov model gives high throughput whereas the Random waypoint and Manhattan models perform with slight decreasing trend compared to Gauss Markov model. This is because the Gauss Markov Mobility Model can eliminate the sudden stops and sharp turns encountered. This Gauss Markov is a more realistic mobility model when compared with the Random Waypoint model. Because of this the chances of getting unrelated route error messages is comparatively less in the case of Gauss Markov model. 300 Nodes 0 10 20 30 40 50 2 4 6 8 10 Comminucation Channel Routing Load GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 400 Nodes 0 20 40 60 80 2 4 6 8 10 Communication Channel Routing Load GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 100 Nodes 0 100 200 300 400 500 600 700 2 4 6 8 10 Communication Channel Throughput GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 200 Nodes 0 100 200 300 400 500 600 700 2 4 6 8 10 Communication Channel Throughput GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 300 Nodes 0 100 200 300 400 500 600 700 2 4 6 8 10 Communication Channel Throughput GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 400 Nodes 0 100 200 300 400 500 600 700 2 4 6 8 10 Communication Channel Throughput GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 63 Figure 14. Mobility Models-Latency (time) with varied communication channel in 100 WiMax Environments Figure 15. Mobility Models-Latency (time) with varied communication channel in 200 WiMax Environments Figure 16. Mobility Models-Latency (time) with varied communication channel in 300 WiMax Environments Figure 17. Mobility Models-Latency (time) with varied communication channel in 400 WiMax Environments As shown in the Figures 14,15,16,17, in all 100,200,300 and 400 nodes Gauss Markov model gives high latency whereas the Random waypoint and Manhattan models perform with slight decreasing trend compared to Gauss Markov model. This Gauss Markov is a more realistic mobility model when compared with the Random Waypoint model. Because of this, the chances of getting unrelated route error messages is lower in the case of Gauss Markov model. 9. Conclusion In this paper, the three mobility models have been taken up and their performance have been compared with different stressful WiMax environments with ns-2. The performance metric of PDF, Routing load, Throughput and Latency for DSR protocols under the different simulation environment with varying communication channel has been computed. As a result, through simulation, it reveals that the throughput, latency and routing load are high in Gauss Markov Mobility model. This is due to a more realistic mobility model. Because of this the chances of getting unrelated route error messages is lower in the case of Gauss Markov Model when compared Random Waypoint mobility Model. It also shows that packet delivery fraction is high in Manhattan Grid model. This is due to the more restricted movement of the nodes in the network, which leads to slightly lesser number of broken links and subsequently lowering the chances of getting a stray route error message. Compared to Manhattan and Gauss Markov models the Random waypoint model is stable. References [1] T.Camp, J.Boleng, V.Davies, “ A Survey of Mobility Models for Ad Hoc Network Research”, in Wireless Communication and (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Appications, Vol.2, no 5, pp. 483-502, 2002. [2] C. Bettsltter, G. Resta, P.Santi, “ The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks”, IEEE Transactions on Mobile Computing, July -September 2003, pp 257-269 [3] Chen, J, Wang, C., Tsai, F., Chang, C., Liu, S.,Guo,J., Lien, W., Sum, J., Hung, C., “The Design and Implementation of WiMax Module for ns-2 Simulator”, ACM Valuetools 2006,Pisa,Italy,ACM Press, New York (2006) [4] Jenhui Chen, Chih-Chieh Wang,“The Design and Implementation of WiMax Module for ns-2 Simulator”,WNS2-06. [5] Cicconetti,C., Erta, A., Lenzini,L.,Mingozzi, E. “Performance Evaluation of the Mesh Election Procedure of IEEE 802.16/WiMax”, MSWiM’07,October 22-26,2007,Chania 100 Nodes 0 0.005 0.01 0.015 0.02 2 4 6 8 10 Communication channel Latency GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 200 Nodes 0 0.005 0.01 0.015 0.02 2 4 6 8 10 Communication Channel Latency GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 300 Nodes 0 0.005 0.01 0.015 0.02 0.025 2 4 6 8 10 Communication Channel Latency GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT 400 Nodes 0 0.02 0.04 0.06 2 4 6 8 10 Communication channel GAUSS-MARKOV MANHATTAN GRID RANDOM WAY POINT(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 64 [6] Leonardo Betancur, Roberto C. Hincaple, Roberto Bustamante, “WiMax Channel-Phy Model in Network Simulator 2”, Oct 10, 2006. [7] Shiang Ming Huang, “NCTUns simulation tool for WiMax modeling”, WICON 2007, Oct 22-24, 2007. [8] Bohnert, T.M.,Jakubiak, J.,Katz, M.,Koucheryavy, Y.,Monteiro,E., Borcoci,E, “On Evaluating a WiMax Access Network for Isolated Reserch and Data Networks Using NS-2”, Springer-Verlag Berlin Heidelberg 2007. [9] Cao,M., Raghunathan,V and Kumar, P.R A tractable algorithm for fair and efficient uplink scheduling of multi-hop Wimax mesh networks. Proc. WiMesh 2006, Reston(VA),USA, Sep.25,2006,pp 101-108. [10] Elizabeth M.Royer and C.K Toh “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personeal Communications, April 1999,pp 46-55. [11] S.Azad,A Rahman and F.Anwar,”A Performance Comparison of Proactive and Reactive Routing Protocols of Mobile Ad-hoc NET work(MANET),” Journal of Engineering and Applied Sciences 2(5),2007, pp 891-896. [12] Perkins C.E and Royer.E.M, “Ad Hoc On-demand Distance Vector Routing” In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications,New Orleans,LA,February 1999,pp.46-55 [13] Network Simulator 2 (NS-2), http://www.isi.edu/nsnam/ns/[14] NDSL WiMax Module for ns2 Simulator, http://nds1.csie.cgu.edu.tw/wimax_ns2.php [15] The WiMax forum.available at http://www.wimaxforum.org/home/. [16] The WiMax module for ns-2.available at http://ndsl.csie.cgu.edu.tw/wimax_ns2.php. [17] BonMotion Scenario Generation. www.informatik.unibonn.de/IV /BonnMotion/Authors Profile N Vetrivelan Research Scholar, Department of Computer Applications, National Institute of Technolgoy, Trichy. India. Working as an Assistant Professor in Periyar Maniammai University, Thanjavur, India With 15 Years of Engineering Collegiate experience. Presented five International Papers and published two papers in the refereed journals. Presented paper in IAENG International Conference at Hong Kong. Established WiMax Broad Band connection with Six rural villages in and around Thanjavur district under PURA. Dr. A V Reddy received Ph.D in II.Sc Bangalore, India. Working as a Professor, Department of Computer Applications, National Institute of Technology, Trichy, Tamilnadu, India with 25 Years of Academic experience. Published Six International journal Papers in refereed journal and also ten International papers presented. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 65 Partial Aggregation for Multidimensional Online Analytical Processing Structures Naeem Akhtar Khan1 and Abdul Aziz2 1Faculty of Information Technology, University of Central Punjab, Lahore, Pakistan naeemkhan@ucp.edu.pk 2Faculty of Information Technology, University of Central Punjab, Lahore, Pakistan aziz@ucp.edu.pk Abstract: Partial pre-computation for OLAP (On-Line-Analytic Processing) databases has become an important research area in recent years. Partial pre-aggregation is implemented to speed up the response time of queries that are posed for the array-like decision support interface, subject to the different constraint that all pre-computed aggregates must fit into storage of a pre-determined calculated size. The target query workload contains all base and aggregate cells that are stored in a multidimensional structure (i.e. cube). These queries are in fact range queries pre-defined by users for the support of decision makers. The query workload of an OLAP scenario is the set of queries expected by the users. Most of the published research only deals with the optimization for the workload of views in the context of ROLAP (Relational OLAP). Many researchers have criticized partial-computation schemes, optimized for views that lack of support to ad-hoc querying. The other main aspect is that a view may be too large for precompuutatio that calculate very small answers. In this paper, we study the problems of partial pre-computation for point queries, which are best for MOLAP (Multidimensional OLAP) environment. We introduce multidimensional approach for efficiency of the cover-based query processing and the effectiveness of PC Cubes. Keywords: OLAP, MOLAP, Data-Cubes, Data warehouse. 1. Introduction A data warehouse (DW) is centralized repository of summarized data with the main purpose of exploring the relationship between independent, dimensions, static variables and dependent, dynamic, variables facts or measures. There is a trend within the data warehousing community towards the separation of the requirements for preparation and storage necessary for analyzing the accumulated data and the requirements for the exploration of the data with the necessary tools and functionality required [1]. In terms of the storage necessities, a convergent tendency is towards a multi-dimensional hypercube model [2]. On the other hand in terms of analysis and the tools required for On-Line Analytic Processing (OLAP), there is a trend towards standardizing this as well; e.g., the efficient OLAP Council’s Multi-Dimensional Application Programmers Interface (MD-API). Although the trends are for separating the storage from the analysis, the actual physical implementation of DW/OLAP systems reconnects them. This is an evident from the parade of acronyms used today, e.g., MOLAP, ROLAP, DOLAP, HOLAP, etc., where all physical implementation determines the advantages and disadvantages of storage access an analysis capabilities and also determines any possible extensions in future to the model. In the models quoted above, the two most common in practice are the Multidimensional On-line Analytic Processing (MOLAP) model and the Relational On-line Analytic Processing (ROLAP) model. The main advantage of ROLAP, which depends on relational database (RDB) technology, is that the database technology is well standardized (e.g., SQL2) and is readily available too. This permits for the implementation of a physical system, based on readily available technology and open standards. As this technology is well studied and researched, there are mechanisms which allow for transactions and authorization schemes, thus allowing for multi-user systems with the ability to update the data as required. The main disadvantage of this technology is that the query language as it exists (SQL) is not so sufficiently powerful or flexible enough to support true OLAP features [1]. Furthermore, there is an impedance difficulty, that the results returned, tables, always required to be converted to another form before further programming abilities can be performed. The main advantage of MOLAP, which depends on generally proprietary multi-dimensional (MDD) database technology, is based on the disadvantages of ROLAP and is the major reason for its creation. MOLAP queries are quite powerful and flexible in terms of OLAP processing. The physical model further closely matches the multidimensional model, and the impedance issue is remedied within a vendor’s side. However, there are disadvantages of the MOLAP physical model: 1st) There is no real standard for MOLAP; 2nd) there are no off-the-shelf MDD databases per se; 3rd) there are scalability problems; and 4th) there are problems with authorizations and transactions. As the physical implementation ultimately determines the abilities of the system, it would be advised to find a technology that combines and maximizes the advantages of both ROLAP and MOLAP while at the same time minimizing the dis-advantages. Online Analytical Processing (OLAP) has become a basic component of modern decision support systems. As claimed in [3] introduced the data-cube, a relational operator as well as model used for computing summary views of data that can, in turn, significantly improve the response time of core OLAP operations such as roll-up, drill down, and slice and (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 66 dice, drill down approach is reflected in Figure 1. Typically developed on top of relational data warehouses these summary views are formed by aggregating values across different attribute combinations. For a d-dimensional input set R, there are 2d probable group bys. A data-cube as well as a lattice which is often used for representing the inherent relationships between group-bys [5], there are two standard data-cube representations: ROLAP (set of relational tables) and MOLAP (multi-dimensional OLAP). The main differences between ROLAP and MOLAP architectures are shown in Table 1 [4]. Figure 1. Hierarchies in data The array-based structure, MOLAP (Multi-dimensional OLAP), has the advantage that native arrays provide an immediate form of indexing for queries of cube. Research has shown, however, that MOLAP has scalability problems [6]. For example, high-dimension data-cubes represent tremendously sparse spaces that are not easily adapted to the MOLAP model. Hybrid indexing schemes are normally used, significantly diminishing the power of the model. Table 1: ROLAP Vs MOLAP Feature ROLAP MOLAP Usage Variable performance Good performance Relational engine Multidimensional engine Storage and Access Tables/tuples Proprietary arrays SQL access language Lack of a standard language Third party tools Sparse data compression Database Size Easy updating Difficult updating Large space for indexes 2% index space Gigabyte-Terabyte Gigabyte Moreover, since MOLAP requires to be integrated with standard relational databases, middleware of some form must be employed for handling the conversion between relational and array-based data representations. The efficiency of relational model, ROLAP (Relational OLAP), does not suffer by such restrictions. In standard relational tables its summary records are stored directly without any need for data conversion. ROLAP table based data representation does not pose scalability problems. Yet, many current commercial well-known systems use the MOLAP approaches. The main issue, as outlined in [6] is the indexing problem for the fastest execution of OLAP queries. The main problem for ROLAP is that it does not offer an immediate and fast index for OLAP queries. Many wellknnow vendors have chosen the sacrifice scalability for performance. Query performance issue is discussed for ROLAP and proposed a novel, distributed multidimennsiona ROLAP efficient indexing scheme [7]. They showed that the ROLAP advantage for high scalability can be maintained, while at the same time providing a rapid index for OLAP queries. They proposed a distributed indexing efficient scheme which is a combination of packed R-trees with distributed disk striping and Hilbert curve based data ordering. Their method requires very meager communication volume between processors and works in very low bandwidth connectivity multi-processor environments such as Beowulf type processor clusters or workstation farms. There is no requirement of a shared disk and scales well with respect to the number of processors used, and for further improving the scalability of ROLAP with respect to the size and dimension of the data set (which is already better than MOLAP’s scalability), they extend their indexing scheme to the partial cube case. The large number of group-bys, 2d, is a major problem in practice for any data-cube scheme. They considered the case where they do not wish to build (materialize) all group-bys, but only a subset. For example, a user definitely wants to only materialize those group-bys that are frequently used, thereby saving disk space and time for the cube construction. The problem was to find a best way to answer effectively those less frequent OLAP queries which required group-bys that had not yet been materialized. Solving this problem they presented an indexing scheme, based on “surrogate group-bys”, which answers such queries effectively. Their experiments showed that their distributed query engine is almost as efficient on “virtual” group-bys as it is on ones that actually exist. In summary, they claimed that their method provides a framework for distributed high performance indexing for ROLAP cubes with the following properties [7]. In practical, it shows lower communication volume, fully adapted to external memory. There is no requirement of shared disk, maintainable, incrementally; it is efficient for spatial searches in various dimensions, scalable with respect to data sizes, dimensions, and number of processors. They implemented their distributed multi-dimensional ROLAP indexing scheme in STL and MPI, C++ and tested it on a 17 node Beowulf cluster (a frontend and 16 compute nodes). While easily extendable for sharing everything multiproceessors their algorithms performed well on these lowcoos commodity-based systems. Their experiments showed that for RCUBE index construction and updating, close to optimal speed has been achieved. A RCUBE index having fully materialized data cube of ≈640 million rows (17 Gigabyttes on a 16 processor cluster can be generated in just within 1 minute. Their method for distributed query resolution also exhibited good speedup achieving, for example, a speedup of 13.28 on just 16 processors. For distributed query resolution in partial data-cubes, their experiments showed that searches against absent (i.e. non(IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 67 materialized) group-bys can typically be easily resolved at only a small additional cost. Their results demonstrated that it is possible to build a ROLAP data-cube that is scalable and tightly integrated with the standard relational database approach and, at the same time, provide an efficient index to OLAP queries. 2. DW and OLAP Technologies The prominent definition of Data Warehouse is a "subjectorieented integrated, nonvolatile and time-variant collection of data in support of management's decisions" [8]. A data warehouse is a well organized single site repository of information collected from different sources. In data warehouse, information is organized around major subjects and is modeled so as fast access to summarize data. "OLAP" as discussed in [9],[10] refers to analysis functionalities generally used for exploring the data. Data warehouse has become a most important topic in the commercial world as well as in the researcher’s community. Data warehouse technology has been mostly used in business world, in finance or retail areas for example. The main concern is to take benefits from the massive amount of data that relies in operational databases. According to [11], the data-modeling paradigm for a data warehouse must fulfill the requirements that are absolutely different from the data models in OLTP environments, the main comparison between OLTP and OLAP environment is reflected in Table 2. Table 2: OLTP Vs OLAP Feature OLTP OLAP Amount of data retrieved per transaction Small Large Level of data Detailed Aggregated Views Pre-defined User-defined Age of data Current (60-90 days) Historical 5-10 years and also current Typical write operation Update, insert, delete Bulk insert, almost no deletion Tables Flat tables Multi-Dimensional tables Number of users Large Low-Med Data availability High (24 hrs, 7 days) Low-Med Database size Med (GBTTB High (TB – PB) Query Optimizing Requires experience Already “optimized” The data model of the data warehouse must be simple for the decision maker to understand and for write queries, and must get maximum efficiency from queries. Data warehouse models are called hyper-cubes or multidimensional models and have been prescribed by [12]. The Models are designed for representing measurable indicators or facts and the various dimensions that characterize the facts. For example, in a area of retail, typical indicators are price and amount of a purchase, dimensions being location, product, customer and time. A dimension is mostly organized in hierarchy, for example the location dimension can be aggregated in city, division, province, country. The "star schema" molds the data as a simple cube, where hierarchical relationship in a dimension is not explicit but is rather encapsulated in attributes; the model of star schema with dimensions is reflected in Figure 2. Figure 2. Star Schema The dimension tables are normalized by “snowflake schema”, and make it possible for explicitly representing the hierarchies by separately identifying dimension in its different granularities. At last, when multiple fact tables are required, the "fact constellation" or "galaxy schema" model allows the design of collection of stars. OLAP architectures adopt a multi-tier architecture as reflected in Figure 3 where first tier is a warehouse server, implemented by a relational DBMS. Data of interest must be extracted from OLTP systems (operational legacy databases), extracted, cleaned and transformed by ETL (Extraction, Transformation, Loading) tools before going to load in the warehouse. Figure 3. How does an OLAP piece fit together This process aims to consolidate heterogeneous schema (structure heterogeneity, semantic heterogeneity) and for reducing data in order to make it conform to the data warehouse model (by implementing aggregation, discretiizatio functions). Then the data warehouse holds high quality, efficient historical and homogeneous data. The second tier is a data mart, a data mart handles data received from the data warehouse, which is reduced for a selected subject or category. The main focus of data marts is to isolate data of interest for a smaller scope or department, thus permitting the focusing on optimization needs for this data and increase more security control. However this intermediate tier of data mart is optional and not mandatory. The OLAP server is implemented at 3rd level. It optimizes and calculates the hypercube, i.e. the set of fact values for all the relevant tuples (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 68 of instances for different dimensions (also called embers). In order for optimizing accesses against the data, query results are advance calculated in the form of aggregates. OLAP operators allow materializing different views of the hypercube, allowing interactive queries from decision makers and analysis of the data. Common OLAP operations include drilldown, roll-up, slice and dice, rotate. The fourth tier is an OLAP client, which provides a user interface with various reporting tools, analysis tools and data mining tools for obtaining results. Software solutions are existed for a traditional use. 3. Distributed Index Construction for ROLAP Different methods have been proposed and recommended for building ROLAP data-cubes [13], [14], [15] but there are only very few results available for the indexing of such cubes. For sequential query processing, [16] proposed an indexing model, which is composed of a collection of btreees While adequate for low-dimensional data-cubes, btrree are inappropriate for higher dimensions in that (a) multiple, redundant attribute orderings are required to support arbitrary user queries (b) their performance deteriorates rapidly with increased dimensionality. In [17] proposed the cube-tree, an indexing model which is based on the concept of a packed R-tree [18]. In the dimension of parallel query processing, a typical approach used by current commercial systems like ORACLE 9i RAC for improving throughput by distributing a stream of incoming queries over multiple processors and having each processor answer a subset of queries. But this type of an approach provides no speedup for each individual query. For OLAP queries, which are time consuming, the parallelization of each query is important for the scalability of the entire OLAP system. With respect to the parallelization for general purpose environments of R-tree queries, a number of researchers have presented solutions. As claimed in [19] Koudas, Faloutsos and Kamel presented a Master R-tree structure that employs a centralized index and a collection of distributed data files. Schnitzer and Leutenegger’s Master-Client R-tree [20] improves upon the earlier model by partitioning the central index into a smaller master index as well as a set of associated client indexes. While offering considerable performance advantages in generic indexing environments, neither approach is wellsuiite for OLAP environment systems. In addition to the sequential problems on the main server node, both utilize partitioning methods that can lead to the localization of searches. Furthermore, neither approach provides the methods for incremental updates. Data reliability is major issue in data warehouses and many solutions have been proposed for its solution. Replication is a widely used mechanism for protecting permanent data loss while replica placement will significantly impact data reliability. Several replica placement policies for different objectives, have been proposed and deployed in real-world systems, like RANDOM in GFS, PTN in RAID, Q-rot in [16], [13], [21] have analyzed how the system parameters, such as object size, system capacity, disk and switch bandwidth, could affect the system’s reliability. However, they only focused on the rough trend about their impact but did not illustrate the correct optimal values of these parameters. The co-impact of these parameters was not also discussed. Furthermore, for getting the accurate reliability value, some models are so complicated that it is difficult to figure out the best value of each parameter. In [22] worked for designing a reliable large-scale data warehouse or storage system and presented a new objectbassedrepairing Markov model, which induces many key challenges. One problem was to figure out some basic system parameters, such as the number of nodes, the total number of stored objects and the bandwidth of switch and the node. For designing a reliable system with the optimal system parameters, compared with previous work, their approach makes a significant contribution in two aspects. Firstly, they presented a new object-based Markov model for quantifying the impact of key system parameters on the system reliability in three replica placement strategies. They compared their model with previous complex models; this object-based compact model not only turns to be easier for solving because of its smaller state transition matrix, but also leads to more integrative and practical efficient results. Secondly, they proposed a two-step analyzing process. The first is to find out the comparatively precise optimal value of a system parameter by independently analyzing its impact on the system reliability when other system parameters are fixed. The second is to figure out the best possible combination of these parameters by analyzing their integrated and complex impacts on the system reliability while all of them are tuned. Their analysis results showed that the optimal values do exist and have simple formulas. They presented a new efficient object-based repair model and by analyzing this model, they worked out the individual optimal value of parameters and their optimal combination. The results obtained by them can provide the engineers with direct instructions to design reliable systems. 4. Related Work Here we introduce the lattice view that depicts the relationships between existing views, some algorithms of the pre-computation of views, answering query using the materialized views and view selection. 4.1 The View Lattice Framework The CUBE BY in [23] has resulted in the computation of views which related to SQL queries which has been grouped on all possible combinations of the dimension attributes. Those views are usually denoted by the grouping attributes, e.g. T, L, P, LT, PT, PL, PLT, and All for the example of database with three attributes Time(T), Location(L) and Product(P). As claimed by [24] that a lattice is used to depict the relationship between views. An aggregate view is represented by each node in the lattice. In the lattice view edge existed form node i to node j, view j can be computed from view i to view j which contains one attribute less than view i. In this case, view i is called, parent view of j. in this situation there is a basic view on which every view is dependent. The complete aggregation view “ALL” can be computed from any other view of lattice. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 69 Figure 4. Lattice View 4.2 Pre-computation of aggregates In Figure 4 lattice views are shown, for example database which have three dimensions, Time, Location and Product which are reflected as T, L and P respectively. A view is labeled by the dimension’s name, where it is aggregated on view PLT is the basic view while PL is parent view. A lot of aggregation is involved on OLAP queries in data warehouse. Performance can greatly be improved by the precompuutatio of aggregates. Many researchers have developed pre-computation algorithms for efficient computing all possible views, which are so called view materialization. In [25] and [26] different efficient view materialization algorithms have been proposed, e.g., Overlap, Pipesoft and PipeHash, which incorporate many efficient optimization techniques, such as using the data sorting in a particular order for computing all views that are prefixes in that order, computing a view from its smallest previously computed parent, and computing the views with most common prefixes in a pipelined technique. In [27] there are some efforts have been made for studying, how the skewed data may affect the pre-computation of aggregates and an approach for dynamically manage the memory usage is recommended. A comparison has been made in [28], difference between the view materialization in MOLAP and ROLAP further an array-based pre-computation efficient algorithm for MOLAP is proposed. In this algorithm the partitions of views is stored in main memory array and further overlaps the computation of different views while using minimum storage memory for each view. In [29] author examined the pre-computation on compressed MOLAP database and some algorithms for the computation of view without de-compression is proposed. In [30] suggested another pre-computation algorithm for MOLAP. One distinct feature in these algorithms was that the aggregation cells are managed in the similar way as the source data. Primary cells and aggregation cells are stored together single data structure, further proposed one multidimensional array, which allows them for quickly accessing. In this algorithm pre-computation considers the points in multidimensional space. The algorithm examines the coordinates of the cells and relies on the relationships among cells for determining how to perform efficient aggregation. A graph-theoretical model is employed for ensuring the correctness of the summation computation. 4.3 View Selection The main issue in full computation of views is storage space; so many researchers study this problem and recommended partial-computation. In [31] efficient approach was proposed for choosing a set of views for materialization under a situation of limited storage space. They introduced a linear cost model; this algorithm assumes that the cost of answering a query is related to the size of view from which the respond of the query can easily be computed. This linear cost model was verified by the experiments. In a greedy view selection algorithm which tries to decide which aggregate view is best for minimizing the query cost. This greedy view selection algorithm first chooses the base view. Materializing one more view can allow some queries which can be easily answered by a smaller metalized view, in this way query cost can be reduced. Their proposed algorithm chooses the view which produces the more reduction in query cost. Research proved that the benefit of the aggregate views selected by this algorithm in no worse than (0.63-f) times the benefit of an optimized selection. The same problem was discussed in [32] and another view selection algorithm PBS (Pick by Size) was proposed. The main difference was that PBS selects the views solely based on the size of the views. In each turn, the view with the smaller size from unselected views is chosen until the total size of the selected views reaches the allocated space limit. 4.4 Query Processing In [33], the traditional query optimization algorithms were generalized to optimize the query in the presence of materialized views. In [34] proposed some techniques for rewriting a given SQL query, such that it uses one or more than one materialized view. They also proposed a semantic approach for determining whether the information existing in a view is sufficient for answering a query. Another query rewriitin method was suggested in [35], this technique can utilize the views having different granularities, aggregation granularities and selection regions. Generally, for an OLAP query, their can be many equivalent re-writings using different materialized cubes/views in different ways. Their execution cost is different from one another. An efficient algorithm is also proposed in [35] for determining the set of materialized views used in query re-writing. 5. Recommendations for an Efficient Partial pre-Aggregation A completely full pre-computation, where all possible aggregates have been pre-computed, can provide the best and most efficient query performance, but in our point of view this approach in not recommended for the following reasons: · A full pre-computation requires a great storage space for aggregates, so it often exceeds the available space. · This technique is not based on cost effective use of resources-beneficial, in [32], it is mentioned that the gains from pre-computation outweigh the cost of further disk space after some level of precomputtation · Maintenance cost is increased. · It takes long load time. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 70 · A full pre-computation is not suitable as very sparse cube (wastage of space) for high cardinality. However in the situation of fully pre-computation environment, to overcome the storage limitations it is advisable that cube may be partitioned. One logical cube of data should be spread across multiple physical cubes on distinct servers. Divide and Concur approach helps alleviate the scalability limitations of full pre-computation approach. The other approach, which is partial pre-computation of aggregates, can resolve problems of fully aggregation. The main objective of a partial pre-computation technique is to select a certain amount of aggregates for computing before querying time, in this way query answering time can be optimized. But there are two major issues about the optimization process: · How many partial pre-computed aggregates should be computed? · What kind of queries is optimized for precompuutatio strategy? The first question depends upon the storage available, we recommends that 40% of all possible aggregates should be computed in advance. Few years back it was recommended by Microsoft, as the vendor of one of the popular OLAP systems that 20% of all possible aggregates should be computed in advance, but now the technology has improved and storage capacity can be achieved by very low cost. The best answer of second question is that these queries should be those that most expected by the decision maker of OLAP application. This type of answer in not so easy because it varies from user to user and application to application, for this purpose and understanding the question systematically, one needs to precisely categorize the chunk of queries as an object for optimization, this type set of queries or expected queries is often called ”query workload”. Pattern of expected queries can be obtained from other same type of case studies and navigational data analysis task. There are many algorithms for partial pre-computation which have already been discussed. For optimized and efficient processing of OLAP queries, most commonly used approach is to store the results of frequently issued queries by decision makers in to summary tables, and further makes use of them for evaluating other queries, this approach is best. In our point of view PBS (Pick by size) algorithm is so fast and best as it will facilitate database administrators for determining the points, where diminishing returns outweigh the cost of the additional storage space. This algorithm also shows how much space should be allocated for pre-computation. 6. Conclusion The partial pre-computation is most popular research area in OLAP environment. Most of the published papers for partial pre-computation are about optimized performance of views as the query workload. Practically users do not care about the processing overhead and the time used in determining the output of the given query, when planning to implement partial pre-computation strategy. For implementation of point queries, the processing overhead is most important fact of consideration. PBS approach is efficient, and selection by PBS is much effective because PC Cube generated by the PBS leads to shorter time required for answering the point queries. It has most excellent overall performance among variations of member selection algorithms. References [1] Thomsen, Erik, OLAP Solutions: Building Multidimensional Information Systems, John Wiley and Sons, 1997. [2] Agrawal, R., Gupta, A., Sarawagi, S., “Modeling Multidimensional Databases”, Proceedings of the 13th International Conference on Data Engineering, pp. 232-243, 1997. [3] J. Gray, A. Bosworth, A. Layman, and H. Pirahesh, “Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals”, Proceeding of the 12th International Conference On Data Engineering, pages 152–159, 1996. [4] Aejandro A. Vaisman, “Data Warehousing, OLAP, and Materialized Views”, A Survey Technical Report TR015-98, University of Buenos Aires, Computer Science Department, 1998. [5] V. Harinarayan, A. Rajaraman, and J. Ullman, “Implementing data cubes”, Proceedings of the 1996 ACM SIGMOD Conference, pages 205–216, 1996. [6] S. Agarwal, R. Agrawal, P. Deshpande, A. Gupta, J. Naughton, R. Ramakrishnan, and S.Sarawagi, “On the computation of multidimensional aggregates”, Proceedings of the 22nd International VLDB Conference, pages 506–521, 1996. [7] F. Dehne, T. Eavis and A. Rau-Chaplin, “Parallel Multi-Dimensional ROLAP Indexing”, Proceedings of the 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, (CCGRID’03) 2003. [8] W.H. Inmon Building the Data Warehouse 3rd Edition, Eds.Wiley and Sons, 1996. [9] S. Chaudhuri, U. Dayal “An Overview of Data Warehousing and Olap Technolog”, SIGMOD Record 26(1), 1997. [10] P. Vassiliadis P., T. Sellis, “A Survey of Logical Models for OLAP Databases”, SIGMOD Record Volume 28, Number 1, March, 1999. [11] R. Kimball, The Data Warehouse Toolkit, J.Wiley and Sons, Inc, 1996. [12] L. Cabibbo and R. Torlone, “A Logical Approach to Multidimensional Databases”, Proceedings of the 6th International Conference on Extending Database Technology (EDBT'98), Valencia, Spain, 1998. [13] V. Harinarayan, A. Rajaraman, and J. Ullman, “Implementing data cubes” Proceedings of the 1996 ACM SIGMOD Conference, pages 205–216, 1996. [14] K. Ross and D. Srivastava, “Fast computation of sparse data cubes”, Proceedings of the 23rd VLDB Conference, pages 116–125, 1997. [15] S. Sarawagi, R. Agrawal, and A.Gupta, “On computing the data cube”, Technical Report RJ10026, IBM Almaden Research Center, San Jose, California, 1996. [16] H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman, “Index selection for olap”, Proceeding of the 13th International Conference on Data Engineering, pages 208–219,1997. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 71 [17] N. Roussopoulos, Y. Kotidis, and M. Roussopolis, “Cubetree: Organization of the bulk incremental updaate on the data cube”, Proceedings of the 1997 ACM SIG-MOD Conference, pages 89–99, 1997. [18] N. Roussopolis and D. Leifker, “Direct spatial search on pictorial databases using packed r-trees”, Proceedings of the 1985 ACM SIGMOD Conference, pages 17–31, 1985. [19] N. Koudas, C. Faloutsos, and I. Kamel, “Declustterin spatial databases on multi-computer architecture”, In Proceedings of Extended Database Technologies, pages 592–614, 1996. [20] B. Schnitzer and S. Leutenegger, “Master-client rtreees a new parallel architecture”, 11th International Conf-erence of Scientific and Statistical Database Management, pages 68–77, 1999. [21] I. Kamel and C. Faloutsos, “On packing r-trees”, Proceedings of the Second International Conference on Information and Knowledge Management, pages 490–499, 1993. [22] K.Du, Z.Hu, H.Wang,Y.Chen, S.Yang and Z.Yuan, “Reliability Design for Large Scale Data Warehouses”, Journal of Computing, Vol.3, No.10, pp 78-85 October 2008. [23] J.Gray, A.Bosworth, A.Layman, H.Pirahesh., “Data Cube: A Relational Aggregation Operator Generalizing Group-By,Cross-Tabs, and Sub-Totals”, In Proceedings of International Conference on Data Engineering (ICE’96), New Orleans, February,1996. [24] V. Harinarayan, A.Rajaraman, and J.D.Ullman, “Implementing Data Cubes Efficiently”, In Proceedings of SIGMOD, pages 205-216,1996. [25] Sameet Agarwal, Rakesh Agarwal, Prasad M. Deshpandre, Asnish Gupta, Jeffrey F.Naughton, Ragnu Ramakrishnan, Sunita Sarawagi, “On the Computation of Multidimensional Aggregates”, In Proceedings of the 22nd VLDB Conference, Bombay, India, pages 506-521,1996. [26] P.M.Deshpande, S.Agarwal, J.F.Naughton, and R.Ramakrishnan, “Computation of Multidimensional Aggregates”, Technical Report 1314, University of Wisconsin-Madison, 1996. [27] Yu,J.X., Hongjun Lu., “Hash in Place with Memory Shifting: Datacube Computation Revisited”, In Proceedings of 15th International Conference on Data Engineering. Page: 254 March, 1999. [28] Y.Zhao, P.M. Deshpande, and J.F.Naughton., “An Array-based Algorithm for Simulataneous Multidimensional Aggregates”, In Proceedings of ACM SIGMOD, pages 159-170, 1997. [29] Li,J.,Rotem, D., Srivastava, J., “Aggregation Algorithm for very large compressed Data Warehouses”, In Proceedings of 25th very large Database (VLDB) Conference. Edinburgh, Scotland, 1999. [30] Woshun Luk., “ADODA: A Desktop Online Data Analyzer”, In 7th International Conference on Database Systems for Advanced Applications (FASFAA,01), Hong Kong, China, April,2001. [31] V.Harinarayan, A.Rajaraman, and J.D.Ullman, “Impleminting Data Cubes Efficienty”, In Proceedings of SIGMOD, pages 205-206, 1996. [32] A.Shukla, P.Deshpande, and J.Naughton, “Materialized View Selection for Multidimensional Datasets”, In Proceedings on 24th VLDB Conference, New York, 1998. [33] S.Chaudhuri,R.Krishnamurthy, S.Potamianos, and K.Shim., “Optimizing Quereis with Materialized Views”, In Proceedings of the 11th IEEE International Conference on Data Engineering, pages 190-200, 1995. [34] D.Srivastava, S.Dar, H.V.Jagadish, A.Y.Levy., “Answering Queries with Aggregation using views”, In Proceedings of 22nd VLDB Conference, Bombay, India, pages 318-329, 1996. [35] C.S.Park, M.H.Kim and Y.J.Lee., “Finding an Efficient Rewriting of OLAP Queries Using Materialized Views in Data Warehouses”, Decision Support Systems, vol.32, No.4, pages 379-399,2002. Authors Profile Naeem Akhtar Khan received the B.S. degree in Computer Science from Allama Iqbal Open University, Islamabad, Pakistan in 2005 and M.S. degree in Computer Science from University of Agriculture, Faisalabad, Pakistan in 2008. He is currently pursuing Ph.D. (Computer Science) degree in University of Central, Punjab, Lahore, Pakistan. His research interests include large-scale data management, data reliability, Data Mining, MOLAP. Dr. Abdul Aziz did his M.Sc. from University of the Punjab, Pakistan in 1989; M.Phil and Ph.D in Computer Science from University of East Anglia, UK. He secured many honors and awards during his academic career from various institutions. He is currently working as full Professor at the University of Central Punjab, Lahore, Pakistan. He is the founder and Chair of Data Mining Research Group at UCP. Dr. Aziz has delivered lectures in many universities as guest speaker. He has published large number of research papers in different refereed international journals and conferences. His research interests include Knowledge Discovery in Databases (KDD) -Data Mining, Pattern Recognition, Data Warehousing and Machine Learning. He is member of editorial board for various well known journals and international conferences including IEEE publications. (e-mail: aziz@ucp.edu.pk). (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 72 Browser Extensible Secured Hash Password Authentication for Multiple Websites 1T.S.Thangavel and 2Dr. A. Krishnan 1 AP/Dept. of M.Sc(IT), K.S.Rangasamy College of Technology, Tiruchengode 637215,Tamilnadu,India. tsthangavel123@yahoo.in 2 Dean, K.S.Rangasamy College of Technology, Tiruchengode 637215,Tamilnadu,India. a_krishnan26@hotmail.com Abstract: The techniques such as secured socket layer (SSL) with client-side certificates are well known in the security research community, most commercial web sites rely on a relatively weak form of password authentication, the browser simply sends a user ’s plaintext password to a remote web server, often using SSL. Even when used over an encrypted connection, this form of password authentication is vulnerable to attack. In common password attacks, hackers exploit the fact that web users often use the same password at many different sites. This allows hackers to break into a low security site that simply stores username/passwords in the clear and use the retrieved passwords at a high security site. Recently, some collisions have been exposed for a variety of cryptographic hash functions including some of the most widely used today. Many other hash functions using similar constructions can however still be considered secure. Nevertheless, this has drawn attention on the need for new hash function designs. This work developed an improved secure hash function, whose security is directly related to the syndrome decoding problem from the theory of error-correcting codes. The proposal design and develop a user interface, and implementation of a browser extension, password hash, that strengthens web password authentication. Providing customized passwords, can reduce the threat of password attacks with no server changes and little or no change to the user experience. The proposed techniques are designed to transparently provide novice users with the benefits of password practices that are otherwise only feasible for security experts. Experimentation are done with Internet Explorer and Fire fox implementations and report the result of initial user. Keywords: password authentication, secured hash, multiwebbsit password, pseudo random, phishing, cryptographic password 1. Introduction A random password generator is software program or hardware device that takes input from a random or pseudo-random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of randomness such as dice or coins, or they can be generated using a computer. While there are many examples of "random" password generator programs available on the Internet, generating randomness can be tricky and many programs do not generate random characters in a way that ensures strong security. A common recommendation is to use open source security tools where possible, since they allow independent checks on the quality of the methods used. Note that simply generating a password at random does not ensure the password is a strong password, because it is possible, although highly unlikely, to generate an easily guessed or cracked password. A password generator can be part of a password manager. When a password policy enforces complex rules, it can be easier to use a password generator based on that set of rules than to manually create passwords. In situations where the attacker can obtain an encrypted version of the password, such testing can be performed rapidly enough so that a few million trial passwords can be checked in a matter of seconds. The function rand presents another problem. All pseudo-random number generators have an internal memory or state. The size of that state determines the maximum number of different values it can produce, an n-bit state can produce at most 2n different values. On many systems rand has a 31 or 32 bit state, which is already a significant security limitation. The main cryptographic hash function design in use today iterates a so called compression function according to Merkle’s [12] and Damgard’s[13] constructions. Classical compression functions are very fast but, in general, cannot be proven secure. However, provable security may be achieved with compression functions designed following public key principles, at the cost of being less efficient. This has been done for instance by Damgard, where he designed a hash function based on the Knapsack problem. Accordingly, this function has been broken by Granboulan and Joux,[10] using lattice reduction algorithms. The present paper contributes to the hash function family by designing functions based on the syndrome decoding problem, which is immune to lattice reduction based attacks. Unlike most other public key cryptosystems, the encryption function of the McEliece cryptosystem is nearly as fast as a symmetric cipher. Using this function with a random matrix instead of the usual parity check matrix of a Goppa code, a provably secure one-way function has been constructed since there is no trapdoor, its security can be readily related to the difficulty of syndrome decoding. The purpose of this paper is to improve updated parameters for the hash function. Our paper analyzes asymptotical behavior of their attack. We shall establish that this attack is exponential, such that the design for the hash function is sound. (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 73 2. Literature Review Computer applications may require random numbers in many contexts. Random numbers can be used to simulate natural or artificial phenomena in computer simulations, many algorithms that require randomness have been developed that outperform deterministic algorithms for the same problem, and random numbers can be used to generate or verify passwords for cryptography-based computer security systems. The present invention relates to the use of random numbers in such security systems, called as cryptographic applications. Specifically, the present invention pertains to generating a random number in a secure manner for such cryptographic applications. In the context of cryptographic applications[1], there may be an hostile trespasser or agent, who desires to infiltrate the security of cryptographic security system in order to gain access to sensitive, confidential, or valuable information contained therein. For example, banks often encrypt their transactions and accounts. In order to ensure the utmost security, it is essential that the security system implements a method for generating a random number that appears completely random. In this manner, a completely random password or cryptographic key presents no opening or prior knowledge that can be exploited by an hostile agent.[2] Many prior art methods exist for generating random numbers. These prior art methods typically involve the use of some type of chaotic system. A chaotic system is one with a state that changes over time in a largely unpredictable manner. To use the chaotic system[4] to generate a random number, there is some means of converting the state of the system into a sequence of bits (i.e., a binary number). In the past, chaotic systems were based on various sources, such as the sound of radio static, the output of a noisy diode, output of a Geiger counter, or even the motion of clouds. These chaotic systems can be converted to produce binary numbers by using standard techniques. For instance, a pseudo-random binary string can be generated from the digital recording of static noise via a digital microphone. Alternatively, a noisy diode can be sampled at a suitable frequency and converted into a digital signal, or a picture of an area of the sky can be taken and subsequently scanned and digitized. These resulting binary strings that are generated over time are generally random in nature. However, there are several problems associated with simply using a chaotic system as a source of random numbers.[3] First, chaotic systems can be completely or partially predicted over small amounts of time. For example, the position of clouds in some area of the sky at some time can be used to achieve reasonably accurate predictions of the position of clouds in the same area a short time into the future. Furthermore, the behavior of chaotic systems [6] can be far from completely random. For instance, a digitized picture of a cloud formation will not look like a picture of random information, but instead, will look like a cloud formation. Moreover, chaotic systems may be biased by outside sources which may be predictable. As an example, a radio signal can be affected by a strong external signal, or the behavior of a noisy diode can be changed by the surrounding temperature. All of the above problems arise because the behavior of a chaotic system may not be completely random. More specifically, an adversary observing or wishing to affect the random number source can take advantage of certain localities that may be inherent in chaotic systems. These localities can occur either in space or time. Finally, a number of existing applications including Mozilla Firefox provide convenient password management by storing the user’s web passwords on disk, encrypted under some master password. When the user tries to log in to a site, the application asks for the master password and then releases the user’s password for that site. Thus, the user need only remember the master password. The main drawback compared to PwdHash is that the user can only use the web on the machine that stores his passwords. On the plus side, password management systems do provide stronger protection against dictionary attacks when the user chooses a unique, high entropy password for each site. However, many users may fail to do this. 3. Methodology Random password generators normally output a string of symbols of specified length. These can be individual characters from some character set, syllables designed to form pronounceable passwords, or words from some word list to form a passphrase. The program can be customized to ensure the resulting password complies with the local password policy, say by always producing a mix of letters, numbers and special characters. The strength of a random password can be calculated by computing the information entropy of the random process that produced it. If each symbol in the password is produced independently, the entropy is just given by the formula where N is the number of possible symbols and L is the number of symbols in the password. The function log2 is the base-2 logarithm. H is measured in bits. An eight character password of single case letters and digits would have 41 bits of entropy (8 x 5.17). Thus a password generated using a 32-bit generator has a maximum entropy of 32 bits, regardless of the number of characters the password contains. 3.1 Secure Hashing The proposed methodology of the secure hash password system contains one-way hash functions that can process a message to produce a condensed representation called a message digest. This algorithm enables the determination of a message’s integrity, any change to the message will, with a very high probability, results in a different message digest. This property is useful in the generation and verification of digital signatures and (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 2, February 2010 74 message authentication codes, and in the generation of random numbers. The algorithm is described in two stages, preprocessing and hash computation. Preprocessing involves padding a message, parsing the padded message into m-bit blocks, and setting initialization values to be used in the hash computation. The hash computation generates a message schedule from the padded message and uses that schedule, along with functions, constants, and word operations to iteratively generate a series of hash values. The final hash value generated by the hash computation is used to determine the message digest. The design principle of hash functions is iterating a compression function (here denoted F), which takes as input s bits and returns r bits (with s > r). The resulting function is then chained to operate on strings of arbitrary length(Fig 1). The validity of such a design has been established and its security is proven not worse than the security of the compression function. Fig 1: Iterative hash function structure 3.2 Compression Hash Function Algorithm The core of the compression function is a random binary matrix H of size r ×n. The parameters for the hash function are n the number of columns of H, r the number of rows of H and the size in bits of the function output, and w the number of columns of H added at each round. 4. System Model The system model concerned with attacks on the extension that originate on malicious phishing sites. Password hashing is computed using a Pseudo Random Function (PRF) as follows: hash(pwd,dom) = PRFpwd(dom) where the user’s password pwd is used as the PRF key and the remote site’s domain name dom or some variant is used as the input to the PRF. The hash value is then encoded as a string that satisfies the site’s password encoding rules, under control of a configuration file used by the browser extension. Password hashing is implemented naively inside a browser with rudimentary knowledge of HTML form components. Forms begin with a tag