Abstract: In this study, we presented a method for distributing data storage by using residue number system for mobile systems and wireless networks based on peer to peer paradigm. Generally, redundant residue number system is capable in error detection and correction. In proposed method, we made a new system by mixing Redundant Residue Number System (RRNS), Multi Level Residue Number System (ML RNS) and Multiple Valued Logic (MVL RNS) which was perfect for parallel, carry free, high speed arithmetic and the system supports secure data communication. In addition it had ability of error detection and correction. In comparison to other number systems, it had many improvements in data security, error detection and correction, speed of storage and retrieval.
INTRODUCTION
Mobile ad-hoc network (MANET) is an efficient technology for providing a wide-area communication environment where installing the infrastructure of a wired network is difficult. It is also suitable for supporting communication among mobile nodes. For the last several decades, many routing protocols have been proposed to make the best use of wireless network technology (Abolhasan et al., 2004; Xiaoyan et al., 2002; Royer and Toh, 1999; Barati et al., 2007a).
As making base station or wired networks for mobile terminal is impossible or unfeasible use of these networks owing to simple configuration and low cost is very suitable. Some applications are communication in hostile environment without any central base station, navies in navy component, mobile computer meetings of people in areas where wired networks are not available, disaster recovery, management of emergencies (for instance in case of earth quake where all infrastructures are destroyed).
The major issue in ad-hoc networks is how to implement dependable and secure data storage. This is an essential requirement in applications where the mobiles cooperate by sharing information and need to create and access shared files. In this situation the system should prevent data losses or corruption due to network disconnections, mobile failures or malicious attacks from untrustworthy mobiles (Satyanarayanan et al., 1990).
On the other hand ad-hoc networks are a heterogeneous mix of different wireless and mobile devices, ranging from little hand-held devices to laptops. Such devices are dependable on batteries for energy consumption, in case of battery depletion which is similar to a crash fault; the mobile may not recover data upon the availability of battery replacement/recharge. As mobiles may not be equipped with permanent storage, failures may result in data losses or corruption. For all of these reasons, many techniques are presented for solving dependable and secure data storage problem up to now, one of these techniques is using residue number system.
The Residue Number System (RNS) is an unconventional and non weighted number system, which is capable of supporting parallel, carry free, high speed arithmetic. In this system, arithmetic operations act on residues-reminder of dividing original number in several definite moduli-in parallel. Consequently computations on these residues which are smaller than the original number are performed, so speed up arithmetic and decreased power consumption is achieved (Szabo and Tanaka, 1967).
A residue number system is characterized by a moduli set {m1,m2,…,mn} where the moduli, mi(i = 1,2,…,n) are pair-wise relatively prime (Parhami, 2001). Any integer X in the dynamic range, M = m1,m2,…,mn, is represented by an N-tuple (x1,x2,x3,…,xn), where xi is the residue of X in moduli mi for i = 1,2,…,n.
The reconstruction of X from its residue (x1,x2,x3,…,xn) is based on the Chinese Reminder Theory (CRT) shown by:
(1) |
The notation
Another advantage of this is security because for RNS conversion to weighted number system knowledge of moduli is required. Consequently this system is a symmetric key encryption system with medium security.
Some applications of RNS are digital signal processing, digital filters (Conway and Nelson, 2004), coding theory (How et al., 2006), RSA encoding algorithm (Bajard and Imbert, 2004), digital communication, ad-hoc networks, distributed dependable and secure data storage and retrieval (Barati and Movaghar, 2007b), error detection and correction (Barsi and Maestrini, 1973; Krishna et al., 1992; Sun and Krishna, 1992) and fault tolerant system.
In addition, in this system owing to separate computation on residues if error occurs one of this residues, the effect of it is not distributed on other residues. In other words RNS architectures inherently are fault tolerant (Kinoshita and Lee, 1997).
MULTI LEVEL RESIDUE NUMBER SYSTEM (ML RNS)
Arithmetic computations on each moduli could be done with a new residue number system and repeated until having very small moduli owing to residue number systems properties in increasing calculations speed, decreasing power consumption, increasing security and fault tolerance. In other words this process could be repeated for several levels.
The system derived from the process is called Multi Level Residue Number System (MLRNS). However in this system the dynamic range of any sub-residue number system like residues in ith level must be grater than the largest moduli in the previous level like residues in (i-1)th level. In this paper two level residue number system is assumed in order to simplify the presentation. It should be considered that provided method could be expanded for more levels as well (Yassine, 1992).
In residue number system with two levels, two symmetrical key encryption algorithms are used in together, so the system has a high security. Another advantage of two levels residue number system is the simple selection moduli set for large presentation limits. This means by selecting a few large modulis and using a new residue system with smaller moduli for second level accordingly this capability is achieved. By having a few numbers of great moduli in first level as a result; First the problem of being pair-wise relatively prime of moduli also unbalancing of them would be solved and second, owing to use of less moduli the converting circuits are simple the conversions would be done rapidly. Meanwhile since modulis in second level are small, internal computations of residue number system-because of short carry propagation are performed rapidly (Skavantzos and Abdallah, 1999).
Notations that used for two residue number system in this paper are as following:
| : | First level residue number system moduli set | |
| : | Second level residue number system moduli set for moduli mi(i = 1,2,3,…,n) | |
| : | Residues in first level residue number system | |
| : | Residues in second level for ri(i = 1,2,3,…,n) |
Arithmetic computations in two level residue number system are performed on the second level residues. Two operand arithmetic operations are defined as following:
(2) |
where, zij = (xijοyij) mod mij, i = 1,2,3,…n, j = 1,2,3,…n and o could be addition, subtraction and multiplication (Hosseinzadeh and Navi, 2007).
For conversion from weighted number system to two level residue number system first of all the supposed number should be converted to first level residue number system and the supposed residues should be converted to second level residue number system. This process is shown in Fig. 1.
In reverse conversion, nxni-channel CRT for i = 1,2,3,…,n it is necessary to convert second level residues to equal residues in first level and then convert to weight number system by using a ni-channel CRT. This process is shown in Fig. 2.
| Fig. 1: | Conversion from weighted number system to two level residue number system |
MULTIPLE VALUED LOGIC (MVL RNS)
Multi-valued logics are logical calculi in which there are more than two truth values. Traditionally, logical calculi are two-valued, that is, there are only two possible truth values (i.e., truth and falsehood) for any proposition to take. An obvious extension to classical two-valued logic is an n>2-ary logic. Those most popular in the literature are three-valued and infinite-valued ones.
It is obvious that the positional weights of any two succeeding columns are multiples of r. Figure 3 represents the positional value of each location.
Each location in an MVL component can store much more information than a binary logic component, the dynamic range of the moduli set {rn-2,rn-1,rn} is much greater than its equivalent in the binary representation. Now the question is how to present the related hardware which is clearly answered in (Skavantzos and Abdallah, 1999) (r = 10 in this research).
REDUNDANT RESIDUE NUMBER SYSTEM
Additional moduli is used in residue number system for error detection and correction capability. This system is called Redundant Residue Number System (RRNS). Redundant residue number system is presented by:
(3) |
In case all moduli were pair-wise relatively prime the presentation limit of this system is equal to:
(4) |
The interval [0,M] that
| Fig. 2: | Conversion from two level residue number system to weight number system |
| Fig. 3: | Positional weight value of each location |
In redundant residue number system with h+r moduli, a number like X that α≤X<α+M is represented by (x1,x2,…,xh,xh+1,…,xh+r).
The minimum distance dmin is a fundamental parameter associated with any error control code. The minimum distance of an RRNS code is dmin, if and only if the product of redundant moduli satisfies the following relation:
(5) |
As a result the minimum hamming distance of a redundant number system is 3, if and only if:
(6) |
For example if a supposed redundant residue number system with moduli set of (m1,m2,m3,m4,m5,m6) = (3,7,11,13,16,17) for d = 3 should 272≤MR<3536.
So minimum distance of 3 will be derived from each of these sets:
(7) |
In addition if we choose moduli {m1,m2,m3,m4,m5: MR = 3696} minimum distance of 4 will be derived.
As we see choosing redundant moduli set for minimum Hemming distance is non-unique. For choosing the optimal redundant moduli set in order to maximize the amount of M according to equation MxMR = C in which C is a constant number, MR should be minimized. The least MR for minimum Hemming distance is equal to:
(8) |
In optimal redundant number system d–1 big moduli of it should be chosen for minimum Hemming distance. In other words:
(9) |
Consequently in optimal redundant number system the minimum Hemming distance is equal to r+1 (Barsi and Maestrini, 1973). From here optimal redundant number system is meant by redundant number system.
In redundant residue number system if h residues were achieved among h+r residues then we could recovered the number X. This property makes error detection and correction possible in redundant residue number system which is the basis of error detection and correction as well.
(10) |
Derivation of X from h option moduli is possible according to these equations by using Chinese Reminder Theory.
Coding properties of redundant residue number system is similar to RS famous codes. As a result by considering the minimum Hemming distance of this code is r+1:
This code has the capability of detection r corrupted residues.
| • | This code has the capability of correcting |
| • | This code has the capability of simultaneous correcting up to λ corrupted residues and detection up to β corrupted residues (β>λ), if and only if λ+β≤r. |
| • | This code has the capability of simultaneous detection of t errors and detection of s residues which are corrupted in the path and hasn`t arrived, if and only if t+s≤r. |
This code has the capability of simultaneous correction of t errors and correction of s residues which are corrupted in the path and hasn`t arrived, if and only if 2t+s≤r.
MVL ML REDUNDANT RESIDUE NUMBER SYSTEM AND ITS APPLICATION IN AD-HOC NETWORKS
MVL ML redundant residue number system: In this article multi level redundant residue number system is presented for increasing error detection and correction and increasing security in high speed computing without carry propagation. In multi level redundant residue number system, redundant moduli could be used for error detection and correction. Many errors could be detected or corrected in low levels in this method.
Multi level redundant residue number system has the capability to provide much fault tolerance for more important moduli in first level, in this method moduli which are supposed for lower levels of redundant residue number system have more redundancy or have more Hemming distance in other words. There is an important issue in this system. The error detection and correction of RRNS coding are performed on moduli not on bits (Note a moduli might be single bit or more). Therefore if a single-bit-error has occurred, the whole moduli will be involved. So, the rate of error detection and correction will be increase for single-bit-error by using small moduli.
Application of MVL ML redundant residue number system in ad-hoc network units: The data storage and retrieval in Ad-Hoc network provides by cooperating the mobiles in creating and sharing files and the system provides procedures for the users to create, share, read and delete the files. For each mobile in ad-hoc network is defined Ui(i = 1,2,…) that is unique in the network. In the rest of the section we describe the file creation, sharing, reading and removal procedures.
| • | File creating: Two-level redundant residue
number system is used for creating encoded a file. For this purpose
a two-Level moduli set realized with described specifications. This
moduli set could be selected in offline situation as well the number
system presentation limit should just be selected greater than the
proposed file.
In case of files with huge volume, partitioning into small sub-file could be used. Each file coded The file owner have a description file that containing moduli set used for encoding any file along with description about mobiles storing residue. This file is hidden and kept by the owner. |
| • | File reading: For reconstruct the file each residue and
its corresponding moduli which is coded with it is required because
of this coding property.
If Ut has a copy of description file, it could order different part of file from other mobiles according to the description file. So Ut could reconstruct the file upon receiving sufficient But during reading execution some of inquiries might be lost or corrupted in the network before reaching Ut. In such situation detection and or correction might be able depending on the amount of received additional residue. |
| • | File sharing: The file owner could share the file for trustworthy
mobiles upon request by sharing the description file. The file owner
could even define access level to this file for other mobiles. For
example access only for reading, writing, reading and writing. |
| • | File removal: File deletion could only be done by owner while the owner could grant this right to others. File deletion is performed upon sending a message for mobiles having residue. |
COMPARISON
A comparison between redundant residue number system (Bajard and Imbert, 2004) and MVL ML redundant residue number system for secure and reliable data storage and retrieve is shown in Table 1.
Error detection and correction is increased in multi-level redundant residue number system owing to moduli Detection and correction capability (because each moduli itself is constructed by a residue number system). Security achieved by using multi-level redundant residue number system is much higher than redundant residue number system by using multiple of symmetric encryption code together.
In multi-level redundant residue number system, residues are less significant amounts because of using small moduli and could be transmitted rapidly and computations on these residues is also very fast.
| Table 1: | MVL ML redundant residue number system comparison with redundant residue number system |
Achieved presentation range is very large by using multi-level redundant residue number system and that is no problem in moduli selection and these would be no limits for file size consequently.
CONCLUSION
In this research, multi-level residue number system, multiple Valued Logic and redundant residue number system are surveyed and then MVL ML redundant residue number system and application of this number system in ad-hoc networks was presented accordingly.
MVL ML redundant residue number system has more security, error detection and correction capability and more speed in comparison to activities done before in this case.
Since the amount of minimum Hamming Distance in multi-level redundant
residue number system, is equal to
If in each second level moduli which is assumed for first level of ith
moduli (i = 1,2,…,n), up to maximum ri error occur, then
the system can detect
If in each second level moduli which is assumed for first level of ith
moduli (i = 1,2,…,n), up to maximum
If in each second level moduli which is assumed for first level of ith
moduli (i = 1,2,…,n), up to maximum
If in each second level moduli which is assumed for first level of ith moduli (i = 1,2,…,n), up to maximum ti error occur and also si residue never reached, then this code capable of detecting t errors and simultaneously correcting s errors, if and only if
If in each second level moduli which is assumed for first level of ith moduli (i = 1,2,…,n), up to maximum ti error occur and also si residue never reached, then this code capable of detecting t errors and simultaneously correcting s errors, if and only if
ACKNOWLEDGMENT
We are grateful to Islamic Azad University of Dezful for financial support.