تجزیه و تحلیل عملکرد از پخش برنامه در شبکه های ad hoc با پذیرش همزمان و غیر همزمان

Analyzing the performance of broadcast in mobile ad hoc networks is necessary because of the importance of broadcast in multiuser communications and the characteristic difference between wireless communications and wired communications. If the time lag between collided packets is small on the order of a symbol, the reception is synchronized; otherwise, the reception is non-synchronized. We find that there is a time complexity gap exponential with the degree of the network between the performance of synchronized and non-synchronized reception. Besides, we also take into account the possibility that a processor is busy with other tasks, and we find that allowing the processors to be temporarily busy with other tasks will not degrade the performance significantly.

Broadcast, i.e. sending a message initiated from a user to other users in the network, is an important task in distributed systems and mobile networks. It can be used for disseminating information among a set of receivers [1] and exchanging messages in distributed computing [2]. Applications of broadcast include sending control messages to all users and video conferencing [1]. In single-hop wireless networks with a base station, such as cellular networks, broadcast can be done by sending the message via the base station to every mobile user in the downlink channel [3]. However, in a mobile ad hoc network [4], there is not a base station that can communicate with all users directly, and not all users can receive the messages from all other users directly [2]. Therefore, ad hoc mobile networks belong to multihop networks, in which it is not so simple to solve the broadcast problem. Modern applications of multihop mobile networks are given in [5], [6], [7] and [8], such as disaster recovery, e.g. search and rescue in fire or earthquake. Another example [5], [6], [7] and [8] is ad hoc personal communications networks, which could be rapidly implemented, for example, on a campus, to support collaborative computing and provide access to the Internet during special events like concerts and festivals. Numerous researches have been conducted to investigate the broadcast problem in multihop wireless network. Chlamtac and Weistein proposed a centralized broadcast algorithm with time complexity where R is the radius of the network, i.e. the maximum number of edges in the shortest path between two nodes, and V is the number of mobile users in the network [9]. Broadcast protocol based on multi-cluster architecture [10] was proposed in Ref. [11]. In Ref. [12], it was proved that any broadcast algorithm requires time slots to finish for a network with radius equal to two. In Ref. [13], it was proved that any distributed broadcast algorithm requires time slots to finish. Bar-Yehuda et al. in Ref. [14] proposed a distributed randomized algorithm, which needs only time slots to finish with probability 1−ϵ. This algorithm is exponentially superior to any distributed deterministic algorithm, which takes Θ(V ) time slots even for a radius-3 network. Based on this randomized algorithm, a routing and multiple broadcast algorithm was proposed in Ref. [15]. In Ref. [16], a lower bound for randomized broadcast algorithm was provided by Kushilevitz and Mansour. In previous researches such as [9], [10], [11], [12], [13], [14], [15] and [16], it was often assumed that the reception of a packet is always successful when there is only one packet received, and it always fails when more than one packet are received at the same time. In a real wireless channel, even if there is only one packet transmitted, it is possible that this packet is not acquired successfully. When there are more than one packet received, it is possible that a packet is acquired successfully [15]. Therefore, in the previous work [17], we analyzed the performance of a distributed randomized broadcast algorithm with consideration of channel reliability. The analysis shows that the performance of randomized broadcast algorithm is satisfactory with channel reliability. Furthermore, adjusting the retransmission probability is a good way to obtain better performance [17]. However, power level is only one of the several important issues in wireless networks. For example, another critical issue is the timing of the signals. Therefore, in this paper, we analyze the performance of broadcast with more considerations than those in Ref. [17]. The impact of the time lag at symbol (bit) level between collided packets is analyzed. If the time lag between packets is small, we say the reception is synchronized. If the time lag is large, we say the reception is non-synchronized. To correctly obtain the information from the signal, the receiver has to know when the signal starts and ends. Therefore, investigating these timing issues will be very important to the performance of wireless networks. Related research topics appear in the analysis of single-hop networks. The phenomenon that a collision does not necessarily destroy packets is called capture [2], [18] and [19]. Capture could enhance the performance of random access protocol radio such as ALOHA, and capture influences the performance of CDMA (code division multiple access) [19]. The goal of the MAC (medium access control) in those topics is to achieve multiple access. Therefore, the packets involved in a collision have different contents. The broadcast problem here contains only single message; therefore, it is successful as long as at least one packet is received successfully. Thus, the MAC is utilized to carry this packet to all users. Besides, there can be more than one hop in the network, so the packet has to be transmitted hop by hop to reach every user. Therefore, the packets involved in a collision have the same contents, if the packets are broadcast in ordered sequence. Furthermore, the probability that a processor is so busy with other tasks that temporarily does not execute the broadcast algorithm is included. This may result from some emergency event that a processor has to deal with, or power-saving considerations, etc. In another point of view, allowing a processor to be busy with other things also gives the processor more freedom since it can deal with other important jobs. Thus, it would be desired to analyze the performance of allowing a processor to be busy with other things and temporarily not carrying out the algorithm. In this paper we analyze the performance of broadcast with synchronized and non-synchronized reception in mobile ad hoc networks. We examine the performance gap between them. How to adjust the parameters in the broadcast algorithm to achieve better performance is also investigated. The rest of the paper is organized as follows. Section 2 analyzes the probability of successful reception of a packet. Performance of broadcast algorithms is analyzed in Section 3. Section 4 gives numerical examples and discussions. Conclusions are provided in Section 5.

In this paper, we analyze the probability of successful reception of the packet when more than one packet is received at the same time. The probability of successful reception is not only dependent on the reception power of packets [17], but also depends on the time lag and the contents of the collided packets. There is a great gap between the performance of synchronized and non-synchronized reception. In broadcast, the performance of synchronized reception of several packets is in fact better than that of reception of only one packet. This is because, the multiple packets received contain the same content, the symbols are synchronized, and the envelope magnitude of the sum of the signals is larger than that of only one signal. Besides, incoherent demodulation is used, so the envelope magnitude decides whether a packet can be received correctly. On the contrary, non-synchronized reception of the packets caused adverse effects. Since the symbols are not synchronized, the content of one packet acts as noise to other packets. Therefore, the receiving processor has a smaller chance to receive any one of the packets successfully. The substantial difference in performance of synchronized and non-synchronized reception also influences how the broadcast algorithm is used. For synchronized case, the processors in fact do not need to use “decay” to solve collision of packets, since collision of packets in fact enhances the probability of successful reception. For non-synchronized case, the processors need to use “decay” to solve collision of packets, since non-synchronized reception of packets might destroy the packet. Therefore, the number of time slots needed in a stage is practically one for synchronized reception, and grows logarithmically with the maximum number of neighbors (i.e. logD) for non-synchronized reception. We also investigate how to improve the performance. When collisions are not frequent and there are only few neighbors, raising q can keep the neighbors transmitting for longer time. When collisions are frequent, the time and power needed can be reduced by using smaller q to reduce the number of collisions. Raising the transmitter power and thus signal-to-noise ratio can only improve the performance within a limit, after which increasing power level does not result in great improvement. Rather, choosing a proper value of retransmission probability q is a more effective way to improve the performance. How to optimize the network topology to reduce the time needed for broadcast also differs in the cases of synchronized and non-synchronized reception. Minimizing the time complexity requires minimizing both the radius of the network R and the degree of the network D. However there is a tradeoff between D and R. For example, if the transmitters increase their power levels, R could decrease and D could increase. To reduce the time needed for broadcast, trying to have smaller R is a better method for synchronized reception, but trying to have smaller D is a better method for non-synchronized reception. Practical processors might not carry out broadcast temporarily. In fact, for the case that collision is detrimental and collisions are frequent, allowing the processors not to carry out broadcast temporarily might also be a method to solve collision of packets. We found that the performance degrades with pr (probability that a processor does not carry out broadcast) for synchronized reception, and the performance sometimes improves with pr for non-synchronized reception. In mobile ad hoc networks, broadcast provides an effective way to implement communications among users under the condition that there is no base station. This is especially true for wireless local area networks, where synchronized reception can be more easily achieved. Furthermore, the mobility of users increases the cost of maintaining a routing table needed by deterministic algorithms. Therefore, randomized algorithms are more appealing. There are several directions for future work. First, the performance of multiple messages broadcast, routing, and multicast can be investigated [15] and [27]. Second, other possible methods of broadcast in mobile ad hoc networks can also be studied. For example, how to carry out broadcast in a completely asynchronous (i.e. unslotted) manner can be studied. Third, we can carry out more accurate analysis of the probability of successful reception with practical considerations. One consideration is the correlation between consecutive events, such as severe fading, non-synchronized reception, and a processor's pause in carrying out broadcast algorithm. Another consideration is the relation between successful reception at packet level and signaling level. The accuracy of the synchronization of the clocks can also be considered. Fourth, we will investigate possible performance improvements by the use of receiver diversity and RAKE receiver to distinguish and combine packets from different users [28].