IJCNC 02

BROADCAST SCHEDULING PROTOCOLS IN MULTIHOP MOBILE AD HOC NETWORKS

Chandra Kanta Samal

Department of Comp.Sc., ANDC, Delhi University, New Delhi, India

ABSTRACT

When packets are sending in multi-hop mobile unintended networks numerous problems occur like flooding, rebroadcast, broadcast latency, power conservation and collision. If multiple transmission of packets simultaneously in MANETs that using the slot assignments approach, when additional channels are transmitting at the same time as the first slot allocations, interference may occur at the nodes. Because of the multi-hops data transfer, the network performance is hampered by the constrained bandwidth and therefore the self-initiated topological alterations. Therefore, a broadcast algorithm is important within the mobile ad hoc network for collision control and reliable communication. This paper proposes two new broadcasting protocols: modify SRBS and DSB algorithms. The planned algorithms outperform context of efficiency, reliability, traffic overload and reachability in highly mobile networks is an enhanced performance within the different environments. Evaluation of simulation results with other well-known exiting protocols as DFCN and PEGSP algorithms shows that the proposed protocol performance is best within the wireless network and channel bandwidths are well utilized within the network.

KEYWORDS

Broadcast latency problems; Efficiency; Reachability; Reliability; Average latency etc

1.INTRODUCTION

A mobile ad hoc network is a group of wireless mobile phones forming a provisional set-up does not include support of any centralized administration. If the source node cannot directly send a message to destination node because of wireless nodes have limited transmission range. So, the source node forwards a message through intermediary nodes towards the destination node. Thus, a multi-step situation happens, and a packet may need to be relayed by several nodes before it reaches its destination [1, 2]. The major problems in MANETs are battery powered, interference, security, bandwidth, and reliability. Due to the mobility of nodes, the network’s properties are unpredictable; its topology changes and the signal strength varies with the environment and time [3, 4].Consequently, communication pathways are divided up and new routes are generated dynamically [5].

For reliable communication in an ad hoc mobile network, the broadcast algorithm is crucial. [6, 7]. Many contentions, redundancy, rebroadcasts, and collisions are different categories for the issue. The flooding process produces a lot of redundant messages because, first, it is possible that neighboring nodes have already received each node’s retransmission of a message. Second, there will be several nodes competing for access to the wireless channel since all nodes want to rebroadcast the message at the same time or very close to it. Third, since the hidden terminal problem will always exist, many collisions will happen even without the use of the RTS/CTS exchange [8, 9].

2.EXITING RELATED WORKS

This section compares two broadcast protocol’s performance in terms of efficiency and reliability in multi-hop ad hoc networks in both highand low-density networks. The two broadcast protocols are Delayed Flooding with Cumulative Neighborhood Protocol and Proposed Enhanced Generic Self-Pruning Protocol. The Delayed Flooding with Cumulative Neighborhood (DFCN) Protocol enables broadcasting on wide-area networks with excellent bandwidth management. It is made up of many different wireless mobile devices, then create a network and we see the network’s bandwidth of the channel is accurately used [10].Suppose we are increasing density of these nodes within the network area, when packet transmission it does not exhaust way increased bandwidth, it may decrease redundancy and rebroadcast there. The main aim of the DFCN protocol is minimizing the number of emissions that’s result impact on improving the network throughput and also route, selecting the path of nodes at maximizing coverage in the network [10]. Basic method of DFCN algorithm is broadcasting messages in distributed mobile unintended networks, message sent from source node to forward to any or all nodes within the network. Here, the method of selecting the routing nodes is used. These nodes forward messages to intermediate nodes, utilizing the least amount of the network as a result. This protocol will be an enhanced version of that which is mentioned in [11].This protocol benefits the conservation of energy in multi-hop unplanned mobile network. The difficulty of this protocol is that the desired bandwidth cannot be transferred because of the high mobility of the nodes. The reliability of the sparse network decreases when network size is increased. There is no system-wide traffic monitoring if the size of the degree is increasing. The network does not communicate the maximum quantity of data because low emission results from the algorithm’s node selection technique.

Excessive network traffic may cause a significant delay in packet transmission if multiple hosts must simultaneously compete for a finite amount of communication bandwidth. The genetic algorithm is more powerful than other algorithms such as the results of the algorithm fulfill high efficiency but low reliability [12].This algorithm’s advantage is that it performs effectively with low mobility. While certain algorithms are highly reliable, they are also inefficient, and vice versa. The proposed enhanced generic self-pruning (PEGSP) algorithm’s main objective is to achieve high reliability in extreme mobile networks. This can be achieved by either increasing the delivery ratio of a reliable algorithm or decreasing the number of forward nodes in an efficient approach.

The “Hello Messages” technique was used by the proposed PEGSP algorithm to detect the high mobility of nodes during route connection establishment, which eliminated the issue of inadequate consideration of their capabilities. Additionally, the proposed PEGSP algorithm used a different set of messages called location information messages and timers that were informed to detect a link failure. The drawback of the algorithm is that when mobile node speeds increase, network efficiency declines. The degree of node dependence is extremely high, and node accessibility within the networks’ transmission range is not always guaranteed. A Dynamic scalable broadcast algorithm is a dynamic broadcast protocol and it is reliably in a MANET. The exiting dynamic broadcast technique is not reliable in mobile ad hoc networks because of the node’s mobility and self-motivated topology changes its position in distributed mobile ad hoc network. The existing protocol designs do not have better performance in the network. Author’s purpose DSB algorithm is very good for slot assignments among nodes due to reduced interference between nodes at the time of slot reservation. Our emphasis is on collision avoidance, but on reducing the problems of redundancy, rebroadcasting and broadcast latency

3.TECHNICAL APPROACH

In a multi-hop Mobile Ad hoc Network, we have created broadcasting protocols for dependable and spam-free communication. In this research, we suggest two novel broadcast protocols that modify the Stable Reliable Broadcast Scheduling (SRBS) and Dynamic Scalable Broadcast (DSB) algorithms. The SRBS is a static broadcast protocol; it is a higher performance in high mobility and increasing network size [13].

In dynamic broadcast protocol nodes join and leave to each other’s within the network. The Dynamic Scalable Broadcast Algorithm has no central computing managed; each node keeps the state data record in its place. Every node makes this recording by gathering information from its neighbors 1-hop and 2-hop stop. When the node communicates over the network, it detects the node of its neighbors within the network. If a network node’s neighbour is occupied, then the sleep cycle repeats this process until the neighbor node in the network is busy otherwise node would join the neighbor’s node in the network for process of registration. As we are using set covering scheme, the node should know its 1-hop neighbors and the 2-hop coverage within the network. In the set covering scheme, minimum 1-hop nodes require covering the 2-hop nodes in the network and hence reduce rebroadcast and redundancy [14].

Figure 1. An example of three-layer graph [14]

In figure 1, when packets communicate in the multi-hop network collision of nodes may occur at layer 3. The nodes “a”, “b”,”c”,”d” and “e” in layer 1 and “l”, “f”, “g”, “h”, ” i”, “j” and “k” at layer 2 is the source node’s one-hop and two-hop neighbours, respectively, whenever the node “s” in layer 0 is the only source node. The nodes “a”, “c” and “e” in layer 1 could be the very minimum required to cover all nodes in layer 2.For layer 2 has no common neighbours for nodes “a”, “c” and “e”, they will broadcast packetsat the same time without collision occur in layer 2.

So, we have got used the independent transmission plan to reduce collisions and broadcast latency [14]. If the degree size of a node is increased within the network it will be unreliable for communication. That’s why the All to All protocols are used for slot allocation between mobile nodes to regulate the overload of node and avoid queuing of node [14]. This approach may be well worked in MANET, it helps for reliable communication in the multi-hop networks. We make slot timers for a node to sense the neighbor node’s network. If the node is not detecting neighbor’s node network within the slot time period, we have got to line the slot timer again. Subsequently, if the source node does not detect the neighbor node’s network, it declares that neighbor node’s network is out of transmission range. Every device chooses to send an identifying packet. A new device must broadcast an ID Packet; If not, it remains in receive mode onlyA recognizes a new neighbour when it receives an ID packet. At the time of the identification interval, we use three slots as follows:

• Request slot
• Collision slot
• Broadcast slot

The new node is introduced through the registration process, it identified to all or part of its neighbors at 1 or 2-hops distance in the network. If more nodes ready to join the network are located one or two hops away from the source node, only those nodes who successfully completed the registration process should be permitted. The X Node reserves the broadcast slot, if no one else has to join the network. If Node Y also wants to affix the registration process, it should wait for an X node to complete the registration process successfully.

If X is a joining node, it detects an empty broadcast slot and sends the request control packet in the request slot for the registration request. If X did not sense any collision in the network when broadcasting its control packets. If X notices an empty collision slot, it knows that neither of its neighbours within 1 or 2 hops is submitting a request to start the registration process. If the registration process is successful, then are made frame schedule for 1-hop neighbors is created otherwise sleep cycle is repeated and slot timers are made again until the registration process is successful. In the final step we execute the frame schedule as collision free in the multi hop network [15].

Neighbor Broadcast Coverage: TheAuthor follows the neighbor broadcast coverage method purpose by reference [16, 17]: Let set Bm and Bn are the neighbor node, node n forwards the messages to node m and Dm stand for neighbor set coverage up to two hops. The m node receives a message from n node first time, so the neighbor set coverage broadcast follows:

Reliable BroadcastPacket: The scalable broadcast algorithm has mentioned by reference [18]. We use to knowledge the two hops neighbor set coverage by equation (1).If n node is not received message from m node, it is clear that m set is no neighbor coverage, on that situation m set is not rebroadcast the packets then node n will delay the rebroadcast schedule. We consider themaximum number of neighbor coverage nodes is a highest priority for broadcast packetas comparison with those nodes is a covered minimum neighbor. Broadcast delay is calculated noden’s degree (Cn) and its neighbor’s maximum degree (Cmax):

3.1. Flow Chart of DSBAlgorithm

The Dynamic Scalable Broadcast (DSB) algorithm flow chart is provided in this work

Figure 2. DSB Algorithm’s Flow chart

3.2. Stable Reliable Broadcast Scheduling Algorithm’s Flow Chart.

The SRBS Algorithm flow chart is mentioned[13].

Flow chart of Reliable time slot allocation among mobile nodes[19].

Figure 3. Flow chart of SRBS Algorithm

4.SIMULATION AND RESULTANALYSIS

We have compared the various metric’s simulation results of theSRBS, DFCN, DSB and PEGSP methods; it is implemented in GloMoSim simulatorv2.03 [20,21,22]. We have got taken the subsequent parameters within the configuration setup.

Table 1. Simulation Configuration setup parameters

The throughput of the network with 150 nodes is displayed in figure 4 as a result.If we consistently increase node speed, it starts at 20 m/s and goes up to 120 m/s then the four algorithms throughput decreases because of the high speed of nodes. Therefore, DFCN algorithm has low throughput and SRBS algorithm performs better than the other three algorithms. Expression of the throughput:

(Where P(mg)→ Sent the total Numberof transmission messages, Q(mg)→Number of neighbor nodes received message, R(nbn)→ Total number of neighbor nodes)

Figure 4. Throughput Vs Mobility of Node (Size of node is 150)

Above figure 5result that when the size of nodes is 500, area is 3000 sq.m2 and speed of nodes is 30 m/s that time PEGSP algorithm results slightly less than the DFCN and DSB algorithms result. If we are increasing regularly the network size and number of nodes, then the four algorithms throughput will decrease. The SRBS algorithm is determined to be superior to the opposing three algorithms.

Figure 5. Throughput Vs Network Size (sq.m2)

Figure 6. Reachability Vs Number of Nodes (Mobile node’s speed is 30 m/s)

The DSB algorithm is more reachable than the SRBS, DFCN and PEGSP algorithms, according to the resulting extract from figure 6. Reachability of the DFCN algorithm is marginally better than PEGSP algorithm at 500 nodes.

Reachability is determined by how many nodes have actually received broadcast packets.

(Where Q(rp) → Actual no of nodes has received broadcast packets, R(nd) → Number of nodes overall in the networks)

Figure 7. Rebroadcast Vs Number of Nodes (Node’s mobility is 30m/s)

Figure 7 demonstrates that the SRBS algorithm’s simulation result is improved than the other three algorithms because of rebroadcast ratio is minimum.

(Where RT → RT is that Actual number of nodes retransmitted packets, TN→The network’s total nodes are represented by the TN).

Figure 8. Average Latencies Vs Number of Nodes (Each Nodes Speed is 10m/s)

Below figure 8 graph shows that when we are increasing network size of nodes, then four algorithm’s broadcast latencies result is increasing. Average broadcast latency means from the interval time of the broadcast was started to destination host finishes at the time of rebroadcast. The DSB algorithm has less average latency than compare DFCN, SRBS and PEGSP algorithms. So, the DSB algorithm is a good performance because of minimum delay.

Figure 9. Reliability Vs Mobility (Size of nodes is 100)

In figure 9’s outcome demonstrates that as node speeds increase from 0 to 240 m/s, the SRBS algorithm is more reliable than the other three algorithms. Percentage number of node shas received that broadcast of packets within the network we called reliability. It concludes that SRBS algorithm’s result beyond other algorithms, but DFCN algorithm’s performance is incredibly poor.

This figure 10 we have seen the efficiency level of SRBS algorithm is better, more other algorithm’s results. In network percentage number of nodes forwarded the packets are called Efficiency. The figure 10, if we are increasing each of the node’s speed is 30m/s then the DFCN performance is slightly less of the PEGSP and DSB algorithm’s performance. Similarly, speed of mobile nodes was increased from 30 to 60 m/s at that time DSB algorithms performance same as PEGSP algorithm. So, as mobile node speed increases from 0 to 210 m/s on a regular basis, the performance of the two methods degrades.

Figure 10. Efficiency Vs Mobility (Mobile Nodes size is 150)

Figure 11. Throughput Vs Transmission Range (Size of nodes is 150 and mobility of nodes is 30 m/s)

The above figure 11SRBS algorithm contains good performance compare with the DSB, DFCN and PEGSP algorithm’s result when varies in the different transmission ranges. After rising transmission range up to 240m and each of the node’s speed is 30m/s, DFCN algorithm’s performance remains the same as DSB algorithm but it is higher than the PEGSP algorithm.

From figure 12, If we regularly varying degree of nodes up to 120 then the DSB algorithm gives higher throughput of DFCN,PEGSP and SRBS algorithms. So, the simulation graph DSB algorithm is healthier.

Figure 12. Throughput Vs Degree of Nodes (Node size is150 and node speed is 15m/s)

Figure 13. Network Connectivity Rate Vs No of Nodes

In Figure 13, the network connectivity rate is decreased if we increase the number of nodes. Thus, the SRBS algorithm produces better results than the other three algorithms.

Figure 14 compares the outputs of the four algorithms result. Performance is improved with the SRBS algorithm. The collision rate likewise rises as packet size grows.

Figure 14. Collision Rate Vs No of Nodes

It shows from figure 15 that as node size increases, there is more delay for four algorithms. The PEGSP algorithm is better than the DFCN algorithm up to a node size 100. When the number of nodes increases, the DFCN protocol outperforms the PEGSP protocol. The SRBS algorithm results best of three algorithms.

Figure 15. End-to-End Delay Vs No of Nodes

Figure 16. Connectivity Rate Vs Traffic Overload of Node

According to Figure 16, a node’s connection rate performance suffers as its traffic overload grows. As a result, the SRBS algorithm achieves better results than the DSB, DFCN and PEGSP algorithms.

5.CONCLUSIONS

The author proposed two broadcast protocols modify SRBS and DSB and compared them with well-known existing broadcast algorithms. It is a reliable and high efficiency in a different traffic pattern of highly mobile networks. When we send packets within the network, it takes minimum nodes for communication from source to destination. This algorithm reduces flooding, broadcast latency and redundancy problems. In our simulation, we have got measured the performance of reliability, efficiency, throughput, average latency and rebroadcast. We have got tested the results by varying node mobility, varies transmission ranges, number of nodes, degree of node, network size, network connectivity rate, collision rate, end-to-end delay, and traffic overload of the node. It shows best result when compared with the DFCN and PEGSP algorithms. Our result shows that once we increase the quantity of nodes and node mobility then the SRBS algorithm produces better results than the opposite three algorithms. In simulation results in some cases, we have seen that if we do not increase node mobility and the number of nodes, then the results of the DSB algorithm are better than the opposite three algorithms in terms of reachability, average latencies, and throughput (Degree of nodes). If we increase the number of nodes and do not increase node mobility, then the DFCN’s algorithm results are better than the PEGSP algorithm. This algorithm is minimizing the frame length to communication in the network, which implies it proves that the bandwidth of the channels is correctly utilized and provides the most throughputs.

CONFLICT OF INTEREST

The author has declared no competing interests for publication.

REFERENCES

[1] DemetresKouvatsos and Is-Haka Mkwawa, “Broadcasting Methods in Mobile Ad hoc Networks: An Overview”, Department of Computing, University of Bradford, UK, Department of Computer Science , University College Dublin, Ireland, in 2009.
[2] Ching-Chuan Chiang and Mario Gerla, “Routing and Multicast in Multi hop Mobile Wireless Networks”, University of California, Los Angeles. In Proc.ICUPC’97.
[3] Eroll L. Lloyd, “Broadcast Scheduling for TDMA in wireless multi hop networks”, Department of Computer Science and Information Sciences, University of Delaware, Hand book of wireless Networks and Mobile Computing Pages 347-368, 2002.
[4] S.Ramanathan and E.L. Lloyd, “Scheduling Algorithms for Multi Hop Radio Networks”, IEEE/ACM Transactions on Networking, 1:166-177, April 1993.
[5] Zygmunt.J.Haas and B.Liang, “ Ad hoc Mobility Management with Randomized Database groups”, 323 Frank Rhodes Hall, School of Electrical Engineering Cornel University, lthaca, NY 14853
Proceedings of the IEEE International Conference on communications 1756-1762, 1999.
[6] B. Williams and T.Camp, “Comparison of Broadcasting Techniques for Mobile Ad hoc Networks”, Department of Math and Computer Science , Colorado, School of Mines Golden, CO 80401, In
Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc 02),194-205, March 2002.
[7] Wei Lou and Jie Wu, “A Reliable Broadcast Algorithm with Selected Acknowledgements in Mobile Ad Hoc Networks”, Department of Computer Science and Engineering, Florida Atlantic University,
Conference on Global Telecommunications Conference, 2003. GLOBECOM ’03. IEEE, Volume: 6, January 2004.
[8] Brian J. Wolf, Joseph L. Hammond, Daniel L.Noneaker and Harlan B. Russell, “Distributed Formation of Broadcast Transmission Schedules for Mobile Ad Hoc Networks”,Dept. of Electrical and Computer Engineering, Clemson University, Clemson SC, IEEE Volume-6, 2007.
[9] J.Jetcheva, Y.Hu, D.Maltz and D.Johnson, “A Simple Protocol for Multicast and Broadcast in Mobile Ad hoc Networks”, Internet Draft, Draft-IETF-MANET simplembcast-01, 2001.
[10] Luc Hogie, Marcin Seredynski and Frederic Guinand, “A Bandwidth-Efficient Broadcasting Protocol for Mobile Multi-Hop Ad hoc Networks”, Pascal BouvryUniversity,Luxembourg6, rueR. CoudenhoveKalergiL- 1359 Luxembourg, Polish Academy of Sciences Ordona 2102-237, Warsaw, Poland, University du Havre 25, rue Philippe Lebon76600 Le Havre, France. Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies (ICNICONSMCL’06) Computer Society IEEE 2006.
[11] L. Hogie, F. Guinand, and P. Bouvry, “A heuristic for efficient broadcasting in the Metropolitan ad hoc networks”, University du Havre, University du Luxembourg. University du Havre, 25, rue Philippe Lebon 76600 Le Havre, France. University du Luxembourg Campus Kirchberg 6, rue R.Coudenhove-Kalergi L-1359 Luxembourg. In KES, pages 727–733, 2004.
[12] H.A Ali, M.S Saleh, M.A. Sadik, “An Efficient Reliable Broadcast Algorithm in Ad hoc Networks Based on Self-Pruning”,IJICIS, Vol.5, No. 1, July 2005.
[13] Chandra Kanta Samal, G.V. Singh and Sanjay Kumar Dhurandher, “Stable and Reliable Broadcast Scheduling in Multi-Hop MANET”, AND College, University of Delhi, New Delhi, India, SC&SS,
Jawaharlal Nehru University, New Delhi, India and NSIT, University of Delhi, New Delhi, India, International Journal of Engineering Science and Technology (IJEST), Vol. 3 No. 9 September 2011, page no. 6962-6969, ISSN: 0975-5462.
[14] Pei-Kai Hung, Jang-Ping Sheu and Chin-Shun Hsu, “Scheduling of Broadcasts in Multi-hop Wireless Networks”, Dept. of Computer Science and Information Engineering, National Central University Chung-Li, 320 Taiwan, R.O.C., European Wireless 2002 proceedings , 2002.
[15] Research Scholar S. Madhavi and Professor I. Ramesh Babu, “A New Method for Adaptive Broadcast Scheduling in Mobile Ad hoc Networks”, Department of Computer Science and Engineering,
Acharya Nagarjuna University Guntur, A.P., India, IJCSNS International Journal of Computer Science and Network Security, Vol.8 No.3, March 2008.
[16] Lim, H. and Kim, C, “Multicast tree construction and flooding in wireless ad hoc networks”, In Proceedings of the 3rd ACM international workshop on modeling, analysis and simulation of wireless and mobile systems, pages 61-68. ACM Press. (2000).
[17] Tseng, Y.-C., Ni, S.-Y, and Shih, E.-Y. “Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network”, In Proceedings of the International Conference on Distributed Systems, pages 481.488(2001).
[18] Peng, W. and Lu, X. C. ,“On the reduction of broadcast redundancy in mobile ad hoc networks”, In Proceedings First Annual Workshop on Mobile and Ad Hoc Networking and Computing, pages 129- 130(2000).
[19] Chandra Kanta Samal, “Reliable Time Slot Allocation Scheme among Mobile Nodes in MANET” AND College, University of Delhi, New Delhi, India, International Journal of Computer Science
Trends and Technology (IJCST), Volume 9, Issue 5, Sep-Oct 2021.
[20] GloMoSim:“Global Mobile Information Systems Simulation Library”, http://pcl.cs.ucla.edu/projects/glomosim.
[21] Mario GerlaLokesh Bajaj, MineoTakai, Rajat Ahuja, RajiveBagrodia, “GloMoSim: A Scalable Network Simulation Environment”, Technical Report 990027, University of California, 13, 1999.
[22] Richard A.Meyer and RajiveBagrodia, “PARSEC USER MANUAL for PARSEC. Release 1.1”, Revised in September 1999, http://pcl.cs.ucla.edu,1999.

AUTHOR

Dr. Chandra Kanta Samal received the M. Tech. (CS) and Ph. D(CS) from Jawaharlal Nehru University, New Delhi, India. Having 16th years of teaching experience in the field of Computer Science at AND College, Delhi University, New Delhi, India. More papers published on Wireless Networks, Image Processing and robotics in various International Journals and Conferences.