A trust management model based on NSGA-II in mobile grid system

Abstract

Mobile Grid network connects large number of mobile devices like smartphones, tablets, PDAs, wireless digital medical equipment’s etc for the purpose of sharing their resources and performing the task collaboratively and cooperatively. The mobile nodes participating in the mobile grid are autonomous and open in nature making them more vulnerable to data and control attacks made by malicious or selfish nodes. Preventing these malicious or selfish nodes and identifying the trusted nodes to participate in the network is an NP-hard problem. To recognize trusted nodes in the mobile grid system a novel trust management model is proposed in this paper by applying an elitist multi objective optimization algorithm Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The proposed trust management model assesses the trust index of each mobile node in the network using various evaluation factors or attributes and then obtains the non-dominated set of trusted nodes in each front. Comparative analysis of the proposed trust model shows that the proposed model can be a potential candidate for implementing trust management in mobile grid network.

Keywords

NSGA-II trust management mobile grid system

1. Introduction

Mobile Grid [1] network connects large number of mobile devices like smartphones, tablets, PDAs, wireless digital medical equipment’s etc for the purpose of sharing their resources and performing the task collaboratively and cooperatively. However, these mobile devices are having limited resources like energy and processing capability making them valuable. Also the mobile devices are autonomous in nature due to which the mobile grid network does not have fixed topology and structure. The communication channel and the route between the nodes in the network is also dynamic and open. There is no central control system to monitor the nodes in the network making the environment decentralized. These characteristics of the mobile grid network such as autonomous structure, dynamic participants and open nature make it more vulnerable to attacks from inside and outside the network. There are various mechanisms proposed in literature to handle the attacks in the mobile grid network. These mechanisms are categorized as preventive and reactive mechanisms. Preventive mechanisms avoid the attacks beforehand whereas reactive mechanisms take the corrective actions after the attack happens.

One such preventive mechanism is to allow only trusted nodes and prevent malicious or selfish nodes from participating in the network. Malicious nodes are the nodes that compromise the security of the system by participating selfishly into the network and degrading the performance of the system. Malicious nodes can intentionally drop the data packets and control packets to disrupt the communication between the peers in the network and consuming or blocking their valuable resources. Depending on the strategy, frequency and loss made by the attack, the attacks made by malicious nodes can be categorized as data traffic attack and control traffic attack [2]. Different types of attacks caused by malicious nodes are:

Eavesdropping – Here the malicious node reads the packets while transmission. Jamming – Here the malicious node introduces noise in the network with the intention of DoS. Block hole – Here the malicious node spreads false information and directs the whole traffic towards itself and the then drops the received data packets. Worm hole – Here multiple malicious nodes collaborate to share the confidential information. Gray hole – Here the malicious node misguides the network by sometimes behaving as normal node and sometimes dropping the data packets. Link spoofing – Here the malicious node claims itself to be the neighbor and directs the data packets to itself through a fake link. Rushing – Here the malicious node floods the network by broadcasting received route request (RREQ) packets and behaves like original sender of the packet. Flooding – Here the malicious node floods the network with false routing information with the intent of consuming large resources of the network. Sybil – Here the malicious node misguides the network by showing multiple identities of the target nodes and redirects the data packets to itself. Byzantine attack – Here multiple malicious nodes collaborate together to form loops in the network and affect the QoS by sending the data packets on non-optimal paths.

All the above attacks can be avoided by detection of malicious nodes and preventing them from participating the network. Malicious nodes can be detected by using a robust trust management system that assesses the trustworthiness of the participating nodes in the network. Nodes with low trust values are treated as malicious nodes and are restricted to enter the network.

In this paper we have proposed a novel trust management model for identifying trusted nodes in the mobile grid system by applying an elitist multi-objective optimization algorithm Non-dominated Sorting Genetic Algorithm-II (NSGA-II) [3]. The proposed trust management model assesses the trust index of each mobile node in the network using various evaluation factors or attributes and then obtains the non-dominated set of trusted nodes in each front. The latter part of the paper is composed of following sections: Section 2 discusses various approaches in literature for solving the trust management problem, Section 3 introduces the proposed approach based on NSGA-II, Section 4 evaluates the performance of the proposed approach with the existing fuzzy logic trust model and Section 5 discusses conclusion and future work.

2. Related work

There exists a vast set of solutions to solve the problem of trust management in mobile grid network. Different approaches for calculation of the trust index of a node in mobile grid network are fuzzy logic based approach, Bayesian networks based approach, approaches based on probability theory and other mathematical methods. However there are some of the trust management models based on genetic algorithms.

A trust management model GenTrust [5] proposed by Ugur Eray Tahta et al. [6] for P2P networks uses GA to calculate the trust index of the peers by extracts the features from past interactions and the recommendations received from other peers. GenTrustprovides securityfromnaive attackers, hypocritical attackers and pseudospoofers.

ChithraSelvaraj et al. [7] proposed a trust model based on peer profiling in which the peer profiles are assimilated with the detected unusual behavior using genetic algorithm. A peer establishes trusted relationship with other peers based on the comparison between the present and past transactions with the other peers. After each transaction, crossover and mutation operations are performed to dynamically update the peer profile. The unusual behavior of the peer is then detected using GA.

A fast and efficient trusted job scheduling algorithm Space-Time Genetic Algorithm (STGA) [8] is based on three security modes. A job is said to be in secure mode if the security of the allocated resource site fulfills the security requirements of a job. A job is said to run in unsafe mode if the job is allocated to any available resource. However, if the risk associated with the allocated resource site is limited to probability f, then the job is said to run in f-risky mode.

In crowdsourcing platform a task publisher is required to select the trustworthy workers for execution of the tasks. Selecting trustworthy worker can be modeled as a nonlinear multiobjective optimization problem. A model proposed by Ye et al. called MOWS_GA [9] solves this NP-hard problem by using NSGA-II. According to the proposed model the trustworthiness of the worker differs based on different task types and number of rewards. The proposed model effectively identifies the honest and dishonest workers based on the rates of Human Intelligence Tasks (HITs) approval.

A wireless sensor network can be efficiently deployed using different techniques like machine learning, neural networks, artificial intelligence, fuzzy logic and genetic algorithms. Such a clustered wireless sensor network consists of a cluster head CH that collects the data from the sensor nodes and forwards the data to one or more sink nodes. A cluster head is a node with the highest trust value. The author Nimbalkar et al. [10] has proposed a cluster head selection technique Trust-based Energy Efficient Clustering using Genetic Algorithm in Wireless Sensor Networks (TEECGA) based on GA. To enhance the security of the communication a set of trusted cluster heads is selected by TEECGA in which one trusted cluster head forwards the data to another nearest trusted CH and so on. The trust value of the CH is calculated using various metrics like outstanding energy, distance etc.

Wang et al. [11] proposed an efficient solution for solving the multi objective problem of node-to-task assignment in a service oriented mobile ad-hoc network (MANET). The proposed solution has three objectives: maximize the reliability, minimize resource consumption variance thereby maximizing workload balance and maximize the QoS. The algorithm is based on the concept of Beta ( $\alpha$ , $\beta$ ) distribution [11] for the direct trust evaluation and the concept of belief discounting [12] for recommender’s ( $\alpha$ , $\beta$ ) trust evidence.

Optimal Security with Optimal Overhead Scheduling (OSO2S) [13] is a secure task scheduling algorithm based on NSGA-II having multiple conflicting objectives viz minimize the Security Overhead (SO) and maximize the Security Level (SL).

NSGA-G [14] is an extension of NSGA based on grid partitioning strategy proposed by Le et al. to find the Query Execution Plans (QEPs) in cloud computing as per the user preferences such as minimum budget, low response time etc. The proposed grid partitioning method divides the entire population into small groups by using the nearest grid Min Point and nearest grid Max Point for each group and calculate and compare solutions in one group during each iteration. This reduces the computation time and improves the speed by reducing the size of population.

3. Propsed trust model

In autonomous systems like mobile grid there is no central point of control for managing the trustworthiness of the peers and nodes are dynamic in nature, which makes the problem NP-hard.

Thus trust management in such a self-organizing network should be efficient enough to determine the malicious behavior of the selfish nodes and allow only genuine nodes to perform the computational or data intensive tasks. In this paper we propose a trust management model using NSGA-II. The dual objectives of the proposed trust management system are to minimize the attacks and maximize the job success rate of the participants in the network. Thus NSGA-II is the most suitable elitist pareto optimal solution for solving multiobjective optimization problems like trust management.

3.1 NSGA-II

NSGA-II [3, 4] is an extension of the most popular multiobjective optimization algorithm [15] NSGA (Non dominated Sorting Genetic Algorithm). NSGA-II has two important properties:

Elitism preserving: NSGA-II selects the best set of solutions in the next itteration. Diversity preserving: NSGA-II also supports the diversity in the population.

These two properties differentiates it from other multiobjective optimization algorithms in literature.

The basic procedure of NSGA-II is shown in Fig. 1 [3].

Figure 1.

Basic structure of NSGA-II.

Table 1

Capability based features

Symbol	Feature	Description
F1	CPU available	Determines the processing capability of the node to execute the computationally intensive task
F2	Battery available	The battery of a mobile node is a limited local resource
F3	Storage available	Determines the storage capability of the node in case of data-intensive task
F4	Job success rate	Determines the number of successfully completed jobs
F5	Average task completion time	Determines the average time taken by the node to complete a task
F6	Online time rate	Determines the average time during which a node participates in the mobile grid network
F7	Bandwidth	Upload and download speed available used to determine the ability to send and receive date
F8	Operating system	Such as Android, iOS etc. determine the type of platform available

Table 2

Interaction based features

Symbol	Feature	Description
F9	Successful Interaction	Number of successful interactions between the peers
F10	Satisfaction	Level of satisfaction based on the successful interactions

Table 3

Recommendation based features

Symbol	Feature	Description
F9	Average of neighbors successful interaction	Average of successful interactions with the peer
F10	Average of neighbors satisfaction	Average of the satisfaction level based on successful interactions

NSGA-II uses two specialized multi-objective operators:

Non-dominated Sorting: When the genetic operators (select, crossover and mutation) are applied to the first population P, with N members, a new offspring population Q is generated with N members. After joining P and Q, and the total population R ${}_{\text{t}}$ with 2N members. Then nondominated sorting is applied to calculate the “front” and the crowding of each member of R ${}_{\text{t}}$ . Then the best N member of R ${}_{\text{t}}$ are selected and set as the new P. Thus nondominated sorting ensures elitism property. Crowding Distance: When sorting R ${}_{\text{t}}$ (with the length 2N), sort all individuals and calculate their “rank” and “crowding distance”. Select N individuals from the population R ${}_{\text{t}}$ (of length 2N) based on the following two criteria: first the “rank”, (individuals with less rank are preferred), and if two individuals have the same “rank” then the second criterion is “crowding distance” (individuals with more crowding distance are preferred). Thus crowding distance ensures diversity preservation in the population.

3.2 Feature sets

The proposed trust model analyze the characteristics of the malicious and genuine nodes by extracting the information of the peers based on their capability to perform the task, past interaction and recommendations. This information forms the feature set for evaluating the trusted nodes in the network using NSGA-II.

The features representing the capability of the peers to perform the task are based on the resources available on the node as per the task requirements. Features based on the capability of the mobile node to perform task are listed in Table 1.

The features based on past interaction are extracted from the experience of each peer while interacting with the other peers in the network. Table 2 contains the list of features based on past interaction.

Whenever a peer need to evaluate the trustworthiness of the other peer in the network, it request its neighbors to share their experience about the requested peer in the form of recommendations. This experience shared by the neighbors provide the bases for recommendation based feature set listed in Table 3.

The proposed trust model is then evolved using these three categories of feature sets by using NSGA-II to find the trusted nodes in the mobile grid.

3.3 Fitness function

Trust management in mobile grid network has dual objectives conflicting with each other i.e. minimizing the Number Of Attacks (NOA) and maximizing the Job Success Rate (JSR). The fitness functions determines the success of the proposed solution to solve this multi-objective problems. Equations (1) and (2) represent the fitness functions used by the proposed trust model for calculating the number of attacks and job success rate respectively.

$\displaystyle\text{Minimize Fit (NOA (p))}=\mathop{\sum}\limits_{i=1}^{n}\text% {NOA}_{i}$ (1) $\displaystyle\text{Maximize Fit (JSR (p))}=\mathop{\sum}\limits_{i=1}^{n}\text% {JSR}_{i}$ (2)

Where NOA ${}_{{i}}$ is the Number Of Attacks on the $i^{\text{th}}$ node and JSR ${}_{{i}}$ is the Job Success Rate of the $i^{\text{th}}$ node. To obtain a base case each experiment is run without having a trust model. This gives us an information about number of attacks and job success rate in the testbed environment in the absence of trust model. Then this base is compared with the results obtained after applying the trust model.

3.4 Trust management using NSGA-II

In mobile grid network the node who wishes to evaluate the trust value is called as trustor node. The trustor node needs to identify as set of trusted nodes to execute the submitted task successfully. The proposed trust model helps the trustor node to identify a set fittest nodes in the population based on non-dominated sorting and crowding distance. The fittest nodes in the population are selected as the most trustworthy nodes.

The steps involved in the trust management system using NSGA-II are as follows:

Step 1:
Using YenTopShortestPath algorithm find K-shortest loopless paths from trustor node to all other peers in the network.
Step 2:
Initially generate the parent population $P_{{i}}$ of all the $N$ nodes on each of the shortest path obtained in Step 1.
Step 3:
Generate the offspring population $O_{i}$ of size $N$ by applying the selection, crossover and mutation operators on the $N$ nodes in population $P_{{i}}$ .
Step 4:
Combine the parent population $P_{{i}}$ and offspring population $O_{{i}}$ to generate the total population $T_{{i}}$ of size $2N$ in the first iteration.

$\displaystyle{T}_{{i}}={P}_{{i}}\cup{O}_{{i}}$
Step 5:
Using the feature set described above and applying the non dominated sorting operator classify the population $T_{{i}}$ into the fronts $F_{i}$ , where $i=$ 1, 2, 3, …etc. Rank the population based on the front in which it belongs. For example, all the nodes in the first front will have the rank 1, all the nodes in second front will have rank 2 and so on. All the individuals in front $F_{1}$ are the best and are non dominated by individuals in the next front $F_{2}$ and so on.

Table 4
Input parameters for mobile grid environment

Parameter Value/range

No. of mobile nodes 10–50

Population size 10

Type of crossover Single point crossover

Mutation probability 0.9

Mutation operator Swap mutation

Selection operator Binary tournament selection

Figure 2.
Job success rate.

Figure 3.
Execution time.

Step 6:
Generate the next population $P_{{i}+1}$ using the following steps:

Select the population in each front beginning from front $F_{1}$ unless the size of the population in the next iteration $P_{{i}+1}$ is less than or equal to $N$ .

$\displaystyle\text{For }i=1\text{ to }|{P}_{{i}+1}|+|{F}_{{i}}|<{N}$ $\displaystyle\quad{P}_{{i}+1}={P}_{{i}+1}\cup{F}_{{i}}$ $\displaystyle\text{Next }i$

If the size of population in front $F_{{i}}$ is such that $|{P}_{{i}+1}|+|{F}_{{i}}|>{N}$ then apply the function crowdsort ( $F_{{i}}$ , $<_{\text{c}}$ ) to select the most diverse nodes in the population $P_{{i}+1}$ . The crowdsort function calculates the crowding distance $d_{{j}}$ of node $j$ in Front $F_{{i}}$ and sorts the nodes in the same front based on the two fitness functions for minimizing the attacks and maximizing the job success rate respectively.

Crowdsort ( $F_{i}$ , $<_{\text{c}}$ )

For $j=$ 1 to $|{F}_{{i}}|$

Crowding distance $dj=$ 0;

For each of the fitness functions $F_{{m}}$ for $m=$ 1 …2

Sort the population in $F_{{i}}$ in worst order for function $F_{{m}}$ and store the population in $F_{{m}}$ .

Assign the crowding distance for boundary nodes to maximum ( $\infty$ )

Calculate the crowding distance of the remaining nodes as shown in Eq. (3)

$\displaystyle d_{F_{j}}^{m}=d_{F_{j}}^{m}+\frac{F_{j}^{m}+1+F_{j}^{m}-1}{F_{m}% ^{\max}+F_{m}^{\min}}$ (3)

Where $F_{m}^{\max}$ and $F_{m}^{\min}$ is the maximum and minimum value of the node for fitness function $F_{m}$
Step 7:
Generate the offspring population $O_{{i}+1}$ for the next iteration from the parent population $P_{{i}+1}$ using the crowding distance tournament selection operator. The selection of the node $i$ over the node $j$ using the crowding distance tournament selection operator is based on two criteria’s:

Figure 4.
Battery utilization.

Figure 5.
CPU utilization.

Let $r_{{i}}$ and $r_{{j}}$ be the nondominated ranks of nodes $i$ and $j$ respectively. The node $i$ will be selected in the offspring population $O_{{i}+1}$

$\displaystyle\text{If }r_{{i}}<{r}_{{j}}$

Let $d_{{i}}$ and $d_{{j}}$ be the crowding distance of nodes $i$ and $j$ respectively. The node $i$ will be selected in the offspring population $O_{{i}+1}$

$\displaystyle\text{If }d_{{i}}>{d}_{{j}}$
Step 8:
Repeat until the maximum number of iterations is reached.

4. Results and discussion

Parameter	Value/range
No. of mobile nodes	10–50
Population size	10
Type of crossover	Single point crossover
Mutation probability	0.9
Mutation operator	Swap mutation
Selection operator	Binary tournament selection

To demonstrate the effective application of NSGA-II to solve the multi objective problem of trust management in mobile grid system we have deployed a mobile grid system by connecting a set of pervasively available android smartphones of different make like Samsung Galaxy On7 Pro, Xiaomi Redmi Note-11, Motorola G3 etc. using Wi-Fi. Experimental test bench includes corei7 with 3.6 Ghz CPU and 16 GB RAM. Environmental setup uses Node.js version 11.2.0, XAMPP Server version 7.3.5. The initial parameters used as input for the deployed mobile grid environment are shown in Table 4. In the deployed mobile grid system initially the trust value of all the mobile nodes is uncertain. Initial trust value of a node is calculated based on the features indicating the capacity of the node to perform or process the submitted task. Once the task is completed successfully the trust value of the nodes performing the task is revaluated based on successful or unsuccessful completion of the task. This direct trust value is calculated using the direct interaction based features. Similarly the recommendation trust is evaluated using recommendation based features. The total trust of each node is then obtained by aggregating the direct trust and recommendation trust. The proposed trust management model based on NSGA-II is then applied to find the most trustworthy nodes in the mobile grid to perform the further task with maximum job success rate and minimum security threat. The sample task submitted to each node is to process the ECG dataset of about 10000 patients. ECG data contains the cardiological signals that show the electrical activity. From the ECG data we can measure the heart rate of a patient and analyse if the patient requires immediate attention.

To prove the efficiency and applicability of the proposed trust management model based on NSGA-II we have compared it with a hierarchical fuzzy logic based trust management model HFSTrust [16] since fuzzy logic is most common approach used in majority of the trust management systems in literature. The performance of both the solutions is compared in terms of time taken by both the approaches to identify the trusted nodes in the network as well as utilization of resources such as battery and processor as mobile nodes are limited in these resources.

Identifying the trusted nodes in a reasonable time using optimum resources of the nodes in the network maximizes the job success rate of the system. Figure 2 shows the job success rate before applying the trust management model and after applying the trust management model on the mobile grid network with 40 nodes consisting of 10, 20, and 30 percentage malicious nodes.

Table 5
Average precision

TP	TN	FP	FN	Recall	Precision
90	2	3	5	0.9474	95
90	3	5	2	0.9783	92
90	2	5	3	0.9677	93
85	4	9	2	0.977	87
85	5	5	5	0.9444	90

Figure 6.

Accuracy in percentage.

The graph shown in Fig. 3 shows the time taken for execution of both the trust management systems. It can be clearly seen that the proposed trust management system based on NSGA-II outperforms the existing fuzzy logic basedsystem. Also the proposed system proves to be more efficient in terms of consumption of precious and limited mobile device resources like battery and CPU for computation of the trust of all the devices as shown in Figs 4 and 5 respectively.

Each model is executed for five rounds. During each round, both the algorithms are executed ten times to evaluate the trust index of 5 devices. The precision and accuracy of the algorithm is shown in contingency Table 5 and represented graphically in Fig. 6.

5. Conclusion

Trust management in mobile grid network is a NP-hard problem having dual objectives maximizing the job success rate and minimizing the security threats by allowing only trusted nodes to participate in processing or performing the task. In this paper a novel method is proposed to solve this multi objective problem by applying a fast and elitist multi objective optimization algorithm NSGA-II for trust management in mobile grid network. Experimental results prove that the proposed model identifies the trusted nodes at higher speed as compared to the existing fuzzy logic based trust model and consumes fewer resources like battery and processor. The proposed approach can be used as an efficient and alternative solution for most of the commonly used approaches like fuzzy logic, neural network etc.

References

Rosado

D.G.

Fernandez-Medina

Lopez

and Piattini

, Systematic design of secure Mobile Grid systems, Journal of Network and Computer Applications, 2011, 1168–1183.

Bhattacharya

Banerjee

Bose

Saha

H.N.

and Bhattacharya

, Different types of attacks in Mobile ADHOC Network: Prevention and mitigation techniques, Xiv preprint arXiv, 2011.

Deb

Pratap

Agarwal

and Meyarivan

, A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, APRIL 2002, 182–197.

Brownlee

, Clever Algorithms: Nature-Inspired Programming Recipes, 2011, 152–158.

Tahtaa

U.E.

Sen

and Can

A.B.

, GenTrust: A genetic trust management model for peer-to-peer systems, Applied Soft Computing, Elsevier, 2015, 693–704.

Tahta

U.E.

Can

A.B.

and Sen

, Evolving a Trust Model for Peer-to-Peer Networks Using Genetic Programming, in: European Conference on the Applications of Evolutionary Computation, EvoApplications: Applications of Evolutionary Computation, 2014, pp. 3–14.

Selvaraj

and Anand

, Peer profile based trust model for p2p systems using genetic algorithm, Peer-to-Peer Networking and Applications (1) (2012), 92–103.

Song

Kwok

Y.K.

and Hwang

, Security-driven heuristics and a fast genetic algorithm for trusted grid job scheduling, in: 19th IEEE International Parallel and Distributed Processing Symposium, 2005, pp. 1–10.

Wang

and Liu

, Crowd Trust: A Context-Aware Trust Model for Worker Selection in Crowdsourcing Environments, in: IEEE International Conference on Web Services, 2015, pp. 121–128.

10.

Nimbalkar

N.B.

Das

S.S.

and Wagh

S.J.

, Trust-based Energy Efficient Clustering using Genetic Algorithm in Wireless Sensor Networks (TEECGA), International Journal of Computer Applications, 2015, 30–33.

11.

Wang

Chen

I.R.

Cho

J.H.

and Tsai

J.J.P.

, Trust-Based Task Assignment with Multi-Objective Optimization in Service-Oriented Ad Hoc Networks, IEEE Transactions on Network and Service Management, 2016, 217–232.

12.

Cho

J.H.

Chen

I.R.

Wang

and Chan

K.S.

, Trust-based Multi-Objective Optimization for Node-to-Task Assignment in Coalition Networks, in: 19th IEEE International Conference on Parallel and Distributed Systems, 2013, pp. 372–379.

13.

Kashyap

and Vidyarthi

D.P.

, Security Driven Scheduling Model for Computational Grid Using NSGA-II, Journal of Grid Computing, Springer, 2013, 721–734.

14.

T.D.

Kantere

and d’Orazio

, An efficient multi-objective genetic algorithm for cloud computing: NSGA-G, in: International Workshop on Benchmarking, Performance Tuning and Optimization for Big Data Applications (BPOD), 2018.

15.

Konaka

Coitb

D.W.

and Smith

A.E.

, Multi-objective optimization using genetic algorithms: A tutorial, Elsevier, 2006, 992–1007.

16.

Han

Wen

Feng

and Ren

, Self-nominating trust model based on hierarchical fuzzy systems for peer-to-peer networks, Springer, Peer-to-Peer Networking and Applications, 2016, 1020–1030.

A trust management model based on NSGA-II in mobile grid system

Abstract

Keywords

1. Introduction

2. Related work

3. Propsed trust model

3.1 NSGA-II

3.3 Fitness function

Table 5 Average precision

References

Table 5
Average precision