# Cooperation-Driven Virtual Terminal Coalition Formation Games for Task Assignment in Mobile Crowdsensing

Authors: Haifei Yu; Shiyong Chen; Xiang Liu; Yucheng Wu
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Mobile crowdsensing (MCS) is a popular way of data collection, which forms the large-scale sensing system by smart mobile terminal users and provides multimodal sensor data. In the sensing scenario, there are various sense resource requirements of tasks released by the platform. One of the most urgent issues in MCS is how to choose corresponding users with appropriate sense resources to accomplish assigned tasks. In this article, cooperating among a host of users to perform sense tasks is considered. Firstly, the cooperation among users to accomplish the sense tasks is described as an overlapping coalition formation game (OCF game). In addition, an initial coalition method of using social networks (SN) is proposed to accelerate the formation of coalition. Finally, the cooperation degree is used to describe the cooperative relationships among users, and virtual terminal coalition formation (VTCF) algorithm is proposed to simplify the process of coalition formation. The simulated results show that the proposed approach effectively improves the system’s utility under the constraints of task cost and sense quality.


---

## Body

## 1. Introduction

With the development of Internet technology and the popularization of smart devices, diverse high-performance sensors have been embedded into smart terminals, which can monitor and collect surrounding data to promote the development of mobile crowdsensing (MCS). Many new applications have been developed based on smart terminal sensing, such as smart healthcare [1], environment sensing [2], traffic condition detection [3], news [4], and even social networks [5]. Generally, these applications can be divided into three types [6]: personal sense, group sense, and community sense [7]. The mobile crowdsensing, in which a certain number of users are encouraged to participate in smart terminal sensing, is applied to ensure the sense quality of applications.A typical MCS framework consists of task requesters, sense platforms, and mobile users [8–12]. In MCS, the sense platform assigns tasks required by requesters to the users, and then the matched users complete the tasks through mobile terminals. Finally, users upload the sensed results to the platform. Users upload information collected by sensors to the sense platform via wireless communication technologies such as WIFI and cellular network [13]. With the development of 5G [14], SDN [15], D2D [16], and other communication technologies, the communication in MCS has become faster, and the communication performance has also been greatly improved.While sensing and uploading data, users need to consume their resources, such as battery energy, computing, and communication. Therefore, unless users are rewarded for compensating for the resources they consume, they may not be interested in sensing tasks. If the platform cannot recruit enough users, then sense quality of the task could not be guaranteed, which will affect the service quality provided by the platform. Hence, some works have considered the incentive mechanism to motivate users participating in the sensing task for the MCS system. The mechanism [17] considers the potential contribution of reverse auction and maintaining existing users when participants recruit new users. The optimization goal is to optimize the composition of users in the system while reducing the system cost. By quantifying the reputation of users [18], an incentive mechanism based on local differential privacy is proposed, which includes four aspects: incentive, reputation, data disturbance, and data aggregation. The incentive mechanism can select users who can offer more accurate data and compensate users who have spent privacy costs. Simultaneously, the reputation mechanism quantifies the reputation of users to improve the benefits of users.It is worth pointing out that, during choosing sense tasks, it is assumed that users will make independent decisions and do not know how their strategies affect the sense performance of each task in most literatures. Therefore, most users are likely to participate in a popular task, while other tasks distributed by the platform cannot recruit enough participants, which leads to uneven allocation of users’ resources and a decrease in sensing quality. When the platform releases complex tasks, the user’s limited sense resources may affect the completion of the task.To prevent the problem of uneven resource allocation mentioned above, cooperating among users is considered. Through cooperation and information exchange, users can understand the specific circumstances of their selected tasks, making more intelligent resource allocation choices. Considering the selfishness and reasonability of users, the coalition game theory is considered as an appropriate method to describe users’ cooperation relationships [19]. However, most of the literatures using coalition formation game for user cooperation assume that one user can only join one coalition [20], which is not suitable for practical scenario. As each user can participate in multiple sense tasks in the MCS system, the coalitions for different sense tasks may be overlapped.To tackle the issues discussed above, a novel incentive mechanism that uses social networks to recruit users for the MCS system is described. Users can cooperate through social networks to complete tasks released by the platform. In the process of coalition forming, the concept of cooperation degree inspired by the concept of trust degree [21] is proposed to describe cooperation relationships among users. The main contributions of this paper are summarized as follows:(1)
The concept of cooperation degree in the MCS system is introduced to better describe cooperation relationships among users. When the user completes the task, the corresponding cooperation degree will be updated at once, which estimates the positivity of users taking part in the coalition.(2)
To accelerate the formation of coalitions, a coalition initialization method based on SN according to the characteristics of users’ social networks is proposed, which makes coalition formation much faster.(3)
The task allocation problem in MCS is described as an OCF game. To simplify the process of coalition formation, a virtual terminal coalition formation algorithm (VTCF algorithm) is proposed, which can transform an overlapping coalition problem into a nonoverlapping coalition formation one. Moreover, virtual terminals choose different coalitions to join and allocate sense resources to maximize the system utility. Through simulated experiments, the proposed and reported task allocation algorithms are evaluated and compared. Experimental results have verified the effectiveness of the proposed algorithm.The rest of this paper is organized as follows. First of all, the related works are reviewed in Section2; and then system models are described in Section 3. In Section 4, an OCF game is used to describe task assignment of MCS. A coalition initialization method based on SN and the VTCF algorithm are proposed to solve the forming of coalition and the utility of platform is evaluated. In Section 5, the proposed task allocation algorithm is simulated and the effectiveness of the proposed algorithm has been verified. In the end, the related works discussed in this paper are concluded in Section 6.


## 2. Related Works

At present, some researchers have summarized the research work of task assignment [22–26] and cooperation mechanism [27–30] from different perspectives.Usually, participants will not voluntarily participate in tasks provided by the sense system. Due to the selfishness of users, the appropriate task allocation and cooperation mechanism are very important to improve the performance of the system. The two complementary modes of opportunistic participation and participatory participation into a two-stage hybrid framework called HyTasker were proposed in [22]. In an offline stage, one group of users (called opportunistic users) is selected, and they complete MCS tasks in daily life. In an online stage, the other groups of users (called participatory users) is assigned; they are required to perform tasks that opportunistic users cannot accomplish. A task management framework called Spatial Recruiter to match staffs to perceptual tasks effectively was proposed in [23]. A greedy heuristic method is designed to select and allocate workers. An optimal incentive mechanism for service providers was studied in [24]. The two-stage Stackelberg game method was used to analyze the participation degree of mobile users and optimal incentive mechanisms of service providers by backward induction. In order to motivate the participants, an incentive mechanism was designed by taking the social network effect, which was from the underlying mobile social field, into consideration. An incentive mechanism algorithm of joint coverage and reputation based on Stackelberg game theory was developed in [25]. In the first place, location information and the historical reputation of mobile users were used to select optimal users, meeting the user’s requirements for information quality. Secondly, the two-stage Stackelberg game was employed to analyze the sense level of mobile users; in this way, an optimal incentive mechanism of the server center was obtained. Last but not least, the expectation maximization (EM) algorithm is used to evaluate the data quality of tasks, and the historical reputation of each user is updated accordingly. An incentive mechanism was proposed in [26], which first selected some users from online social networks as seeds and then social relationships among users were used to influence selection of potential candidates for task execution. The target was to maximize the number of recruiters and increase coverage based on the initial seed.A smartphone collaborative sense system to encourage users to participate in sense tasks was considered in [27]. In the case of limited wireless channel resources, the authors therein discussed the incentive mechanism of cooperation and noncooperation and expressed the cooperation of users to complete tasks as overlapping coalitions forming game. Users maximize their own interests by choosing multiple coalitions to join and invest in wireless resources. Compared with noncooperative methods, the system performance will be improved if the cooperative method has been adopted. The cooperation between secondary users (SUs) in cognitive radio to improve sense performance and spectrum efficiency was discussed in [28]. Each SU makes its own cooperative sense decision according to its own business needs. SU’s cooperation was described as the formation of overlapping coalitions and proved the stability of the coalition structure. The cooperation strategy between roadside units (RSU) was studied in [29]. Through cooperation, the RSU can coordinate the data types transmitted to the vehicle through the vehicle-to-roadside (V2R) communication link. This solution used the underlying content-sharing V2R communication network increased the diversity of information circulation in the network. Compared with the noncooperative situation, the average rate of return has been improved. A strategy based on a genetic algorithm approach was proposed to achieve optimal collaborative learning groups and the system performance in [30].


## 3. System Model

In this section, the MCS system model is given, which is composed of a service platform, a wireless base station (BS), and some users carrying smart terminals, as shown in Figure1. In the system, the sensing platform publicizes N sense tasks, and the set of sense tasks is denoted by N=1,2,…,N. The set of smartphone users is denoted by M=1,2,…,M. To simplify the model analysis, it is assumed that a user has only one mobile terminal. The concept of the terminal is equivalent to the user in the subsequent sections. M mobile terminal users form a social network, represented by graph G=V,E; in a G, the vertex v∈V represents a user on the social network and connects with other users through undirected edges; and the edge e∈E stands for the communication from its source user to its direct destination user. The weight of the edge indicates the degree of cooperation between the mobile users m and n is expressed as com,n. If the value of the cooperation degree is larger, it means that the cooperation relationship is more positive.Figure 1
System model of MCS.It is supposed that a mobile terminal user has at mostr0 types of sense resources and there are l kinds of sense resources in the MCS system; each user i∈M is associated with sense resource si, which is a set of sense resources owned by user i, denoted as si=1,2,…,r0; for example, the user has three kinds of sense resources: si=1,2,3. Sense cost of sense resources ci,j represents the cost of user i providing sense resources j. Ci expresses the total cost of user i providing all sense resources. Neighbor ni is the set of social neighbors of user i, where ni=b|i,b∈E, and user b is the neighbor of user i; for example, the neighbor set of user 1 is n1=2,3 as shown in Figure 1. Sense quality of sense resources qi,j expresses sense quality of user i providing sense resource j. The larger value of qi,j means stronger sense ability of user i.Taskk∈N is denoted by Rk,Dk,Bk,Uk,CAk. Rk expresses a group of sense resources required for task k. Dk represents the quality requirements of sense resources for task k. Bk represents the budget of task k. Uk expresses the revenue of task k, and CAk expresses the amount of computation required to execute task k. It is supposed that a task always requires multiple users with different sense resources to cooperate with each other. Each user can freely allocate sense resources among these tasks. An N×K matrix S represents resource allocation, in which si,jk=1 denotes that user i provides the j-th resource for task k. Resources of the terminal i are limited as(1)∑j∈si∑k∈Nsi,jk≤r0.The utility function of the certain task, which is a function of terminal sense cost and task budget, is used to evaluate the performance of accomplishing each task. The set of users participating in taskk is denoted as Mk. The utility function of task k is given by(2)Uk=RNkRk×Bk−∑i∈MkCi,where Ci=∑j∈sici,j, RNk is the number of sense resources all users actually provided for task k, and RNk/Rk is the completion rate of task k. When the user completes the sense task, the cost usually includes consumption of battery energy and computing resources [31]. When the user i performs sense task, the consumption of computing resources and battery energy can be expressed as ti and ei. Let fi>0 denote the computing capability of terminal i in terms of CPU cycles/s. If user i provides sense resource j to execute sense task k, the task completion time is ti=caj/fi, where caj represents the amount of computation required to provide sense resource j [32], where caj=CAk/Rk.To calculate the energy consumption of the terminal performing tasks, the energy consumption model widely usedE=κf2 for each computing cycle [33], where κ is the energy coefficient depending on the chip structure and f is the CPU frequency. Therefore, the energy consumption eij of terminal i when providing resource j is calculated as(3)eij=κfi2caj.Therefore, the total cost of useri participating in task k to provide resource j is(4)ci,j=κfi2caj+cajfi.Considering all tasks of the platform, the utility function of the platform is given by the following formula:(5)Uplatform=∑k∈NUk=∑k∈NRNkRk×Bk−∑i∈Mk∑j∈sici,j.If users consume their resources without getting any benefits from the sensing platform, they will not be willing to participate in the task. To encourage users to participate in the task and ensure the quality of task completion, an incentive mechanism is designed in which users will be rewarded in the platform according to their contributions to the task. The total revenue of useri can be defined as(6)Pi=∑k∈Npik−Ci,where pik represents the benefit of user i from task k. The total benefit for user i can be described as ∑k⊂Npik=ω∑k⊂NUk, where ω is an incentive factor. Because the benefits of users from different tasks are different due to the resources invested in the task and the utility of task, the resource allocation among tasks is significant to maximize their benefits and improve the platform’s performance.


### 3.1. Centralized Case

Note that users are not willing to participate in tasks without pay. Therefore, the platform needs to reward the contribution of users, which is often called an incentive mechanism. For an existing MCS system, the platform provides an incentive mechanism, while users try to get maximum profits from the platform. The centralized case represented the upper bound of the system sense performance [27], where users are fully scheduled by the platform. In the centralized case, users are forced to participate in the task without any reward. The platform determines how users participate in the task. This example describes the upper bound of the system’s sense performance, which does not exist in practice because users are unwilling to participate in tasks without any reward.Given the constraints in (1), the utility of platform in centralized case is(7)Uplatform=maxS∑k∈NUk,s.t.∑j∈si∑k∈Nsi,jk≤r0.This is a 0-1 integer nonlinear programming (INLP) problem, which can be solved by optimization algorithm [34].


### 3.2. Cooperative Approach

The resource allocation problem of the terminals can be modeled as an OCF game. The terminal has the right to determine the resources allocated to each task. In this scenario, it is supposed that a coalition corresponds to a task and the members of the coalition complete relevant sensing task in the OCF game. Moreover, the members of the coalition can allocate sense resources for different tasks. Based on the OCF game model, the overlapping coalition formation algorithm is suitable for multiterminal sense resource allocation. The algorithm can converge to a stable overlapping coalition structure (OCS), improving overall sense performance. The coalition for completing the task can be described as the coalition members and the allocation resources of members.Definition 1.
The sense resource allocation problem of terminal is modeled as OCF game, which is expressed asM,V, where M represents the set of terminals and V represents the coalition value; the coalition value of coalition Ck is defined as(8)VCk=RNkRk×Bk−∑i∈Ck∑j∈sici,j.
To represent the cooperation behavior among terminals, the cooperation degree between the terminalsm and n is described as com,n. The cooperation degree of the coalition is represented by CoCk=∑m,n∈Ckcom,n. Assuming that the cooperation degree among all terminals with cooperation relationships is initialized with the same initial value co0m,n=c>0, among them, the cooperation degree of coalition member i is expressed as(9)coi=CoCkRk∑i∈Ckpikgipik,where ∑i∈Ckpik is the income of all users participating in task k and gi represents the number of sense resources contributed by terminal i to the coalition. The update of cooperation degree among users will be introduced in the third part of Section 4.
In OCF game model, the coalition structure is a set of the total coalitions for accomplishing all tasks and is denoted as∏=C1,C2,…,CN. Each task corresponds to a coalition. Therefore, the size of the coalition structure is fixed, which is equal to N.
When a coalition completes the task, it can be called an effective coalition. The set of effective coalitions is called an effective coalition structure (ECS). In the process of coalition formation, on the one hand, terminal resource allocation needs to maximize the cooperation degree of coalition. On the other hand, it needs to form the coalition with the most significant coalition value. The sense resource allocation problem of all terminals can be formed as the following optimization problem:(10)Uplatform=maxS∑Ck∈∏αCoCk+βVCk,s.t.Rk⊆∪i∈Cksi,qi,j≥dk,j,∀i∈Ck,j∈si,∑i∈CkCi≤Bk,where α,β are scale factors, satisfying α+β=1;α,β∈0,1 and dk,j represents the sense quality requirement of sense resource j in coalition Ck. The goal is constrained by three equations: Rk⊆∪i∈Cksi means that the sense resources provided by the terminal must satisfy sense resources required by sense task k, qi,j≥dk,j,∀i∈Ck,j∈si, means that the quality of the sense resources provided by terminal i is not lower than the quality of sense resources required by the task, and ∑i∈CkCi≤Bk means that cost of coalition Ck to complete the task does not exceed the budget of the task.
Usually, the coalition pays users a certain reward in some form according to its resource allocation. Hence, a reasonable method of income distribution is very crucial to motivate them to join a coalition. In the OCF game model, the return is a finite vector, expressed byP=p1,p2,…,pN. pk is the revenue of coalition Ck. In the proposed OCF game, it is assumed that the total profits of the coalition are affected by the participating degree of coalition members. The coalition will offer rewards to its members. For terminal i∈Ck, the revenue of terminal i from coalition Ck is defined as follows:(11)pik=ωVCk∑j∈sisi,jk∑i∈Ck∑j∈sisi,jk,where si,jk represents the resources provided by terminal i for coalition Ck and ∑j∈sisi,jk represents total resources provided by terminal i for coalition Ck. With the revenue that terminal i obtained from coalition Ck, the terminal i’s total revenue from the platform is(12)Pi=∑Ck∈∏ωVCk∑j∈sisi,jk∑i∈Ck∑j∈sisi,jk−Ci.


## 3.1. Centralized Case

Note that users are not willing to participate in tasks without pay. Therefore, the platform needs to reward the contribution of users, which is often called an incentive mechanism. For an existing MCS system, the platform provides an incentive mechanism, while users try to get maximum profits from the platform. The centralized case represented the upper bound of the system sense performance [27], where users are fully scheduled by the platform. In the centralized case, users are forced to participate in the task without any reward. The platform determines how users participate in the task. This example describes the upper bound of the system’s sense performance, which does not exist in practice because users are unwilling to participate in tasks without any reward.Given the constraints in (1), the utility of platform in centralized case is(7)Uplatform=maxS∑k∈NUk,s.t.∑j∈si∑k∈Nsi,jk≤r0.This is a 0-1 integer nonlinear programming (INLP) problem, which can be solved by optimization algorithm [34].


## 3.2. Cooperative Approach

The resource allocation problem of the terminals can be modeled as an OCF game. The terminal has the right to determine the resources allocated to each task. In this scenario, it is supposed that a coalition corresponds to a task and the members of the coalition complete relevant sensing task in the OCF game. Moreover, the members of the coalition can allocate sense resources for different tasks. Based on the OCF game model, the overlapping coalition formation algorithm is suitable for multiterminal sense resource allocation. The algorithm can converge to a stable overlapping coalition structure (OCS), improving overall sense performance. The coalition for completing the task can be described as the coalition members and the allocation resources of members.Definition 1.
The sense resource allocation problem of terminal is modeled as OCF game, which is expressed asM,V, where M represents the set of terminals and V represents the coalition value; the coalition value of coalition Ck is defined as(8)VCk=RNkRk×Bk−∑i∈Ck∑j∈sici,j.
To represent the cooperation behavior among terminals, the cooperation degree between the terminalsm and n is described as com,n. The cooperation degree of the coalition is represented by CoCk=∑m,n∈Ckcom,n. Assuming that the cooperation degree among all terminals with cooperation relationships is initialized with the same initial value co0m,n=c>0, among them, the cooperation degree of coalition member i is expressed as(9)coi=CoCkRk∑i∈Ckpikgipik,where ∑i∈Ckpik is the income of all users participating in task k and gi represents the number of sense resources contributed by terminal i to the coalition. The update of cooperation degree among users will be introduced in the third part of Section 4.
In OCF game model, the coalition structure is a set of the total coalitions for accomplishing all tasks and is denoted as∏=C1,C2,…,CN. Each task corresponds to a coalition. Therefore, the size of the coalition structure is fixed, which is equal to N.
When a coalition completes the task, it can be called an effective coalition. The set of effective coalitions is called an effective coalition structure (ECS). In the process of coalition formation, on the one hand, terminal resource allocation needs to maximize the cooperation degree of coalition. On the other hand, it needs to form the coalition with the most significant coalition value. The sense resource allocation problem of all terminals can be formed as the following optimization problem:(10)Uplatform=maxS∑Ck∈∏αCoCk+βVCk,s.t.Rk⊆∪i∈Cksi,qi,j≥dk,j,∀i∈Ck,j∈si,∑i∈CkCi≤Bk,where α,β are scale factors, satisfying α+β=1;α,β∈0,1 and dk,j represents the sense quality requirement of sense resource j in coalition Ck. The goal is constrained by three equations: Rk⊆∪i∈Cksi means that the sense resources provided by the terminal must satisfy sense resources required by sense task k, qi,j≥dk,j,∀i∈Ck,j∈si, means that the quality of the sense resources provided by terminal i is not lower than the quality of sense resources required by the task, and ∑i∈CkCi≤Bk means that cost of coalition Ck to complete the task does not exceed the budget of the task.
Usually, the coalition pays users a certain reward in some form according to its resource allocation. Hence, a reasonable method of income distribution is very crucial to motivate them to join a coalition. In the OCF game model, the return is a finite vector, expressed byP=p1,p2,…,pN. pk is the revenue of coalition Ck. In the proposed OCF game, it is assumed that the total profits of the coalition are affected by the participating degree of coalition members. The coalition will offer rewards to its members. For terminal i∈Ck, the revenue of terminal i from coalition Ck is defined as follows:(11)pik=ωVCk∑j∈sisi,jk∑i∈Ck∑j∈sisi,jk,where si,jk represents the resources provided by terminal i for coalition Ck and ∑j∈sisi,jk represents total resources provided by terminal i for coalition Ck. With the revenue that terminal i obtained from coalition Ck, the terminal i’s total revenue from the platform is(12)Pi=∑Ck∈∏ωVCk∑j∈sisi,jk∑i∈Ck∑j∈sisi,jk−Ci.


## 4. Virtual Terminal Coalition Formation (VTCF) Game

Since one coalition corresponds to one task, one terminal can participate in multiple tasks to make full use of the terminal’s resources. Based on distributed social networks, in this section, the coalition forming methods are proposed, where the terminal’s sense cost, sense quality, and the degree of cooperation between terminals are considered to be used to comprehensively express preference relationships in the process of dynamic coalition formation.


### 4.1. Virtual Terminal

To solve the problem of overlapping coalition formation in an uncertain distributed environment, the concept of the virtual terminal is introduced to reduce the complexity in the overlapping coalition formation process, which is inspired by the concept of virtual auctioneer proposed in [35]. In the actual application of the Internet of things, a terminal usually has multiple sense capabilities. For instance, in the application of air quality monitoring, a terminal can collect CO,NO2, and other gas concentrations at the same time. A terminal with multiple sense capabilities is virtualized into multiple virtual terminals. Each virtual terminal has only one sense capability. For example, terminal i has a sense capability set si=1,2,3, which can be replaced by three virtual terminals Vi=vi1,vi2,vi3, and each virtual terminal has only one sense capability. In this case, each virtual terminal uses distributed mobility to form a coalition structure. A terminal can participate in multiple tasks in the coalition structure, while a virtual terminal can only participate in one task. Therefore, overlapping coalition formation is simplified as the problem of nonoverlapping coalition formation, if the concept of the virtual terminal is adopted.In social networks, each terminal can participate in multiple tasks, which leads to the overlapping coalitions. According to the characteristics of the coalition, the virtual terminal coalition form (VTCF) game is described. The terminal can join multiple coalitions at the same time, while the virtual terminal can only join one coalition. A multisense ability terminal is replaced by multiple virtual terminals with single-sense ability. The virtual terminal participates in the allocation of sense resources. The virtual terminal of terminali is represented by Vi=vi1,vi2,…,vir0. When j∈si, it indicates that the virtual terminal vij has sense resources. A distributed coalition formation model for terminals in social networks to ensure convergence is built, which adopts three mobile strategies, exiting, joining, and switching, to form a virtual terminal coalition structure.


### 4.2. VTCF Algorithm Design

In this section, the resource allocation problem is modeled as the formation of the virtual terminal coalition, in which the virtual terminal participates in the resource allocation process. In the overlapping coalition game, the terminal is willing to cooperate to form a coalition for higher return. The virtual terminal can form a nonoverlapped coalition to complete corresponding tasks. However, each terminal has a variety of sensing capabilities, causing different tasks. As a result, it is natural to use overlapping coalitions to form a game to simulate resource allocation of terminals with multiple sense capabilities.In the OCF game, participants form overlapping coalitions to improve the degree of cooperation and coalition value. To improve the cooperation degree of the system, each cooperative terminal can participate in multiple coalitions by using multiple sense capabilities. In this way, terminals form overlapping coalitions to maximize system utility. The introduction of a single-sense virtual terminal instead of a multisense terminal can effectively reduce the complexity of the overlapping coalition formation process. The coalition formation game for resource allocation is represented by the set ofM,R,U. M is a group of cooperative terminals, and each terminal can be virtualized into multiple virtual terminals. Sense resource owned by all terminals is R=s1,s2,…,sm. For task allocation, each virtual terminal only participates in one task, and the number of coalitions for each terminal participating is up to si. In the coalition formation game model, all terminals work together to increase the value of Uplatform. The game M,R,U can be regarded as a VTCF game. The main feature of the game is that each virtual terminal can join a coalition.As each virtual terminal contributes a kind of sensing resources and can join different coalitions, the set of virtual terminals to form the coalition is described asCk=vm1,…,vnp. The supporter of coalition is denoted as supCk=vij∈Ck|si,jk=1,i∈M,j∈si. Coalition structure ∏ is expressed as ∏=C1,C2,…,CN+1. As some terminals prefer to be idle in later tasks, they may not contribute sense resources. CN+1 is used to express the virtual terminal coalition that does not participate in any task. The number of coalitions is equal to N+1.To evaluate the performance of each finished task, the utility function of the virtual terminal is written as(13)Uk=Bk−∑vij∈supCkci,j.The total cost of all virtual terminals is expressed as∑vij∈supCkci,j. For each coalition structure, the total resource allocation of each terminal i in each coalition does not exceed its own capacity, as shown in the following equation:(14)∑Ck∈∏si,jk<=si,∀vij∈supCk,j∈si.The cooperation degree obtained by the terminal from different tasks is determined by sensing resources invested in the task and cooperation utility completing the task. Considering coalition value and cooperation degree, the system utility is shown as(15)Uplatform=∑Ck∈∏aVCk+βCoCk.It is very vital for the terminal to update a new coalition cooperation degree for maximizing the utility of platform. During the terminal executing the task, the update formula of cooperation degree is given as(16)coqm,n=coq−1m,n+Δcoqm,n,coq−1m,n.The variation of cooperation degree between terminalsm and n can be expressed as(17)Δcoqm,n=comdegreem+condegreen.degreem is the number of terminals connecting to terminal m in the graph.From (9), (16), and (17), the update formula of cooperation degree of terminal can be obtained as(18)coqm,n=coq−1m,n+CoCkgmpmkdegreemRk∑m∈Ckpmk+CoCkgnpnkdegreen×Rk∑n∈Ckpnk,if task complished,coq−1m,n,otherwise.


#### 4.2.1. The Formation of Initial Coalition Structure

Because the terminal is in social network, the theory of graph search can be used to study the generation of initial coalition structure. This section proposes searching for initial coalition members based on SN, as shown in Figure2. Task initiator a1 initiates coalition request and negotiates with its directly connected a2,a3 firstly to form a coalition. If sense resources contributed by negotiated coalition still cannot satisfy sense resources required by the task, then negotiate with a2,a3’s acquaintance a4 to form a coalition. In a large-scale coalition, if the sense cost of existing members is higher than the sense cost of the current member to be negotiated during the negotiation process, the assigned sense resource for the task will be updated, and the process will be repeated until the task requirements are met.Figure 2
SN-based coalition initialization.The social network-based coalition initialization method (SN-CI) is described in Algorithm1. Starting from the task initiator i to search for the virtual terminal set MCk and sense resource set SCk that satisfy sense resource Rk required by task k (Steps 6–12), if the sense resources of task cannot meet the needs of the task, SN is used to find the neighbors of terminal i to complete the task (Steps 13–31), where fstQ means that the first terminal in queue Q is taken out. If sense resource j contributed by terminal i can just be satisfied by neighbor p of terminal i (Step 17), the cost of neighbor p providing resource j is lower than the cost of resource contributed by terminal i. Sense quality requirements are met, and then vij is replaced in the original virtual terminal set SCk with vpj (Step 19). Resource j in the resource set sp of p can no longer be used in other tasks, so it is deleted from the queue (Step 20). The resource set si that previously removed resource j must readd resource j (Step 21); otherwise, resource q is directly added to SCk (Steps 23–27). appendQ,np means adding p’s neighbors to queue Q. The entire social network can be used until all resource requirements of task k are met (Steps 28-29). Finally, a coalition structure containing all virtual terminal coalition sets is obtained.Algorithm 1: SN-CI algorithm.
(1)
Input:G,M,N(2)
Output: coalition structure ∏(3)
∏←∅(4)
fork∈N,i∈Mdo(5)
MCk←∅,SCk←∅;(6)
forj∈sido(7)
ifj∈Rkandqi,j≥dk,jthen(8)
MCk←MCk∪vij;(9)
SCk←SCk∪j;(10)
si←si\j.(11)
end if(12)
end for(13)
Q←ni;(14)
whileQ≠∅andSCk<Rkdo(15)
p←fstQ;(16)
forq∈spdo(17)
if∃j∈SCk,q==j,qp,j≥dk,jthen(18)
ifci,j>cp,qthen(19)
MCk←MCk\vij∪vpj;(20)
sp←sp\q;(21)
si←si∪j.(22)
end if(23)
else ifq∈Rkandqp,q≥dk,qthen(24)
MCk←MCk∪vpq;(25)
SCk←SCk∪q;(26)
si←sp\q.(27)
end if(28)
Q←Q\p;(29)
Q←appendQ,np.(30)
end for(31)
end while(32)
ifSCk==Rkthen(33)
∏←∏∪MCk.(34)
end if(35)
end for(36)
return:∏.Different coalition structures may lead to different system utility. To maximize the utility of the system, it is necessary to find the best coalition structure.


#### 4.2.2. Virtual Terminal Joining, Exiting, and Switching

The critical mechanism of coalition formation is to enable virtual terminals to leave or join the coalition according to specified preferences. In particular, each virtual terminal must compare and rank its potential coalitions based on its preferences. Here, the preference order≻ij for any virtual terminal vij is defined below.Definition 2.
(preference order). For any virtual terminalvij, two coalition structures ∏p,∏q for completing tasks are given. For any virtual terminal vij, ∏p≻ij∏q indicates that vij prefers ∏p to ∏q. Since the preference order depends on the system utility, the preference order for the virtual terminal vij is defined as follows:(19)∏p≻ij∏q⇔U∏p>U∏q.
According to Definition2, the utility of the coalition structure increases, and the virtual terminal vij will choose this coalition structure. This preference order guarantees a comprehensive increment in the degree of cooperation and platform utility during the formation of the coalition. Using our proposed preference order, the coalition structure can reach stability with a limited number of iterations during its coalition formation.
During the formation of coalition, the virtual terminal decides to join or leave the coalition according to the order of preference. Three-movement rules are defined for possible movement directions of the virtual terminal. Firstly, the virtual terminal exits from the current coalition and enters an idle coalition. Secondly, the virtual terminal leaves an idle coalition and enters any other coalition. Thirdly, the virtual terminal transfers from its existing coalition to a nonidle coalition. Virtual terminals can form different coalition structures with these operations.Definition 3.
(exiting rule). It is assumed that the virtual terminalsvij∈Cm and Cm∈∏p. If ∏q≻ij∏p, then vij leaves coalition Cm, and then coalition structure ∏p becomes the coalition structure ∏q. The new coalition structure is ∏q=∏p\Cm,Ct+1∪Cm\vij∪Ct+1∪vij.
According to Definition3, if system utility of this newly formed coalition structure is better than that of current coalition structure, the virtual terminal vij leaves the current coalition Cm to join the idle coalition Ct+1, and ∏p becomes ∏q. This situation occurs because of virtual terminal vij, which may have a negative coalition effect. Therefore, vij may be more willing to leave coalition Cm to avoid negative benefits. That is, vij is unfriendly, and no other terminal is willing to form a coalition with it.Definition 4.
(joining rule). It is assumed that the virtual terminalsvij∈Ct+1 and Cn∈∏p. If ∏q≻ij∏p and vij join coalition Cn, the coalition structure ∏p becomes ∏q, and the new coalition structure is ∏q=∏p\Cn,Ct+1∪Cn∪vij∪Ct+1\vij.
Based on Definition4, vij does not initially belong to coalition Cn in the coalition structure ∏p. It is assumed that the virtual terminal vij, which does not participate in the sensing task, leaves the current idle coalition Ct+1 and joins coalition Cn. The current coalition structure ∏p becomes a new coalition structure ∏q. If the coalition structure ∏q is better than ∏p for virtual terminal vij, according to equation (19), vij joins the coalition and current coalition structure ∏p is replaced by ∏q. Only when the terminal’s actions improve the effectiveness of the coalition structure will the virtual terminal join a new coalition.Definition 5.
(switching rule). It is assumed that the virtual terminalvij∈Cm and ∏p. If ∏q≻ij∏p, vij is transferred from coalition Cm to coalition Cn and coalition structure ∏p becomes ∏q. The new coalition structure is ∏q=∏p\Cm,Cn∪Cm\vij∪Cn∪vij.
According to Definition5, when a new coalition structure is better than the current coalition structure, vij is transferred from the coalition where it was to the new coalition. Switching rules balance scale of different coalitions and improve the utilization of resources. During the formation of the coalition structure, one task can be selected by many virtual terminals, and one virtual terminal can select multiple tasks. When the virtual terminal finds that it can improve its system utility by transferring from coalition Cm to Cn, it will execute the switch rules. In this way, Cn can allocate their sense resources to different coalitions autonomously, and the utility of the system will be improved.Definition 6.
If, for anyvij∈M, there are vij∈Cm and vij∉Cn, where vij will not leave coalition Cm and will not join other coalitions, then the coalition structure ∏ of a group of virtual terminals is stable. That is, Nash equilibrium is reached.
According to Definition6, for a virtual terminal vij∈Cm in a stable coalition structure, it will not leave any coalition and will not join any new coalition. Therefore, all virtual terminals will stay in the current coalition, and no changes will be made.


#### 4.2.3. VTCF Algorithm

To achieve a stable coalition structure, the VTCF algorithm is proposed, as shown in Algorithm2, which is a distributed algorithm and is executed by each vij∈M. In Algorithm 2, vij∈M forms a coalition according to three moving rules. At the beginning of each iteration, vij∈M is randomly selected from feasible coalitions. Assuming that vij leaves current coalition Cm and forms a new coalition structure ∏Quit (Step 7), judge whether current coalition structure ∏Quit is a valid coalition structure (Step 8). If so, using vij based on equations (8) and (15), calculate the system utility value of coalition structure ∏Quit (Step 9). Similarly, the joining rule and the switching rule can generate a potential new coalition structure. The values of coalition structures ∏Join and ∏Transfer are calculated by equations (8)) and (15) (Steps 15 and 22), respectively. If the coalition structure produced by the roll-out operation is better than the current coalition structure, the coalition structure is updated (Step 11). Similarly, vij considers joining rules (Step 14) as well as switching rules (Step 21) and updates the system utility value of the coalition structure. When a task is completed, the degree of cooperation is updating between terminals (Step 27) through equation (18). vij repeats the coalition formation process until all vij will not deviate from current coalition or join other new coalitions (Step 29). In other words, the process converges to a stable coalition structure.Algorithm 2: VTCF algorithm.
(1)
Initialization stage:(2)
Virtual terminalvij forms an initial coalition based on Algorithm 1(3)
Coalition formation Stage:(4)
repeat(5)
fork∈Ndo(6)
vij randomly selects from idle coalition;(7)
∏Quit=∏\Cm,Ct+1∪Cm\vij∪Ct+1∪vij;(8)
if∏Quit is a ECS then(9)
calculatesU∏Quit;(10)
if∏Quit≻ij∏then(11)
∏=∏Quit;U∏=∏Quit;(12)
end if(13)
end if(14)
if∏Join is a ECS then(15)
calculatesU∏Join;(16)
if∏Join≻ij∏then(17)
∏=∏Join;UΠ=U∏Join;(18)
end if(19)
end if(20)
∏Transfer=∏\Cm,Cn∪Cm\vij∪Cn∪vij;(21)
if∏Transfer is a ECS then(22)
calculatesU∏Transfer;(23)
if∏Transfer≻ij∏then(24)
∏=∏Transfer;U∏=U∏Transfer;(25)
end if(26)
end if(27)
update cooperation degree according to equation (18);(28)
end for(29)
until the coalition converges to the final Nash-stableTheorem 1.
After a finite number of iterations, the proposed VTCF algorithm converges to a stable coalition structure.Proof.
Assume that the numbers of terminalsM and sense resource types r0 owned by terminals are limited and there are structural restrictions among terminals. The number of possible coalition structures must be less than 2Mr0. When the VTCF algorithm is executed, the coalition formation process involves a series of movements of the virtual terminal, which leads to the generation of a series of coalition structures ∏0,∏1,…,∏r, where r is the total number of movements of virtual terminal. According to equations (10) and (15), a new coalition structure with higher system utility is formed after each virtual terminal moves. In addition, the number of possible coalition structures is limited. Therefore, r is a finite number. The contradiction proof method is used to prove that if ∏r is final coalition structure after last virtual terminal movement, then it must be stable. Assuming that ∏r is unstable, according to Definition 6, the existence of vij∈M causes vij to deviate from its current coalition or join a new coalition. Therefore, according to the proposed virtual terminal coalition formation algorithm, vij will join, exit, or transfer operations, and coalition structure ∏r will become a new coalition structure. This contradicts the fact that ∏r is the final coalition structure. Therefore, ∏r is a stable coalition structure. Therefore, after a limited number of iterations, the proposed VTCF algorithm enables vij to achieve a stable coalition structure.
In the coalition formation process of Algorithm2, each vij seeks to improve value of coalition structure. After each iteration, the movement of vij leads to a new coalition structure ∏. Therefore, whenever the coalition structure ∏ changes, more excellent system utility is obtained, and vij can adaptively change their cooperation strategy to form a stable coalition structure.


## 4.1. Virtual Terminal

To solve the problem of overlapping coalition formation in an uncertain distributed environment, the concept of the virtual terminal is introduced to reduce the complexity in the overlapping coalition formation process, which is inspired by the concept of virtual auctioneer proposed in [35]. In the actual application of the Internet of things, a terminal usually has multiple sense capabilities. For instance, in the application of air quality monitoring, a terminal can collect CO,NO2, and other gas concentrations at the same time. A terminal with multiple sense capabilities is virtualized into multiple virtual terminals. Each virtual terminal has only one sense capability. For example, terminal i has a sense capability set si=1,2,3, which can be replaced by three virtual terminals Vi=vi1,vi2,vi3, and each virtual terminal has only one sense capability. In this case, each virtual terminal uses distributed mobility to form a coalition structure. A terminal can participate in multiple tasks in the coalition structure, while a virtual terminal can only participate in one task. Therefore, overlapping coalition formation is simplified as the problem of nonoverlapping coalition formation, if the concept of the virtual terminal is adopted.In social networks, each terminal can participate in multiple tasks, which leads to the overlapping coalitions. According to the characteristics of the coalition, the virtual terminal coalition form (VTCF) game is described. The terminal can join multiple coalitions at the same time, while the virtual terminal can only join one coalition. A multisense ability terminal is replaced by multiple virtual terminals with single-sense ability. The virtual terminal participates in the allocation of sense resources. The virtual terminal of terminali is represented by Vi=vi1,vi2,…,vir0. When j∈si, it indicates that the virtual terminal vij has sense resources. A distributed coalition formation model for terminals in social networks to ensure convergence is built, which adopts three mobile strategies, exiting, joining, and switching, to form a virtual terminal coalition structure.


## 4.2. VTCF Algorithm Design

In this section, the resource allocation problem is modeled as the formation of the virtual terminal coalition, in which the virtual terminal participates in the resource allocation process. In the overlapping coalition game, the terminal is willing to cooperate to form a coalition for higher return. The virtual terminal can form a nonoverlapped coalition to complete corresponding tasks. However, each terminal has a variety of sensing capabilities, causing different tasks. As a result, it is natural to use overlapping coalitions to form a game to simulate resource allocation of terminals with multiple sense capabilities.In the OCF game, participants form overlapping coalitions to improve the degree of cooperation and coalition value. To improve the cooperation degree of the system, each cooperative terminal can participate in multiple coalitions by using multiple sense capabilities. In this way, terminals form overlapping coalitions to maximize system utility. The introduction of a single-sense virtual terminal instead of a multisense terminal can effectively reduce the complexity of the overlapping coalition formation process. The coalition formation game for resource allocation is represented by the set ofM,R,U. M is a group of cooperative terminals, and each terminal can be virtualized into multiple virtual terminals. Sense resource owned by all terminals is R=s1,s2,…,sm. For task allocation, each virtual terminal only participates in one task, and the number of coalitions for each terminal participating is up to si. In the coalition formation game model, all terminals work together to increase the value of Uplatform. The game M,R,U can be regarded as a VTCF game. The main feature of the game is that each virtual terminal can join a coalition.As each virtual terminal contributes a kind of sensing resources and can join different coalitions, the set of virtual terminals to form the coalition is described asCk=vm1,…,vnp. The supporter of coalition is denoted as supCk=vij∈Ck|si,jk=1,i∈M,j∈si. Coalition structure ∏ is expressed as ∏=C1,C2,…,CN+1. As some terminals prefer to be idle in later tasks, they may not contribute sense resources. CN+1 is used to express the virtual terminal coalition that does not participate in any task. The number of coalitions is equal to N+1.To evaluate the performance of each finished task, the utility function of the virtual terminal is written as(13)Uk=Bk−∑vij∈supCkci,j.The total cost of all virtual terminals is expressed as∑vij∈supCkci,j. For each coalition structure, the total resource allocation of each terminal i in each coalition does not exceed its own capacity, as shown in the following equation:(14)∑Ck∈∏si,jk<=si,∀vij∈supCk,j∈si.The cooperation degree obtained by the terminal from different tasks is determined by sensing resources invested in the task and cooperation utility completing the task. Considering coalition value and cooperation degree, the system utility is shown as(15)Uplatform=∑Ck∈∏aVCk+βCoCk.It is very vital for the terminal to update a new coalition cooperation degree for maximizing the utility of platform. During the terminal executing the task, the update formula of cooperation degree is given as(16)coqm,n=coq−1m,n+Δcoqm,n,coq−1m,n.The variation of cooperation degree between terminalsm and n can be expressed as(17)Δcoqm,n=comdegreem+condegreen.degreem is the number of terminals connecting to terminal m in the graph.From (9), (16), and (17), the update formula of cooperation degree of terminal can be obtained as(18)coqm,n=coq−1m,n+CoCkgmpmkdegreemRk∑m∈Ckpmk+CoCkgnpnkdegreen×Rk∑n∈Ckpnk,if task complished,coq−1m,n,otherwise.


### 4.2.1. The Formation of Initial Coalition Structure

Because the terminal is in social network, the theory of graph search can be used to study the generation of initial coalition structure. This section proposes searching for initial coalition members based on SN, as shown in Figure2. Task initiator a1 initiates coalition request and negotiates with its directly connected a2,a3 firstly to form a coalition. If sense resources contributed by negotiated coalition still cannot satisfy sense resources required by the task, then negotiate with a2,a3’s acquaintance a4 to form a coalition. In a large-scale coalition, if the sense cost of existing members is higher than the sense cost of the current member to be negotiated during the negotiation process, the assigned sense resource for the task will be updated, and the process will be repeated until the task requirements are met.Figure 2
SN-based coalition initialization.The social network-based coalition initialization method (SN-CI) is described in Algorithm1. Starting from the task initiator i to search for the virtual terminal set MCk and sense resource set SCk that satisfy sense resource Rk required by task k (Steps 6–12), if the sense resources of task cannot meet the needs of the task, SN is used to find the neighbors of terminal i to complete the task (Steps 13–31), where fstQ means that the first terminal in queue Q is taken out. If sense resource j contributed by terminal i can just be satisfied by neighbor p of terminal i (Step 17), the cost of neighbor p providing resource j is lower than the cost of resource contributed by terminal i. Sense quality requirements are met, and then vij is replaced in the original virtual terminal set SCk with vpj (Step 19). Resource j in the resource set sp of p can no longer be used in other tasks, so it is deleted from the queue (Step 20). The resource set si that previously removed resource j must readd resource j (Step 21); otherwise, resource q is directly added to SCk (Steps 23–27). appendQ,np means adding p’s neighbors to queue Q. The entire social network can be used until all resource requirements of task k are met (Steps 28-29). Finally, a coalition structure containing all virtual terminal coalition sets is obtained.Algorithm 1: SN-CI algorithm.
(1)
Input:G,M,N(2)
Output: coalition structure ∏(3)
∏←∅(4)
fork∈N,i∈Mdo(5)
MCk←∅,SCk←∅;(6)
forj∈sido(7)
ifj∈Rkandqi,j≥dk,jthen(8)
MCk←MCk∪vij;(9)
SCk←SCk∪j;(10)
si←si\j.(11)
end if(12)
end for(13)
Q←ni;(14)
whileQ≠∅andSCk<Rkdo(15)
p←fstQ;(16)
forq∈spdo(17)
if∃j∈SCk,q==j,qp,j≥dk,jthen(18)
ifci,j>cp,qthen(19)
MCk←MCk\vij∪vpj;(20)
sp←sp\q;(21)
si←si∪j.(22)
end if(23)
else ifq∈Rkandqp,q≥dk,qthen(24)
MCk←MCk∪vpq;(25)
SCk←SCk∪q;(26)
si←sp\q.(27)
end if(28)
Q←Q\p;(29)
Q←appendQ,np.(30)
end for(31)
end while(32)
ifSCk==Rkthen(33)
∏←∏∪MCk.(34)
end if(35)
end for(36)
return:∏.Different coalition structures may lead to different system utility. To maximize the utility of the system, it is necessary to find the best coalition structure.


### 4.2.2. Virtual Terminal Joining, Exiting, and Switching

The critical mechanism of coalition formation is to enable virtual terminals to leave or join the coalition according to specified preferences. In particular, each virtual terminal must compare and rank its potential coalitions based on its preferences. Here, the preference order≻ij for any virtual terminal vij is defined below.Definition 2.
(preference order). For any virtual terminalvij, two coalition structures ∏p,∏q for completing tasks are given. For any virtual terminal vij, ∏p≻ij∏q indicates that vij prefers ∏p to ∏q. Since the preference order depends on the system utility, the preference order for the virtual terminal vij is defined as follows:(19)∏p≻ij∏q⇔U∏p>U∏q.
According to Definition2, the utility of the coalition structure increases, and the virtual terminal vij will choose this coalition structure. This preference order guarantees a comprehensive increment in the degree of cooperation and platform utility during the formation of the coalition. Using our proposed preference order, the coalition structure can reach stability with a limited number of iterations during its coalition formation.
During the formation of coalition, the virtual terminal decides to join or leave the coalition according to the order of preference. Three-movement rules are defined for possible movement directions of the virtual terminal. Firstly, the virtual terminal exits from the current coalition and enters an idle coalition. Secondly, the virtual terminal leaves an idle coalition and enters any other coalition. Thirdly, the virtual terminal transfers from its existing coalition to a nonidle coalition. Virtual terminals can form different coalition structures with these operations.Definition 3.
(exiting rule). It is assumed that the virtual terminalsvij∈Cm and Cm∈∏p. If ∏q≻ij∏p, then vij leaves coalition Cm, and then coalition structure ∏p becomes the coalition structure ∏q. The new coalition structure is ∏q=∏p\Cm,Ct+1∪Cm\vij∪Ct+1∪vij.
According to Definition3, if system utility of this newly formed coalition structure is better than that of current coalition structure, the virtual terminal vij leaves the current coalition Cm to join the idle coalition Ct+1, and ∏p becomes ∏q. This situation occurs because of virtual terminal vij, which may have a negative coalition effect. Therefore, vij may be more willing to leave coalition Cm to avoid negative benefits. That is, vij is unfriendly, and no other terminal is willing to form a coalition with it.Definition 4.
(joining rule). It is assumed that the virtual terminalsvij∈Ct+1 and Cn∈∏p. If ∏q≻ij∏p and vij join coalition Cn, the coalition structure ∏p becomes ∏q, and the new coalition structure is ∏q=∏p\Cn,Ct+1∪Cn∪vij∪Ct+1\vij.
Based on Definition4, vij does not initially belong to coalition Cn in the coalition structure ∏p. It is assumed that the virtual terminal vij, which does not participate in the sensing task, leaves the current idle coalition Ct+1 and joins coalition Cn. The current coalition structure ∏p becomes a new coalition structure ∏q. If the coalition structure ∏q is better than ∏p for virtual terminal vij, according to equation (19), vij joins the coalition and current coalition structure ∏p is replaced by ∏q. Only when the terminal’s actions improve the effectiveness of the coalition structure will the virtual terminal join a new coalition.Definition 5.
(switching rule). It is assumed that the virtual terminalvij∈Cm and ∏p. If ∏q≻ij∏p, vij is transferred from coalition Cm to coalition Cn and coalition structure ∏p becomes ∏q. The new coalition structure is ∏q=∏p\Cm,Cn∪Cm\vij∪Cn∪vij.
According to Definition5, when a new coalition structure is better than the current coalition structure, vij is transferred from the coalition where it was to the new coalition. Switching rules balance scale of different coalitions and improve the utilization of resources. During the formation of the coalition structure, one task can be selected by many virtual terminals, and one virtual terminal can select multiple tasks. When the virtual terminal finds that it can improve its system utility by transferring from coalition Cm to Cn, it will execute the switch rules. In this way, Cn can allocate their sense resources to different coalitions autonomously, and the utility of the system will be improved.Definition 6.
If, for anyvij∈M, there are vij∈Cm and vij∉Cn, where vij will not leave coalition Cm and will not join other coalitions, then the coalition structure ∏ of a group of virtual terminals is stable. That is, Nash equilibrium is reached.
According to Definition6, for a virtual terminal vij∈Cm in a stable coalition structure, it will not leave any coalition and will not join any new coalition. Therefore, all virtual terminals will stay in the current coalition, and no changes will be made.


### 4.2.3. VTCF Algorithm

To achieve a stable coalition structure, the VTCF algorithm is proposed, as shown in Algorithm2, which is a distributed algorithm and is executed by each vij∈M. In Algorithm 2, vij∈M forms a coalition according to three moving rules. At the beginning of each iteration, vij∈M is randomly selected from feasible coalitions. Assuming that vij leaves current coalition Cm and forms a new coalition structure ∏Quit (Step 7), judge whether current coalition structure ∏Quit is a valid coalition structure (Step 8). If so, using vij based on equations (8) and (15), calculate the system utility value of coalition structure ∏Quit (Step 9). Similarly, the joining rule and the switching rule can generate a potential new coalition structure. The values of coalition structures ∏Join and ∏Transfer are calculated by equations (8)) and (15) (Steps 15 and 22), respectively. If the coalition structure produced by the roll-out operation is better than the current coalition structure, the coalition structure is updated (Step 11). Similarly, vij considers joining rules (Step 14) as well as switching rules (Step 21) and updates the system utility value of the coalition structure. When a task is completed, the degree of cooperation is updating between terminals (Step 27) through equation (18). vij repeats the coalition formation process until all vij will not deviate from current coalition or join other new coalitions (Step 29). In other words, the process converges to a stable coalition structure.Algorithm 2: VTCF algorithm.
(1)
Initialization stage:(2)
Virtual terminalvij forms an initial coalition based on Algorithm 1(3)
Coalition formation Stage:(4)
repeat(5)
fork∈Ndo(6)
vij randomly selects from idle coalition;(7)
∏Quit=∏\Cm,Ct+1∪Cm\vij∪Ct+1∪vij;(8)
if∏Quit is a ECS then(9)
calculatesU∏Quit;(10)
if∏Quit≻ij∏then(11)
∏=∏Quit;U∏=∏Quit;(12)
end if(13)
end if(14)
if∏Join is a ECS then(15)
calculatesU∏Join;(16)
if∏Join≻ij∏then(17)
∏=∏Join;UΠ=U∏Join;(18)
end if(19)
end if(20)
∏Transfer=∏\Cm,Cn∪Cm\vij∪Cn∪vij;(21)
if∏Transfer is a ECS then(22)
calculatesU∏Transfer;(23)
if∏Transfer≻ij∏then(24)
∏=∏Transfer;U∏=U∏Transfer;(25)
end if(26)
end if(27)
update cooperation degree according to equation (18);(28)
end for(29)
until the coalition converges to the final Nash-stableTheorem 1.
After a finite number of iterations, the proposed VTCF algorithm converges to a stable coalition structure.Proof.
Assume that the numbers of terminalsM and sense resource types r0 owned by terminals are limited and there are structural restrictions among terminals. The number of possible coalition structures must be less than 2Mr0. When the VTCF algorithm is executed, the coalition formation process involves a series of movements of the virtual terminal, which leads to the generation of a series of coalition structures ∏0,∏1,…,∏r, where r is the total number of movements of virtual terminal. According to equations (10) and (15), a new coalition structure with higher system utility is formed after each virtual terminal moves. In addition, the number of possible coalition structures is limited. Therefore, r is a finite number. The contradiction proof method is used to prove that if ∏r is final coalition structure after last virtual terminal movement, then it must be stable. Assuming that ∏r is unstable, according to Definition 6, the existence of vij∈M causes vij to deviate from its current coalition or join a new coalition. Therefore, according to the proposed virtual terminal coalition formation algorithm, vij will join, exit, or transfer operations, and coalition structure ∏r will become a new coalition structure. This contradicts the fact that ∏r is the final coalition structure. Therefore, ∏r is a stable coalition structure. Therefore, after a limited number of iterations, the proposed VTCF algorithm enables vij to achieve a stable coalition structure.
In the coalition formation process of Algorithm2, each vij seeks to improve value of coalition structure. After each iteration, the movement of vij leads to a new coalition structure ∏. Therefore, whenever the coalition structure ∏ changes, more excellent system utility is obtained, and vij can adaptively change their cooperation strategy to form a stable coalition structure.


## 4.2.1. The Formation of Initial Coalition Structure

Because the terminal is in social network, the theory of graph search can be used to study the generation of initial coalition structure. This section proposes searching for initial coalition members based on SN, as shown in Figure2. Task initiator a1 initiates coalition request and negotiates with its directly connected a2,a3 firstly to form a coalition. If sense resources contributed by negotiated coalition still cannot satisfy sense resources required by the task, then negotiate with a2,a3’s acquaintance a4 to form a coalition. In a large-scale coalition, if the sense cost of existing members is higher than the sense cost of the current member to be negotiated during the negotiation process, the assigned sense resource for the task will be updated, and the process will be repeated until the task requirements are met.Figure 2
SN-based coalition initialization.The social network-based coalition initialization method (SN-CI) is described in Algorithm1. Starting from the task initiator i to search for the virtual terminal set MCk and sense resource set SCk that satisfy sense resource Rk required by task k (Steps 6–12), if the sense resources of task cannot meet the needs of the task, SN is used to find the neighbors of terminal i to complete the task (Steps 13–31), where fstQ means that the first terminal in queue Q is taken out. If sense resource j contributed by terminal i can just be satisfied by neighbor p of terminal i (Step 17), the cost of neighbor p providing resource j is lower than the cost of resource contributed by terminal i. Sense quality requirements are met, and then vij is replaced in the original virtual terminal set SCk with vpj (Step 19). Resource j in the resource set sp of p can no longer be used in other tasks, so it is deleted from the queue (Step 20). The resource set si that previously removed resource j must readd resource j (Step 21); otherwise, resource q is directly added to SCk (Steps 23–27). appendQ,np means adding p’s neighbors to queue Q. The entire social network can be used until all resource requirements of task k are met (Steps 28-29). Finally, a coalition structure containing all virtual terminal coalition sets is obtained.Algorithm 1: SN-CI algorithm.
(1)
Input:G,M,N(2)
Output: coalition structure ∏(3)
∏←∅(4)
fork∈N,i∈Mdo(5)
MCk←∅,SCk←∅;(6)
forj∈sido(7)
ifj∈Rkandqi,j≥dk,jthen(8)
MCk←MCk∪vij;(9)
SCk←SCk∪j;(10)
si←si\j.(11)
end if(12)
end for(13)
Q←ni;(14)
whileQ≠∅andSCk<Rkdo(15)
p←fstQ;(16)
forq∈spdo(17)
if∃j∈SCk,q==j,qp,j≥dk,jthen(18)
ifci,j>cp,qthen(19)
MCk←MCk\vij∪vpj;(20)
sp←sp\q;(21)
si←si∪j.(22)
end if(23)
else ifq∈Rkandqp,q≥dk,qthen(24)
MCk←MCk∪vpq;(25)
SCk←SCk∪q;(26)
si←sp\q.(27)
end if(28)
Q←Q\p;(29)
Q←appendQ,np.(30)
end for(31)
end while(32)
ifSCk==Rkthen(33)
∏←∏∪MCk.(34)
end if(35)
end for(36)
return:∏.Different coalition structures may lead to different system utility. To maximize the utility of the system, it is necessary to find the best coalition structure.


## 4.2.2. Virtual Terminal Joining, Exiting, and Switching

The critical mechanism of coalition formation is to enable virtual terminals to leave or join the coalition according to specified preferences. In particular, each virtual terminal must compare and rank its potential coalitions based on its preferences. Here, the preference order≻ij for any virtual terminal vij is defined below.Definition 2.
(preference order). For any virtual terminalvij, two coalition structures ∏p,∏q for completing tasks are given. For any virtual terminal vij, ∏p≻ij∏q indicates that vij prefers ∏p to ∏q. Since the preference order depends on the system utility, the preference order for the virtual terminal vij is defined as follows:(19)∏p≻ij∏q⇔U∏p>U∏q.
According to Definition2, the utility of the coalition structure increases, and the virtual terminal vij will choose this coalition structure. This preference order guarantees a comprehensive increment in the degree of cooperation and platform utility during the formation of the coalition. Using our proposed preference order, the coalition structure can reach stability with a limited number of iterations during its coalition formation.
During the formation of coalition, the virtual terminal decides to join or leave the coalition according to the order of preference. Three-movement rules are defined for possible movement directions of the virtual terminal. Firstly, the virtual terminal exits from the current coalition and enters an idle coalition. Secondly, the virtual terminal leaves an idle coalition and enters any other coalition. Thirdly, the virtual terminal transfers from its existing coalition to a nonidle coalition. Virtual terminals can form different coalition structures with these operations.Definition 3.
(exiting rule). It is assumed that the virtual terminalsvij∈Cm and Cm∈∏p. If ∏q≻ij∏p, then vij leaves coalition Cm, and then coalition structure ∏p becomes the coalition structure ∏q. The new coalition structure is ∏q=∏p\Cm,Ct+1∪Cm\vij∪Ct+1∪vij.
According to Definition3, if system utility of this newly formed coalition structure is better than that of current coalition structure, the virtual terminal vij leaves the current coalition Cm to join the idle coalition Ct+1, and ∏p becomes ∏q. This situation occurs because of virtual terminal vij, which may have a negative coalition effect. Therefore, vij may be more willing to leave coalition Cm to avoid negative benefits. That is, vij is unfriendly, and no other terminal is willing to form a coalition with it.Definition 4.
(joining rule). It is assumed that the virtual terminalsvij∈Ct+1 and Cn∈∏p. If ∏q≻ij∏p and vij join coalition Cn, the coalition structure ∏p becomes ∏q, and the new coalition structure is ∏q=∏p\Cn,Ct+1∪Cn∪vij∪Ct+1\vij.
Based on Definition4, vij does not initially belong to coalition Cn in the coalition structure ∏p. It is assumed that the virtual terminal vij, which does not participate in the sensing task, leaves the current idle coalition Ct+1 and joins coalition Cn. The current coalition structure ∏p becomes a new coalition structure ∏q. If the coalition structure ∏q is better than ∏p for virtual terminal vij, according to equation (19), vij joins the coalition and current coalition structure ∏p is replaced by ∏q. Only when the terminal’s actions improve the effectiveness of the coalition structure will the virtual terminal join a new coalition.Definition 5.
(switching rule). It is assumed that the virtual terminalvij∈Cm and ∏p. If ∏q≻ij∏p, vij is transferred from coalition Cm to coalition Cn and coalition structure ∏p becomes ∏q. The new coalition structure is ∏q=∏p\Cm,Cn∪Cm\vij∪Cn∪vij.
According to Definition5, when a new coalition structure is better than the current coalition structure, vij is transferred from the coalition where it was to the new coalition. Switching rules balance scale of different coalitions and improve the utilization of resources. During the formation of the coalition structure, one task can be selected by many virtual terminals, and one virtual terminal can select multiple tasks. When the virtual terminal finds that it can improve its system utility by transferring from coalition Cm to Cn, it will execute the switch rules. In this way, Cn can allocate their sense resources to different coalitions autonomously, and the utility of the system will be improved.Definition 6.
If, for anyvij∈M, there are vij∈Cm and vij∉Cn, where vij will not leave coalition Cm and will not join other coalitions, then the coalition structure ∏ of a group of virtual terminals is stable. That is, Nash equilibrium is reached.
According to Definition6, for a virtual terminal vij∈Cm in a stable coalition structure, it will not leave any coalition and will not join any new coalition. Therefore, all virtual terminals will stay in the current coalition, and no changes will be made.


## 4.2.3. VTCF Algorithm

To achieve a stable coalition structure, the VTCF algorithm is proposed, as shown in Algorithm2, which is a distributed algorithm and is executed by each vij∈M. In Algorithm 2, vij∈M forms a coalition according to three moving rules. At the beginning of each iteration, vij∈M is randomly selected from feasible coalitions. Assuming that vij leaves current coalition Cm and forms a new coalition structure ∏Quit (Step 7), judge whether current coalition structure ∏Quit is a valid coalition structure (Step 8). If so, using vij based on equations (8) and (15), calculate the system utility value of coalition structure ∏Quit (Step 9). Similarly, the joining rule and the switching rule can generate a potential new coalition structure. The values of coalition structures ∏Join and ∏Transfer are calculated by equations (8)) and (15) (Steps 15 and 22), respectively. If the coalition structure produced by the roll-out operation is better than the current coalition structure, the coalition structure is updated (Step 11). Similarly, vij considers joining rules (Step 14) as well as switching rules (Step 21) and updates the system utility value of the coalition structure. When a task is completed, the degree of cooperation is updating between terminals (Step 27) through equation (18). vij repeats the coalition formation process until all vij will not deviate from current coalition or join other new coalitions (Step 29). In other words, the process converges to a stable coalition structure.Algorithm 2: VTCF algorithm.
(1)
Initialization stage:(2)
Virtual terminalvij forms an initial coalition based on Algorithm 1(3)
Coalition formation Stage:(4)
repeat(5)
fork∈Ndo(6)
vij randomly selects from idle coalition;(7)
∏Quit=∏\Cm,Ct+1∪Cm\vij∪Ct+1∪vij;(8)
if∏Quit is a ECS then(9)
calculatesU∏Quit;(10)
if∏Quit≻ij∏then(11)
∏=∏Quit;U∏=∏Quit;(12)
end if(13)
end if(14)
if∏Join is a ECS then(15)
calculatesU∏Join;(16)
if∏Join≻ij∏then(17)
∏=∏Join;UΠ=U∏Join;(18)
end if(19)
end if(20)
∏Transfer=∏\Cm,Cn∪Cm\vij∪Cn∪vij;(21)
if∏Transfer is a ECS then(22)
calculatesU∏Transfer;(23)
if∏Transfer≻ij∏then(24)
∏=∏Transfer;U∏=U∏Transfer;(25)
end if(26)
end if(27)
update cooperation degree according to equation (18);(28)
end for(29)
until the coalition converges to the final Nash-stableTheorem 1.
After a finite number of iterations, the proposed VTCF algorithm converges to a stable coalition structure.Proof.
Assume that the numbers of terminalsM and sense resource types r0 owned by terminals are limited and there are structural restrictions among terminals. The number of possible coalition structures must be less than 2Mr0. When the VTCF algorithm is executed, the coalition formation process involves a series of movements of the virtual terminal, which leads to the generation of a series of coalition structures ∏0,∏1,…,∏r, where r is the total number of movements of virtual terminal. According to equations (10) and (15), a new coalition structure with higher system utility is formed after each virtual terminal moves. In addition, the number of possible coalition structures is limited. Therefore, r is a finite number. The contradiction proof method is used to prove that if ∏r is final coalition structure after last virtual terminal movement, then it must be stable. Assuming that ∏r is unstable, according to Definition 6, the existence of vij∈M causes vij to deviate from its current coalition or join a new coalition. Therefore, according to the proposed virtual terminal coalition formation algorithm, vij will join, exit, or transfer operations, and coalition structure ∏r will become a new coalition structure. This contradicts the fact that ∏r is the final coalition structure. Therefore, ∏r is a stable coalition structure. Therefore, after a limited number of iterations, the proposed VTCF algorithm enables vij to achieve a stable coalition structure.
In the coalition formation process of Algorithm2, each vij seeks to improve value of coalition structure. After each iteration, the movement of vij leads to a new coalition structure ∏. Therefore, whenever the coalition structure ∏ changes, more excellent system utility is obtained, and vij can adaptively change their cooperation strategy to form a stable coalition structure.


## 5. Numerical Simulations

Task allocation using the VTCF algorithm in a social network environment is simulated. The simulated results of the proposed algorithm are compared with coalition forming based on random initialization, SN-CI, and centralized case [27], respectively. In random allocation, users only randomly allocate their resources to tasks that they can complete. In the case of SN-CI, the user allocates resources according to the allocation method of Algorithm 1. Finally, the platform utility and the cost of tasks are evaluated in the MCS system. The simulation parameters are shown in Table 1. All curves are generated based on an average of 1000 instances.Table 1
Simulation parameters.
ParametersValueTypes of sense resources included in the system:l10Terminal contains the types of sense resources:r03Scale factor:a,β[0, 1]Terminali provides the quality of j resources: qi,j[0, 1]Budget for taskk: Bk[3, 5]Initial cooperation degree:c3Energy coefficient [36]: κ5×10−27CPU capability of each terminal:f1–2.8 (GHz)In Figure3, the abscissa is the number of effective iterations, which indicates that a user successfully joins a coalition. It can be seen that the utility of platform becomes stable with the increment of effective iteration numbers based on the VTCF algorithm. Convergence time becomes shorter as the number of users is reduced. The utility value becomes larger when the number of users increases, which indicates that much more users participate in coalition forming. The utility of platform for the VTCF algorithm based on SN and random initialization coalition methods to generate a stable coalition structure are compared in Figure 4. It can be observed that the utility of the platform will increase as the number of iterations increases and tends to be stable. It shows that the initialization coalition method of SN converges faster than random initialization coalition method, and it can accelerate the formation of coalitions.Figure 3
The relationship between total number of effective iterations in the VTCF algorithm and system utility withN=10.Figure 4
The impact of different coalition initialization algorithms on system utility withM=30,N=10.Figure5 shows the influence of parameter α on the system utility. The system utility firstly increases with the increment of α and reaches a peak value with α=0.4−0.6, which can be regarded as a good combination of cooperation degree and coalition value, and then it decreases as α further increases. Figure 6 shows the effect of the number of tasks on the utility of the platform with α=0.5. By using the VTCF algorithm, the platform utility will increase as the number of tasks increases with M=30. Moreover, the performance of the proposed algorithm is close to that of centralized case and much better than the results of random and SN initialization coalition forming methods.Figure 5
Impact of parameterα on platform utility with N=10.Figure 6
Impact of the number of tasks on platform utility withM=30.The relationship between the total sense cost and the number of tasks is shown in Figure7. It can be seen that the whole sense cost of platform will increase with the increment of the number of tasks. At the same time, the cost of tasks by using the VTCF algorithm is close to that of centralized case, which indicates that the proposed algorithm consumes less battery energy and computing time. It is very suitable for the IoT applications. In Figure 8, it can be seen that the utility of the platform increases as the number of users becomes larger. This is explained that much more appropriate users join the coalition to improve the utility of the system as the number of users increases. As the budget of the platform is fixed, the coalition forming in the later period will always be concentrated among users with high cooperation and low cost; the system utility will enhance slowly as user numbers furtherly increase.Figure 7
Impact of the number of tasks on total costM=30.Figure 8
Impact of the number of users on platform utility withN=10.


## 6. Conclusion

In this article, a cooperation method using overlapping coalition formation game is used to describe the assignment of sense tasks in MCS. The SN-CI based on social networks is proposed to accelerate the formation of coalitions. Moreover, the VTCF algorithm by using the concept of virtual terminals and cooperation degree is proposed to simplify the process of coalition formation. The utility of platform is evaluated by using VTCF, SN-CI, and random, centralized case methods, respectively. The simulated results show that SN-CI method is much quicker than random initialization method in original coalition forming. Furtherly, the utility of platform has been evaluated by the proposed VTCF algorithm and compared with that of using random, centralized case methods. Simulated results have verified the performance of VTCF. The concepts and algorithm proposed in this paper can be regarded as a reference in related study of MCS.



---

*Source: 9223096-2021-09-03.xml*