Chapter 3 2
Chapter 3 2
Chapter 3 2
3.1.2 Advent of Ad-hoc Wireless NetworksAn Ad-hoc network is a local area network or some other small network, especially one with wireless, in which some network devices are the element of network only for the duration of a communications session. The theory behind ad-hoc networking is multi-hop relay in which data is sent from the source to the destination through the intermediate nodes. In multi-hop wireless network the communication between two end nodes is achieved through a number of intermediate nodes whose function is to relay information from one point to another point. Examples - Classroom, Large IT campus, Shopping mall, etc [22].
b) WSN c) WMN
d) VANETs
A) MANET
A Mobile Ad-hoc Network (MANET) is a collection of autonomous nodes or terminals which communicate with each other by forming a multi-hop radio network and maintaining connectivity in a decentralized manner over relatively bandwidth constrained wireless links. Each device in mobile ad-hoc network is free to move in any direction, and thus changes its links to other devices repeatedly. The topology is extremely dynamic and changes in the topology may be hard to predict. To connect to a network, a node must be within the area of influence of at least one node on the network. Even if the source and destination are not within each others range, data packets are forwarded to the destination by relaying transmission through other nodes that exist between the two nodes [11]. MANET Constraints and Issues 1. Lack of a Centralized Entity 2. Network Topology changes frequently and unpredictably 3. Routing and Mobility Management 4. Channel Access/Bandwidth Availability 5. Hidden/Exposed Station Problem 6. Near Far Effect
2. Collaborative and Distributed Computing A group in a conference can share data in ad hoc networks. Streaming of multimedia among the participating nodes.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 33
Maximizing the network life time is a common objective of sensor network research, since sensor nodes are assumed to be disposed when they are out of battery. In such circumstances, the proposed MAC protocol must be energy resourceful by reducing the potential energy wastes. The types of communication patterns that are observed in sensor network applications should be investigated since these patterns are used to extract the behavior of the sensor network traffic that has to be handled by a given MAC protocol [23]. A. Energy Waste When a receiver node receives more than one packet at the same time, these packets are called collided packets even when they match partially. All the packets which cause the collision must be discarded and the re-transmissions of these packets are required which increase the energy consumption. The second reason of energy waste is over-hearing, means a node receives packets that are destined to other nodes. The third energy waste occurs as a result of control packet overhead. Minimal number of control packets should be used to make a data
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 34
To design a good MAC protocol for the wireless sensor networks, the following attributes must be considered. The first attribute energy efficiency. We have to define energy efficient protocols in order to prolong the network lifetime. Other important attributes scalability and adaptability to changes. Changes in network size, node density and topology should be handled rapidly and effectively for a successful adaptation [10]. Some of the reasons behind these network property changes are limited node lifetime, addition of new nodes to the network and varying interference which may alter the connectivity and hence the network topology. A good MAC protocol should elegantly lodge such network changes. Other attributes such as through put, latency and bandwidth utilization may be secondary in sensor networks. Contrary to other wireless networks, fairness among sensor nodes is not usually a design goal, as all sensor nodes share a common duty [13].
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
35
3.2.3 Classifications of MAC Protocols [11] MAC protocols can be classified into three categories: a. Contention based MAC protocols. b. Contention based MAC protocols with reservation mechanisms. c. Contention based MAC protocols with scheduling mechanisms. Contention Based Mac Protocols Sender-initiated protocols - Transmissions are initiated by the sender node. Single channel sender-initiated protocols - A node that wins the contention to the channel can make use of the entire bandwidth. e.g MACA (multiple access collision avoidance) , MACAW [11]. Multichannel sender initiated protocols - The available bandwidth is divided into multiple channels [11]. Receiver initiated protocols - The receiver node initiates the contention resolution protocol [11]. Contention Based Mac Protocols with Reservation Mechanisms Synchronous protocols - All nodes need to be synchronized [14]. Asynchronous protocols - These protocols use relative time information for e reservations [14]. Contention Based Mac Protocols with Scheduling Mechanisms Node scheduling is done in a manner so that all nodes are treated fairly and no node is starved of bandwidth. Scheduling-based schemes are also used for enforcing priorities among flows whose packets are queued at nodes. Some scheduling schemes also consider battery characteristics [14].
Here signaling packets contain sender address, receiver address, packet size. The neighbor node that overhears an RTS packet has to defer its own transmission until the associated CTS packet is transmitted. Then any node overhearing a CTS packet would defer for the length of expected data transmission. When a node wishes to transmit a data packet, it first transmits a RTS (Request To Send) frame. The receiver node, on receiving the RTS packet, in case it is ready to receive the data packet, transmits a CTS (Clear to Send) packet. Once the sender receives the CTS packet, it starts transmitting the data packet [14]. If a packet transmitted is lost, the node use binary exponential back-off (BEB) algorithm to back off a random interval of time before retrying. The binary exponential back-off mechanism used in MACA might starve flows sometimes. Limitation -
B RTS CTS
CTS collision
Data collision
CTS
Fig. 3.1 Collision at Node B and Node C a) MACA does not provide ACK. b) RTS-CTS approach does not always solve the hidden node problem.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
37
3.4 Multiple Access Collision Avoidance Wireless (MACAW)MACAW (MACA for Wireless) is a revision of MACA (without ACK). The sender senses the carrier to see and transmits a RTS (Request To Send) frame if no nearby station transmits a RTS. The receiver replies with a CTS (Clear To Send) frame. In the meantime Neighbors if see CTS, then keep quiet. If the node sees RTS and not CTS, then keeps quiet until the CTS goes back to the sender. The receiver sends an ACK signal after receiving an frame. Neighbors keep silent until see ACK. Thus, no chance of collision. Significantly higher throughput than MACA.
Fig. 3.2 Working Diagram of MAC In the RTS/CTS algorithm, the node which wants to send frames sends a RTS (request to send) frame to the destination node first, and after the destination node responds with a CTS (clear to send) frame immediately. It is when the source node receives the CTS transmitted from destination node accurately; the source node is allowed to transmit frames. Whenever the source node receives the CTS, it starts the transmission of data. In order to face the unreliability of the
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 38
3.5 Channel Access Mechanism Step 1 If terminal j wants a packet to transmit, it first sends a RTS packet at Pmax, and includes in this packet the maximum allowable power level (P(j)map) that terminal j can use that will not disturb any ongoing reception in js neighborhood. If the destination ID in RTS format matches with the self id of receiver next step is to analyze power level. RTS FRAME Destination address/ID Transmitter address/ID Duration Data Size Allowable power
Additional field Step 2 The intended receiver i receives the RTS packet, and uses the predetermined Pmax, value and the power of the received signal P(ji) received to estimate the channel gain . =
Terminal i will be able to correctly decode the data packet if transmitted at a power P(ji)min P(ji)min =
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 39
= effective bit energy-to-noise spectral density ratio Eb/N0eff , that is needed to achieve the target error rate Pthermal= the thermal noise power, Noise rise (i) = (Eb/N0)unloaded / (Eb/N0)loaded) = (Pthermal + PMAI (i) )/ Pthermal (max) = maximum planned noise rise is set. i responds with a CTS (negative) to inform j that i cannot proceed with js transmission
2. If P (ji)allowed > P(ji)min i calculates the interference power tolerance PMAI -future(i) that it can endure from future unintended transmitters . PMAI -future(i) =3W Gji (P (ji)allowed - P(ji)min)/2 * W= Processing gain.i equitably distributes this power tolerance among future potentially interfering users . P (i) noise = The interference tolerance that each future neighbor can add to terminal i is
P (i) noise= P (i) MAI future/(1+ ) K(i) When responding to js RTS, terminal i indicates in its CTS the power level P (ji)allowed that j must use. i inserts P (i) noise in the CTS packet and sends this packet back to terminal j at Pmax over the control channel using the common code.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
40
CTS FRAME Frame control Receiver Address/ID Duration Interference Tolerance Pi(noise) Power Pji (allowed)
Additional fields Step 4 - Compute P(s)map Potentially interfering terminal S hears the CTS message from i, then computes the channel gain Gsi between s and i also computes the maximum power P(s)map that s can use in its future transmissions. = min( )
Step 5 - j sends data to i . Step 6 - If transmission is successful, receiver i responds j with an ACK packet over the data channel using the same power level that would have been used if i were to send a data packet to j. Protocol recovery- While receiving a data packet, terminal i hears a RTS message (destined to any terminal) that contains an allowable power level P(.)map value which if used can cause an unacceptable interference with is ongoing reception, means Mac id matching fails. Then terminal i shall respond immediately with a special CTS packet, preventing the RTS sender from commencing its transmission and data transmission cannot occur.
Data out
BLOCK INTERLEAVER
1.22 mbps
Decimator
19.2 kbps
Walsh code
19.2 kbps
DBPSK MODULATOR
DBPSK DEMODULATOR
Fig. 3.3 Physical Layer Structure MACAW based DS-SS CDMA Forward Link for Ad-hoc
Network
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
42
For example, 1/2 code rate means each bit entering the encoder results in 2 bits leaving the encoder. The encoder has n modulo 2 adders, and n generator polynomials one for each adder [21].
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 43
The Block diagram of convolution encoder is shown in Fig 3.4. To generate the output, the encoder uses three values of the input signal, one value which is present and two past values. The set of past values of input data is called a state. The no. of input values which is used to generate the code is called the constraint length. Each set of outputs is generated by EX-ORing a pattern of current and shifted values of input data. The pattern used to generate the coded output value can be expressed as binary strings called Generator Polynomials [21]. The MSB of the generator polynomial corresponds to the input; the LSBs of the generator polynomial correspond to the state.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
44
The present state values are the possible 2 bit combinations for both 0 and 1 input. The output is obtained from the expressions in the fig 3.4 . Then, the next state values are calculated by right shifting the input and present state values together by 1 bit position.
3.6.2 Interleaver
An Interleaver is a hardware device commonly used in conjugation with error correcting codes to counteract the effect of burst errors. Interleaving is a standard signal processing technique used in variety of communication system. An Interleaver is a device that takes symbols from a fixed alphabet as input and produces the identical symbol at the output in a different temporal order [20].
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
45
There are two classical kind of Interleaver a) Block b) Convolution Block Interleaver - In this, the input data is written along the rows of memory configured as matrix, and then read out along the columns. Convolution Interleaver - In this, data is multiplexed into and out of a fixed number of shift registers. Interleaving is a process in which the bits that compose a digital signal are reordered before transmission of the signal to compensate for the effects of burst errors resulting during signal propagation of the transrnission channel. The type of bit reordering is determined by the standard of the communication system. In a typical interleaver, the bits are written into a memory block in sequence [20]. Interleaving is basically taking a block of samples from your signal and shuffling (interleaving) them around before sending them. This is so that if a short 'burst' error occurs in a number of bits, the errors affect bits that were not actually next to one another when the signal was created. So when the data is de-interleaved then the error control code can work on the errors more easily, because the errors are spread through the message [20].
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
46
Data Frame
7 6 5
Received Data
4 3 2 1 0
Interleaver
Interleaved Data
7 1 4 2 5 6 3 0
Channel
De Interleaver
(X) be preferred pair of primitive polynomials of degree n whose corresponding shift registers generate maximal length sequences of period magnitude less than or equal to +1 +1 for n odd.. for n even. . (X) will generate and whose cross correlation function has a
Then shift register corresponding to product polynomial different sequences ,with each sequence having a period of
any pair of such sequences satisfying the preceding condition.An illustration of generating a Gold set is shown in figure below [20].
Fig. 3.6 Gold Code Sequence Generator with Shift Register of length m= 5 We consider a maximal length sequence requiring the use of linear feedback shift Register of length m=5. For feedback taps, we select the set [5,2] and [5,4,2,1] from the table. Assuming initial state is 10000, the evolution of maximal length sequences are shown in Table 3.2 and 3.3, where generator returns to initial 10000 after 31 iterations [22].
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
48
Table3.2 Evolution of the maximal length sequence generated by the Feedback Shift Register (a) Feedback taps [5,2 ] Feedback Symbol 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 State of Shift Register 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 Output Symbol 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0
Code: 0001010111011000111110011010010 VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 49
Table 3.3 Evolution of the Maximal Length Sequence generated by the feedback Shift Register [22] (b) Feedback taps [ 5,4,2,1 ] Feedback Symbol 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 State of Shift Register 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 Output Symbol 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0
Code: 0001101010010001011111011001110 VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 50
3.6.4 Decimator
The decimation is accomplished by essentially using every sixty-fourth bit out of the long code frame. Here 64 times decimation reduces the data rate from 1.2288 Mbps to 19.2 Kbps.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
51
The
simplicity
of
their them
generation a good
and
fixed for
power the
feature
along
with
choice
communications systems. The Hadamard Walsh codes are generated in a set of N= With length N= .The generating algorithm is as follows=[
] where N is a
power of 2 and dash denotes the binary complement of bits in the matrix. The smallest set of N=0 is with length 1.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 52
property of walsh codes, because of this the cross correlation between any two hadamard walsh code of same set (matrix) is 0 when the system is perfectly synchronized [20]. For example, lets examine the codeword denoted W(1, 2) and the codeword denoted W(2, 4) to see if they are orthogonal. Since they are of different lengths, we repeat W(1, 2) to match the length of W(2, 4). Hence, we get the following two code words in polar formW(1, 2) [ 1 -1 1 -1 ] W(2, 4) [ 1 1 -1 -1 ] Computing the orthogonality we get (11+ -11 + 1-1+ -1-1 = 0 ) Hence, W(1, 2) and W(2, 4) are orthogonal.
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
53
Input data stream 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 000 000 000 000 000 000 000 000 101 101 101 101 101 101 101 101 000 000 000 000 101 101 101 101 110 110 110 110 011 011 011 011 000 000 101 101 110 110 011 011 011 011 110 110 101 101 000 000 000 101 110 011 011 110 101 000 000 101 110 011 011 110 101 000 000 110 011 101 000 110 011 101 000 110 011 101 000 110 011 101 000 011 000 011 000 011 000 011 000 011 000 011 000 011 000 011 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 Coded output bit stream
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
54
Fig.3.9 Code Tree for the encoder of Fig. 3.4 utilizing Table 3.5 [23]
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks | 55
VHDL Implementation of DS-SS CDMA based Mac protocol for Ad-hoc Networks |
56