Preemptive MACO (MACO-P) Algorithm for Reducing Travel Time in VANETs

Figures & data

Figure 1. Flowchart for the MACO-P algorithm.

Figure 2. Pseudocode for the preemptive sub algorithm.

Figure 3. Pseudocode for the MACO-P algorithm.

Figure 4. Snapshots of various networks used: (a) simple road network, (b) complex road network, (c) University of Delhi network, and (d) North West Delhi network.

Table 1. Waiting and travel times in various networks.

	Overall waiting time (in ms)			Overall travel time (in ms)			Overall waiting time (in ms)			Overall travel time (in ms)
	Dijkstra	MACO	MACO-P	Dijkstra	MACO	MACO-P	Dijkstra	MACO	MACO-P	Dijkstra	MACO	MACO-P
VEHICLES	Simple network						Complex network
600	2839	1577	1329	24,373	30,777	28,453	5018	1620	1582	35,188	35,635	34,954
900	7027	2108	1984	36,485	44,911	41,256	12,174	5742	3214	55,516	55,230	52,419
1200	14,111	4396	3654	53,655	61,551	55,214	36,538	7432	4568	116,326	95,094	78,546
1500	30,182	5343	4487	80,702	77,552	75,412	44,597	9240	7542	117,838	110,861	88,672
1800	47,203	7777	6521	106,768	96,399	94,785	62,629	10,001	8659	151,291	122,942	92,457
2100	60,882	8138	7025	130,059	111,210	99,854	89,117	20,617	12,405	192,514	126,836	99,875
2400	80,730	8451	7269	159,807	112,654	10,058	126,963	36,529	28,035	244,723	131,334	101,458
2700	107,544	8877	7413	196,855	121,405	10,657	165,376	48,079	36,547	297,464	135,107	105,478
3000	137,573	9382	7862	236,929	122,767	10,859	207,776	59,270	45,025	354,539	143,862	10,987
3300	172,673	9698	8247	281,866	122,816	10,963	274,113	78,108	56,457	434,487	169,021	110,259
3600	240,870	11,017	9504	509,167	126,888	11,028	338,134	95,566	69,542	562,966	171,275	11,231
3900	292,849	18,255	12,016	821,570	156,846	11,154	462,546	103,635	84,579	651,297	188,726	11,598
VEHICLES	Real-time DU network						Real-time NWD network
600	2878	529	342	46,789	42,967	40,215	18,618	1600	1325	90,051	74,162	65,478
900	10,975	1371	1125	75,277	46,630	42,541	49,856	3729	1987	150,720	101,590	79,543
1200	21,624	3101	2541	107,066	101,207	65,489	61,750	7490	2354	198,286	143,385	85,479
1500	36,361	7286	3627	140,261	135,160	85,476	120,676	11,677	4529	279,660	175,432	93,157
1800	45,967	9487	5487	173,127	170,757	96,587	158,252	15,051	6587	365,911	228,537	101,598
2100	59,248	12,209	7825	208,321	205,078	108,541	243,077	48,684	7896	486,826	241,382	106,587
2400	78,841	17,264	8964	249,799	222,477	112,547	389,057	58,004	9648	667,761	289,037	112,689
2700	94,210	22,005	9247	287,198	238,850	146,547	670,521	69,547	10,254	983,066	405,814	126,926
3000	120,114	23,922	9876	335,756	282,950	152,598	1,057,375	79,428	10,658	1,603,810	425,784	148,756
3300	140,041	36,941	10,054	377,792	294,444	179,876	1,131,682	88,751	11,025	2,413,606	454,785	178,542
3600	177,282	44,251	10,265	436,553	382,338	185,478	1,201,634	96,547	11,542	3,418,917	485,478	198,755
3900	209,047	50,279	11,429	490,118	399,071	216,547	1,692,484	131,524	25,487	4,545,012	504,125	254,139

Figure 5. Overall waiting time in various networks: (a) simple road network, (b) complex road network, (c) University of Delhi network, and (d) North West Delhi network..

Figure 6. Overall travel time in various networks: (a) simple road network, (b) complex road network, (c) University of Delhi network, and (d) North West Delhi network.

Table 2. t-test for Dijkstra, MACO and MACO-P algorithms in various networks in terms of travel time.

t-test: simple network
	Dijkstra		Values for Dijkstra and MACO	MACO	Values for MACO and MACO-P	MACO-P
Mean	219853			98814.67		38307.75
Variance	53973616385.45			933383.69		1208297097.11
Observations	12			12		12
Hypothesized mean difference	0			0		0
df			12		22
t Stat			1.78	4.09
P(T ≤ t) one-tail			0.0301	0.0002
t critical one-tail			1.78	1.72
t-test: complex network
	Dijkstra	Values for Dijkstra and MACO		MACO	Values for MACO and MACO-P	MACO-P
Mean	152081.75			39653.25		29846.25
Variance	20716023940.75			1360504479.84		814167678.02
Observations	12			12		12
Hypothesized mean difference	0			0		0
df		12			21
t Stat	2.62		0.73
P(T ≤ t) one-tail	0.0111		0.0237
t critical one-tail		1.78			1.72
t-test: real-time DU network
	Dijkstra	Values for Dijkstra and MACO		MACO	Values for MACO and MACO-P	MACO-P
Mean	244004.75			210160.75		119370.17
Variance	20821653524.02			13861760948.6		3292760242.2
Observations	12			12		12
Hypothesized mean difference	0			0		0
df		21			16
t Stat		0.63			2.41
P(T ≤ t) one-tail		0.0268			0.0144
t critical one-tail		1.72			1.75
t-test: real-time NWD network
	Dijkstra	Values for Dijkstra and MACO		MACO	Values for MACO and MACO-P	MACO-P
Mean	1266968.			294125.92		129304.08
Variance	2128443123525.8			24155422925.6		3141138985.36
Observations	12			12		12
Hypothesized mean difference	0			0		0
df		11			14
t Stat		2.29			3.46
P(T ≤ t) one-tail		0.0211			0.0019
t critical one-tail		1.79			1.76