Effective One-to-One Correspondence Method of O(N 2 Log(N)) Complexity between Distributed Units

Abstract

Recently, NCO (Network Centric Operation) has been intensively studied. The new concept provides many benefits by sharing information among distributed militaries linked by network. Based on these, we propose a novel correspondence algorithm of O(N²Log(N)) complexity while maintaining comparable BE (Battle Effects) with the optimal algorithm. We verify the efficiency of our algorithm in terms of complexity and BE by simulation and experiment. The results show that our algorithm improves BE up to 40% comparing to conventional random correspondence methods. Also, our algorithm speeds up by several orders comparing to the optimal algorithm while sacrificing BE only 6%.

Keywords

NCO (Network-Centric Operation)WTAP (Weapon Target Assignment Problem)BE (Battle Effects)SD (Standard deviation)MV (Maximum Value)

1. Introduction

Advanced science and communication technologies have raised a new paradigm of warfare. NCO (Network Centric Operation) is one of the warfare paradigms. It is a crucial theory of warfare in information-oriented society. It is to maximize each effect derived from various components over a network. This strategy is a famous idea that dates back to 1998 when US forces carried out a revolution in military affairs (RMA: Revolution in Military Affairs). It was introduced as a collaborative thesis by Vice Admiral Arthur Cebrowski and John Garstka, afterward; the thesis had spread throughout the world [1-3]. NCO is considered as an operational concept that all of the combat assets (weapon systems, combat arms, etc.) share integrated information through a network. It increases combat power by successful convergence of complex data. It also offers information superiority by information sharing of the sensor and shooter systems regardless of military organizations and local positions.

Figure 1 shows the NCO structure. The sensor grid allows us to access more easily on the battle situation by connecting different types of monitor-sensors. In addition, the engagement grid plays a role in increasing battle power by combining various weapon systems. The information grid closely connects sensor and engagement grids, allowing integration of the sensor and shooter system as if they were operated by a single device included in one grid. Synergy can be achieved by these network connections and the derived effects can be maximized even for a weapon system having platform units such as tanks, war vessels, and fighters. NCO enables the military to access the battle situation more quickly and exactly [3, 4].

Figure 1.

NCO conceptual map through grid network composition

Based on these benefits of NCO, we propose one-to-one correspondence algorithm which can produce magnificent effects in terms of complexity and BE (Battle Effects). Our experimental results show that our algorithm improves BE up to 40% comparing to conventional random correspondence methods. Also, our algorithm speeds up by several orders comparing to the optimal algorithm while sacrificing BE only 6%. This paper is composed of 4 sections. At the first section, we present the theoretical background and applications. Related works are treated on the second section. On the third section, we propose one-to-one correspondence algorithms. Simulation analysis of the proposed methods is presented in section 4. Finally, we conclude in section 5 with a description of future work.

2. Related Work

Our proposed algorithm is one-to-one correspondence method to achieve high efficiency with low complexity. There is a related work about a correspondence method, the WTAP (Weapon-Target Assignment Problem). The WTAP is one of methods that represented weapon-target assignment to maximize the destructive impact on the enemy's offensive objects. On the other hand, it minimizes the loss of our force's defensive objects from external attack. WTAP is a NP-Complete problem [5]. Kattar [6] proposed Weapon-Target Assignment performing associations between an enemy's attack plane and an interceptor plane. Castanon [7] offered an algorithm that finds a sub-optimal solution by using a non-linear network. In addition, Watcholder [8] proposed a solution to the WTAP involving neural circuits. Ahuja et al. [9] proposed a study on weapon-target assignment using a VLSN (Very Large-Scale Neighborhood) search algorithm to solve the WTAP. Luo et al. [10] proposed a study assigning air-to-air missiles using HAGA (Heuristic Adaptive Genetic Algorithm). In a recent study, JMC Liyun [11] has proposed the WTAP by using a pseudo-genetic algorithm and K-means clustering algorithm. MA Sahin [12] has attempted a study on weapon-target assignment similar to the suggestion of SES (Standard Expert System).

Many correspondence methods and WTAP have been proposed and wildly used. However, in NCO, we need to consider WTAP correspondence method as well. We propose a quite simple algorithm in comparison with other related works. Even though it has a low complexity, it performs as an optimal algorithm in terms of BE. In addition, our algorithm is applied to NCO as well as other environments (WTAP solution, War-Game Model, Internet-Game, Sports, etc.) with high efficiency and low complexity.

3. Proposed One-to-One Correspondence Algorithm

NCO provides significant benefits: a locally distributed unit can share mutual information on a network. Battle-field situation can be shared, decision-making and information-conveying can be done in timely manner. In addition, it is possible to shoot targets as soon as those are identified because sensors and weapon systems are connected.

N_{v a l} = {(N_{1} + N_{2} + N_{3} + N_{4} + \dots + N_{n})}^{2}

(1)

(N_val: the value of network, N_n: the value of system n)

Equation 1 is based on Metcalf's theory [3]. The value of the network is relative to the square of the summation of all n. It shows the importance of NCO. Proposed algorithm is to achieve a Metcalfe's law's by exploiting NCO benefits. The details about the proposed method are as follows.

3.1. Concept of Correspondence

Figure 2-(a) depicts the general concept of correspondence between the Blue Forces (N entities) and Red Forces (N entities). There are various correspondence methods between Blue Force (N_i) and Red Force (N_j). When the capability of each entity is different, there are great differences in terms of overall effects according to the various correspondence methods. This method can be applied to the battlefield. Figure 2-(b) shows how the Blue Forces (N entities) and Red Forces (N entities) correspond to the battlefield. Finding out the effective correspondence method is a crucial matter in a war to maximize winning rate for a battle.

Figure 2.

Conceptual diagram of common & NCO correspondence

We propose an algorithm that creates tremendous effects through the correspondence methods of complexity of O (N³) and O(N²Log(N)). The optimal correspondence method is to achieve the maximum effect by comparing with all of the Battle Effect when blue force i engages with red force j. However, this method is hard to apply to practice because the amounts of computation have increased rapidly according to the number of entities. (This algorithm has a complexity of O(N!) on N troops). To solve this problem, a sub-optimal method is required. In this paper, we propose 2 methods using the standard deviation and the maximum value. We define some terms in this paper: Battle Effect ij (BE_ij) means an effect when blue force i engages against red force j. The BE_ij is calculated by the MOE (Measures of Effectiveness: measure of operational success that must be closely related to the objective of the mission or operation being evaluated [13]). We calculate MOE applying Lanchester battle model of the equation 2 [14].

\begin{matrix} {< M O E >}_{j} = \frac{{< N}^{2} > j - < M^{2} > j}{N^{2}} \\ < N^{2} > j = \sum_{k = 1}^{T} * \sum_{k^{'} = 1}^{S} \frac{v_{k} p_{k j} n_{k j}^{2}}{1 + X_{k k'}} \end{matrix}

(2)

(< $N^{2}$ >j: Military strength index of blue force in battle j)

< M^{2} > j = \sum_{k = 1}^{T} * \sum_{k^{'} = 1}^{S} \frac{v_{k'} X_{k k'} q_{k' j} m_{k' j}^{2}}{1 + X_{k k'}}

(< $M^{2}$ >j: Military strength index of red force in battle j)

N²: Military strength of the first blue force

V_k: Weight of military strength for assets of blue K type

P_jk: Chance of survival of blue k assets in battle j

V_k': Weight of military strength for assets of red K' type

q_k'j: Chance of survival of red k' assets in battle j

X_kk': Asset loss of blue K type/asset loss of red K' type

n_k: Number of assets for blue force k

T: Types of blue force assets

m_k': Number of assets for red force k' type

S: Types of red force assets

3.2. Method using SD (Standard Deviation)

There is a precedent study using the standard deviation. The reference [15] is to reduce average waiting time of advertisement broadcasting in ubiquitous environment while our algorithm is to increase BE in NCO environment. In addition, the study has developed a soft real-time environment while our algorithm is close to a hard real-time. Figure 3 shows the method of correspondence algorithm using SD (standard deviation).

Figure 3.

Correspondence algorithm using the standard deviation

To use BET (Battle Effects Table) of Figure 3, the correspondence method using SD is as follow. Calculating the SD of red force j for blue force's side is as follows: SD (R₁ column) =7.95, SD (R₂ column) = 13.60, SD (R₃ column) =32.05, SD (R₄ column) =18.26, SD (R₅ column) = 20.08. We know that the maximum value is SD (R₃ column) = 32.05 and row 5 has the maximum value among column 3. Thus, blue force 5 engages in red force 3. The basic idea is to enhance effectiveness. Afterwards, the row of blue force 5 and the column of red force 3 are removed from BET. With iterating the above step, we can make one-to-one correspondence method as given in Figure 3. Our proposed algorithm using SD is as fallows.

SD (Standard Deviation) algorithm

/* Compile BET (Battle Effects Table) between blue force i and red force j by using Lanchester battle model */ Input: BET N = number of blue forces = number of red forces For n=N to 1{ Max = 0; For j=1 to n { /* Calculate the SD (Standard Deviation) of n blue forces of column j. The SD is calculated through the following formula (3). */

S D_{j} = \frac{\sqrt{\sum_{i = 1}^{n} {(E_{i j} - m)}^{2}}}{n} = \sqrt{\frac{\sum_{i = 1}^{n} {(E_{i j})}^{2}}{n} - m^{2};}

(3)

/*(SD: standard deviation of column j, E_ij: BE value of row i and column j, m: average BE value of column j */ } For j=1 to n { /* Compare SD value of each column(red force), choose maximum SD */ If SD_j > Max, then {Max = SD_j ; max_sd = j;} } j = max_sd; /* Column of Max SD */ Max = 0; For i=1 to n { /* Compare E_ij, choose maximum E_ij */ If E_ij > Max, then {Max = E _ij ; max_blue = i;} } i = max_blue; /* row of Max BE */ Choose the troop (blue force i) achieving the maximum BE among blue forces where red force column has the maximum value of SD; Remove row i, column j from BET }

3.3. Method using MV (Maximum Value)

Figure 4 is a procedure showing one-to-one correspondence method using the MV (Maximum Value) on the algorithm. The maximum efficiency can be found when blue force 1 – red force 4 and blue force 5 – red force 3 engage each other. When a Tie-Break occurs, blue force i takes the side that the BE is relatively small in comparison with other troops having great BE in the second place. Blue force 1 and red force 4 engage each other because the second BE is the smallest (BE₁₁= 17). The row of blue force 1 and the column of red force 4 are removed from the list of BET. With iterating the above step, we can make the correspondence as given in Figure 4. Our proposed algorithm using MV is as fallows.

Figure 4.

Correspondence algorithm using the maximum value

We briefly show the procedure to get maximum efficiency troop from BET since the procedure is similar to merge sort algorithm [16] which has O(N²Log(N)) complexity in even worse case time where N means the number of elements (the number of blue forces multiplied by the number of red forces).

MV (Maximum Value) algorithm

/* Compile BET (Battle Effects Table) between blue force i and red force j by using Lanchester battle model */ Input: BET Apply merge_sort_algorithm to BET Repeat MV_Correspondence_procedure until all of rows and columns in BET are removed MV_Correspondence_procedure Choose the troop (blue force i, red force j) having maximum BE from the sorted array Match the blue force i and the red force j Remove the row and column of the maximum BE (blue force i, red force j) from BET End MV_Correspondence_procedure

Table 1 shows a major difference among the proposed method, the random method, and the optimal method. As shown in Table 1, the optimal algorithm having the best effect is limited according to the increase of the number of troops because computation is quite complex. Even though the proposed algorithm decreases the complexity of computation a lot compared with the optimal algorithm, it shows the close effect to the optimal algorithm. These results are verified by the simulation.

Table 1.

Comparison of main contents by correspondence algorithm < troop number: N>

	Optimal algorithm	Proposed algorithm		Conventionalrandom algorithm
	Optimal algorithm	Standard deviation	Maximum value	Conventionalrandom algorithm
Method	Determine the best BE after comparing each BE.	Determine comparative advantage by using standard deviation.	Determine comparative advantage by using the maximum value.	Determine one-to-one correspondence by a regular sequential method.
Complexity of algorithm	O (N!)	O(N³)	O(N²LogN)	O(1)
Advantages	Achieve maximum efficiency	• Reduce complexity • Achieve BE close to the maximum efficiency	• Reduce complexity • Achieve BE close to the maximum efficiency	Minimum complexity
Dis-advantages	Increases complexity rapidly when the number of N increases	A slight decrease in BE in comparison with the optimal method	A slight decrease in BE in comparison with the optimal method	Poor BE

3.4. Dependability of Proposed Algorithm

The proposed algorithm can be applied to the NCO environment. This environment requires an effective plan to deal with dependability. In NCO, each entity connected to a network can perform mutual roles interactively even when some problems have arisen in an entity. This proposed algorithm provides a fault tolerance as follows. Figure 5 depicts that a coordinator manages blue force entity within a certain size. At this point, a coordinator compiles BET as well as performs command & control for subordinate units. In addition, a coordinator serves as indicators which issue tactical instructions. On a war, if there are some problems with a coordinator, the rest of the units substitutes for dependability by election algorithm. We use the Bully algorithm [17] for electing a coordinator to get the best BE. A coordinator can conduct a variety of correspondence methods based on battle information (Ex: one-to-one, one-to-many, many-to-one, etc.).

Figure 5.

Dependability of proposed algorithm

4. Simulation and Evaluation

The definition of parameter used on simulation is as follows. The number of troops used on X-axis of Figure 6 and Figure 7 means the number of total troops (blue forces and red forces). The time used on Y-axis of Figure 6 means run-time for calculating correspondence method. The sum of BE used on Y-axis of Figure 7 and Figure 8 means the sum of BE of each correspondence method. The scope of BE used on X-axis of Figure 8 means bounds of E_ij. To demonstrate the superiority of the proposed algorithm, three different situations are simulated. First of all, run-time is examined by increasing the number of troops. From this examination, it shows that it is difficult to use the optimal algorithm practically according to the increasing number of troops. The complexity of proposed algorithm is low while the performance is comparable to the optimal algorithm. For the second examination, the sum of BE value is compared among algorithms by increasing the number of troops to demonstrate its superiority. Finally, the proposed algorithm is simulated in a different range of BE value. The result of simulations is as follows. The simulation is used to compare BE among the optimal correspondence method, proposed correspondence method, and random correspondence method.

Figure 6.

CPU run-time vs. number of troops

Figure 6 shows run-time to calculate the 4 correspondence methods by increasing the number of troops. Run-time of the optimal algorithm rapidly increases after 4 troops. On 12 troops, the run-time of the optimal algorithm is 2,400 million times as long as the proposed algorithm. In addition, it is hard to simulate over 12 troops because too much simulation time is required. However, the run-time of our proposed algorithm is relatively short with the large number of troops. This experimental results show that the proposed algorithm is excellent in terms of the run-time.

Figure 7.

Sum of BE vs. number of troops

Figure 7 shows the sum of BE for each correspondence method as the number of troops increases. Simulation results show that the sum of BE in order of superiority is as follows: optimal algorithm, proposed algorithm, and random algorithm. The effects of proposed algorithms (methods of maximum value and the standard deviation) are close to the optimal algorithm. The proposed algorithm shows 40 % higher effects on average than the random algorithm.

Figure 8.

Comparison with BE by scope of effects

Figure 8 shows the sum of BE for each correspondence method as the various capabilities. Various ranges of BE represent troops having various military capabilities on the battlefield. We confirmed that the sum of BE in order of superiority is as follows: optimal algorithm, proposed algorithm, and random algorithm as the scopes of BE expand. Moreover, the proposed algorithm is close to the optimal algorithm and shows a similar effect.

5. Conclusion and Future Works

In this paper, we propose a correspondence algorithm that achieves good results based on the BE (Battle Effects) of distributed units in NCO (Network Centric Operation) environment. Experimental results show that the efficiency of the proposed algorithm is comparable to the optimal algorithm while amount of computation is dramatically reduced. On the other hand, it is verified that our algorithm improves BE up to 40% comparing to conventional random correspondence methods. Our proposed algorithm has high efficiency with the low complexity in comparison with conventional algorithms. We verify that the proposed algorithm is suitable to apply to the battlefield as well as it has the close BE to the optimal algorithm. Future works need to apply it to real battlefield. In addition, N-to-M correspondence method is required rather than a one-to-one correspondence.

Footnotes

6. Acknowledgments

This research is supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2011-0027263).

References

Cebrowski

Garstka

. “Network-Centric Warfare: Its Origin and Future.” U. S. Naval Institute Proceedings, 1998, pp. 1–6.

Cebrowski

. “The Implementation of Network-Centric Warfare.” Office of Force Transformation, Department of Defense, 2005, p. 7.

Park

S-H

Kim

J-H

. “Real-time NCW Systems Using Distributed Processing.” Kisse, Korea Computer Congress, Vol. 36, 2009, pp. 245–249.

Alberts

Garstka

Stein

. “Network Centric Warfare.” Developing and Leveraging Information Superiority, Stormingmedia. US, 1999, pp. 2–16.

Matlin

, “A Review of the Literature on the Missile-allocation Problem.” Operations Research, Vol. 18, No. 2, 1970, pp. 334–337.

Kattar

, “A Solution of the Multi-weapon, Multi-target Assignment Problem.” WP-26597, The MITRE Co, Bedford, MA, 1986.

Castanon

. “Advanced Weapon-target Assignment Algorithm Quarterly Report.” Tr-337, ALPHA TECH Inc., Burlington, Massachusetts, 1987.

Wacholder

. “A Neural Network-Based Optimization Algorithm for the Weapon-Target Assignment Problem.” dtic.mil, 1989.

Ahuja

Kumar

Jha

Orlin

. “Exact and Heuristic Methods for the Weapon Target Assignment Problem.” Operations Research-Baltimore, ise.ufl.edu. 2007.

10.

Luo

Shen

Wang

. “Air Combat Decision-making for Cooperative Multiple Target Attack Using Heuristic Adaptive Genetic Algorithm.” Proceedings of the 4th International Conference on Machine Learning and Cybernetics, Guangzhou, 2005, pp. 473–478.

11.

Liyun

JMC

. “Solving Weapon-Target-Assignment Problem Based on Cluster Analysis.” Science, en.cnki.com.cn, 2009.

12.

Sahin

Leblebicioglu

. “A Standard Expert System for Weapon Target Assignment Problem.” Telecommunication Systems, 12th international conference, portal.acm.org, 2009.

13.

Votruba

Nisley

Rothrock

. “Technical Report 2001- 002, Measures of Effectiveness (MOEs) and Measures of Performance (MOPs).” SINGLE INTEGRATED AIR PICTURE (SIAP) System Engineering Task Force (SE TF), 2001.

14.

Jung

W-S

Lee

J-Y

, “A Study on the Measurement of Force Improvement Effectiveness of Korean Joint Command & Control System.” Korms, 2008, p. 350.

15.

Lee

B-H

Lim

S-H

Kim

J-H

Cho

. “Efficient and Fair Scheduling for Two-level Information Broadcasting Systems.” Concurrence and Computation-Practice & Experience. Vol. 20, 2008, pp. 2170–2200.

16.

Johnsonbaugh

. “Algorithms.” Pearson Prentice Hall, pp. 219–225, 2003.

17.

Tanenbaum

Van Steen

. “Distributed Systems.” Pearson Education Inc., 2007.