—This draft presents a fault -tolerant network segmentation system for the Internet of Things (IoT). When devices of the IoT malfunction or fail, recovery needs to be performed to maintain system functionalities . In modern ad hoc networks like mobile ad hoc networks (MANETs), devices usually form dynamical clusters to collaboratively handle highly diverse sensing environments. To recover cluster information when parts of the IoT are not functionin g, this study develops a centroid -free network segmentation algorithm that diverts dependency on centroid s into empirical -space kernel matrices . The original problem of handling nonvectorial centroids is deduced to kernel matr ix estimation. Index Terms —Incomplete data analysis, missing -value analysis, information recovery, fault -tolerant network segmentation , kernel method, iterative pursuit , clustering, partial kernel matrix estimation , Internet of Things, smart city I. INTRODUCTION The Internet of Things (IoT) is a key to enabling dynamic urban monitoring in a city [1, 2]. When sufficient IoT devices are deployed in a city, city dynamics can be delineated , ranging from crowd activities to environmental statistics [3, 4]. With the recent advancement of telecommunication technology, the IoT is capable of being integrated with ad hoc networks , like mobile ad hoc networks (MANETs) , vehicle ad hoc networks (VANETs) , and flying ad hoc networks ( FANETs) . The IoT becomes fluid and mobile. Therefore , the IoT is no longer fixed at the same place. An IoT device can move around the city. The topology and the number of the IoT may change from place to place in respond to diversified environment s. In h ighly populated area s, more devices can join the IoT, and the density of the IoT becomes higher, so that the system can cope with complex city dynamics . In MANETs [5], IoT devices collaborate with each other to share computational /communication burdens, e.g., visual IoT devices. Under such circumstances, the entir e IoT needs to be dynamically segmented to groups, or clusters [6]. At present , a great deal of research on IoT clustering has been done. Typical approaches like hierarchical clustering , K-means, self-organizing maps , and support vector clustering are widely used in the IoT. For example, Wang et al. [7] utilized support vector clustering for time -series data. Different kernels were B.-W. Chen is with the Department of Electrical Engineering , National Sun Yat-Sen University , Taiwan employed in the work to examine the effectiveness. The merit of support vector learning was that it generated a satisfactory result even when few data were present. Besides, support ve ctor clustering was rapid for dealing with data streams. The system by Tsirmpas et al . [8] was designed for profiling living environments , where the IoT was deployed. The authors devised self-organizing maps to cluster IoT sensed data . In some other studies [9, 10], for instance, Hajjar et al . [10] examined machine learning techniques and proposed a hybrid clustering algorithm based on hierarchical clustering and K-means . Thei r application was aimed at collaborative resource planning for communication networks. As dis cussed above, IoT clusters are important logical formation in networks as they help data processing and communications. This is because IoT clusters are conducive to balancing computational loads or data redundancy in a collaborative mode . Devices in the same cluster present homogeneous characteristics, either in device parameters or data collection . Such a homogeneous characteristic is important when a fault -tolera nt network is established. In a network , especially for the IoT, faults are generated due to device failure or malfunctioned nodes. When such a situation occurs, harvested data contain missing values . If samples contain missing values, they become nonvecto rial data. Subsequently, typical mathematical operations are inapplicable . This may cause a problem to the IoT . To resolve missing values, several approaches have been developed, such as deletion, replacement , regression [11], K-nearest neighbor s [12], multiple imputation [13], and matrix completion [14-16]. Among th ese methods, matrix completion provides more flexible choices for data imputation . Data imputation can generate approximate values for those missing -value entries before IoT cluster recovery is performed. The s ystem by Fekade et al. [17] adopted the same concept. They used typical K-means and matrix completion as the model . Incomplete data were firstly handled and imputed by matrix completion , and subsequently K-means was used for clustering. In general, m atrix completion is usually the first step for cluster recovery . However, considering the objective is to recover cluster membership, matrix completion requires additional computational time. Rather than performing matrix completion prior to cluster recovery, Chi et al. [18] devised an iterative procedure, which contain ed two phases. One wa s K-means, and the other involved generating imputed values based on centroids. Chi et al. [18] filled in missing -value entries with zeros at the initial stage, so that K-means could be done in the first iteration. Afterwards , missing -value entries were filled in with centroids generated by K-means . Two steps were iterate d over many cycles until the predefined criterion stabilized. Another IoT Network Segmentation When Sensor s Fail Bo-Wei Chen interesting work that did not rely on matrix completion before clustering was the system by Wagstaf f [19]. The intuition behind it was that [19] split every incomplete sample (i.e., a feature vector ) into two part s. One was a complete subvector, and the other was the rest of the feature vector that contained partial data. All of the incomplete subvector s were used for constraint generatio n. Clustering was performed based on K-means and complete subvector s with previously discovered constraint s. Inspired by [18, 19], this work is aimed at reduc ing complexity of the above -mention clustering algorithm s while maintaining accuracy at the same time. As the above -mention methods relied on cluster centers dur ing iterations, the dependency on cluster centers is diverted to kernel matrices. Updates in centroids become computation of difference in kernel matrices. Therefore, such a mechanism enhances speeds while avoiding comput ing centroids in each iteration . The rest of th is draft is organized as follows . Section II introduces the proposed model . Subsequently, the proposed fault-tolerant network segmentation based on the model is detailed in Section I II. II. PROPOSED METHODOLOGY This section describe s how malfunctioned IoT devices can be divided into clusters without using typical data imputation. Firstly, subsection II.A introduces efficient kernelized centroid -free clustering . This is because finding centroids among missing -value data is not practica l. Subsection II.A diverts the dependency on centroids to centroid -free kernel matrices. Subsequently, subsection II. B details how kernel matrices are estimated under the condition of missing values . Two versions of kernel matri x estimat ion are discussed. One requires third -party information, and the other needs no imputation. A. Efficient Kernelized Centroid -Free Clustering for the Large -Scale IoT This step follows the algorithm by [20] with modifications to support missing -value data clustering in our scenario. Assume that the dataset contains no missing values. Also a ssum e that the total number of clusters is S, so that the entire IoT can be divided into clusters s, where s denotes the cluster index, and s = 1,2,…, S. The clustering algorithm is aimed at minimizing the distance between samples and their corresponding centroids, EClustering . That is,   2 Clustering 1 2 2 12s sS s s S ss sE          x xxμ xμ (1) where ||∙|| stands for the L2 norm , μs represents the centroid of cluster s, and ϕ is a kernel function that maps an input xι onto the intrinsic space (see the appendix) . Input xι is regarded as a complete sample without missing values herein. Let N denote the total number of IoT devices and Ns signify the number of IoT devices in cluster s. Therefore, N1 + N2 + … + NS = N. The centroid of cluster s is defined as 1 issi sN  xμx . (2) The objective of minimization of (1) is actually equivalent to minimization of 2 Clustering 12 sS ss sE     xμ (3) as ||ϕ(xι)||2 does not affect the clustering result. Therefore, the update of cluster centroids relies merely on ||μs||2 and Rιs. The following description focuses on ||μs||2 and Rιs. In (3), Rιs is given as follows by definition, and it can be interpreted as the similarity between sample ϕ(xι) and centro id μs. ss xμ (4) where  is the transpose operator . Plugging (2) into (4) yields   11 1i s i s iss i i ss i sNN N             xx xx x x x K (5) where K refers to a kernel matrix formed by all the input samples , and Kιi is a scaler and an element of K corresponding to sample s ι and i. For the squared norm of centroid μs, i.e., ||μs||2, it can also be represented by using K as follows.   2 2 211 1 1.s i s s i s s i ss s s i ss i s i sNN N KN             xx xx xxμ μ μ x x xx (6) The squared norm of centroid μs stands for a submatrix based on all the samples in cluster s. With (5) and (6), the connection with ||μs||2 and Rιs in (3) hinges on kernel matrix K. In clustering, the entire process can be decomposed into iterative updates on all the samples. For each iteration, a sample needs to select the closet centroid and disjoins its original cluster. In brief, two phases are involved for a sample. One is to j oin the closest cluster, and the other is to disjoin its original cluster . Let q and p respectively represent the index of the closest cluster and the original cluster for sample xι. Then , the new centroid μ′q of the closest cluster becomes 2 22 2 2 22 1 1 1 1qq q q q q q qNNK N N N       μμ , (7) whereas the new centroid μ′p of the original cluster is 2 22 2 2 22 1 1 1 1pp p p p p p pNNK N N N       μμ . (8) Notably, the above ||μq||2 and ||μp||2 can be replaced with computation of K in (6). As the centroids to q and p change, the distance between the members and these two centroids, i.e., R, should be accordingly modified. Thus, 11, 1, ,1qqjq ji ji iiqqK K j NNN     . (9) 11, 1, ,1ppjp ji ji iippK K j NNN      . (10) The complexity of the above algorithm is (N2/S); however, for a large scale of the IoT, the update is still inefficient. An improve d and rapid clustering algorithm is introduced. Besides, its complexity is merely (N). To remove the dependency on Nq and Np in (7)–(10), (3) is rewritten as 2 21, ,2arg mins s sSs ssN N   μ . (11) Let 2 221q q q Nμμ and 2 221.p p p Nμμ Then, the new centroid of the closest and the original cluster when the membership of sample xι changes is respectively 222q q q K    μμ (12) and 222p p p K    μμ . (13) It becomes more efficient when one rewrit es the above equations into the following form, where the amount of chang es is introduced . Therefore, 2 2 22q q q q K       μ μ μ (14) and 2 2 22.p p p p K       μ μ μ (15) Likewise, let 1jq q jq N    and 1.jp p jp N    Subsequently, , 1, ,jq jq jq j K j N     (16) and , 1, ,jp j K j N    . (17) B. Kernel Matrix Estimation As mentioned earlier at the beginning of this section, the objective of subsection II.A is to shift the dependency on centroids to kernel matrices. This subsection subsequently details estimation of kernel matrices under a condition when IoT devices malfunction and incomplete data are generated. This work employs the concept by [21] with modifications in the Masked Partial Three -Side functions to support fault-tolerant network segmentation (see the next section). Let B represent a mask that performs dimension selection . Then, 1 if is given 0 otherwisemxm xB (18) and x x x B (19) where xm denote s the m–th dimension of x, and  is the element -wise operator , i.e., Hadamard operators . Typically, a kernel matrix measures the similarity between two vectors , i.e., two samples . However, when the system, e.g., [22], calculates such a matrix, no third -party information is used. Take the cosine -similarity function for example . The kernel matrix is formed by calculating T Cosine ,ij ij ijK xxxx xx (20) where i and j respectively signify the indices of two instances . When these two vectors contain missing entries, it involves nonvectoria l similarit ies and results in biased estimation. Let ii iiii jj    xx xxx x B B x x B B , (21) i.e., double masks. Thus, the Masked Partial -Cosine (MPC) function is used for nonvectorial similarit ies.  MPC ,ij ij ijK xxxx xx (22) It is worth noticing that no data approximation is performed in (19) and (21) during masking. Based on (22), the Masked Partial Three -Side (MPT) cosine function is derived as follows.  MPT ,i u j v ij i u j vK  xμ x μ xx xμ x μ (23) where μu and μv are respectively centroids of clusters u and v. Besides, ix ∈ u and jx ∈ v. This creates an approximate value with a cluster -dependent average in the same attribute. The effect of “ ix ⨁μu” and “ jx ⨁μv” indicates that the similarity between ix and jx should also consider the similarity between ix and the cluster centroid of jx Second, the missing -value entries are filled with centroid information. Equation (23) can be extended into MPT cosine polynomial kernels , MPT radial basis function s (RBFs) , and MPT TRBFs , respectively, i.e.,  MPC 2 MPT 21,1 1,1D ij ij ij D i u j v ij i u j vK K             xxxx xx xμ x μ xx xμ x μ , (24)  2 MPC 2 2 MPT 21, exp2 1, exp2j i ij i j jv iu ij iu jvK K                    x xxxx x xμ xμxxxμ xμ , (25) and  M22 1 22P P 1MC T1 ! !1, 1,1j i ij i j jv iu ij u jvD iD K K                    xxxxxx xμ xμxxxμ xμ (26) where σ2 is the variance, D signifies the kernel order , and τ denotes the index of components . The upper parts of (24)–(26) rely on no centroids, whereas the lowers parts require centroids for imputation. These two versions affect the result of fault-tolerant network segmentation , detailed in the following section. III. PROPOSED FAULT -TOLERANT NETWORK SEGMENTATION With kernel matrix estimation and kernelized centroid -free clustering in the previously mentioned sections, fault-tolerant network segmentation is applicable. Two versions of fault-tolerant network segmentation are discussed below. Their difference is computation of k ernel matrices. K ernelized centroid -free clustering is the same. The first one repeatedly fills in missing -value entries with centroids. The second one directly ignores missing -value entries . A. Iterative Pursuit The i terative pursuit algorithm consists of two steps. These steps are iterate d until clusters are stabilized by checking (6). The first step is kernel matrix estimation with centroid -based imputation. The second step uses clustering to update centroid s, so that changes can be reflected in kernel matrix estimation . Algorithm I: MPT -Based Iterative Pursuit Input: X = [x1,x2,…,xN] with missing values Output: 1,2,…,S 1. Randomly initialize μs ∈ M, where s = 1,2,..., S 2. Choose an MPT cosine kernel 3. for limited iterations 4. Estimate the kernel matrix, K 5. while xn migrates between clusters (n= 1,2,..., N) 6. Compute Δ of the squared norm based on (14) and (15) 7. Compute ΔR based on (16) and (17) 8. end 9. Compute μs 10. end Let  represen t the number of iterations and (M2N3) denote the complexity of kernel matrix estimation. Then, the complexity of this algorithm is (M2N3). B. Rapid Computation Unlike the above algorithm, this method does not require imputation. Besides, no iteration is performed for kernel matrix estimation . This algorithm saves more computational time than the above algorithm . Algorithm II: MPC -Based Rapid Computation Input: X = [x1,x2,…,xN] with missing values Output: 1,2,…,S 1. Randomly initialize μs ∈ M, where s = 1,2,..., S 2. Choose an MP C kernel 3. Estimate the kernel matrix, K 4. while xn migrates between clusters (n= 1,2,..., N) 5. Compute Δ of the squared norm based on (14) and (15) 6. Compute ΔR based on (16) and (17) 7. end As no iteration is used, this algorithm has complexity of (M2N3). APPENDIX The appendix shows the drawback of centroid -based clustering and intrinsic kernel space . Consider the case of complete data X. Given an M-by-N matrix X without missing values, where M specifies the number of dimensions, and N denotes the number of observed samples . In our case, observed samples refer to IoT devices. Besides, X = [x1, x2,…, xN]. The objective of matrix completion is to minimize the difference between X and its approximate matrix formed by UV. That is, X ≈ UV. One of the implementation for matrix completion , i.e., ridge alternating least squares [14], is shown as follows  2 2 2 rALS U V min , minE      U V X UV U V (27) where U and V are respectively M-by-H and H-by-N unknown matrices, H is the intermediate dimension, and ||∙|| represents the Frobenius norm . Ridge ALS uses ridge parameter s, ρU and ρV, to regularize and prevent U and V from overfitting , respectively . Differentiating ErALS and zeroing the equations yield 1 V V U U I U X (28) and 1 U U VV I VX (29) where I is an identity matrix . The system can iteratively update U and V based on (28) and (29) to generate a solution. For matrix X with missing values, the procedure is still the same, as shown in (30) and (31). The difference is that an element -wise mask G is imposed on X. If an element of X is missing, then such an entry is temporally substitute d with a zero first. 1 V G    V U U I U X (30) and 1 U G    U VV I V X . (31) Finally, the missing elements of X are replaced with the corresponding elements of the generated matrix, i.e., UV. This completes the matrix approximation. For centroid -based clustering, it requires mapping a sample from feature space into intrinsic space. Assume the size of the dimension in feature space is M, and then that of intrinsic space is ! 11 !!MD MDJMD D     . (32) Let dm represent the power of xm, where m = 1,2,…, M+1. After kernel mapping, the new variable in each dimension follows the form 11 1 11 11 11! !, , ! 0 , ,s.t. MM d d d MM M M MDx x xdd d d D d d D           (33) if polynomial kernel s are used. When truncated RBFs (TRBFs) are employed, 112 11 2 11 11exp2 0 , ,s.t. .MM d d d MM M Mx x x d d D d d D        x (34) In intrinsic space , an M-by-1 vector is converted to a J-by-1 one. There are several drawbacks if centroid -based clustering and intrinsi c space are used. Firstly, typical RBFs are inapplicable due to infinite dimensions in intrinsic space. This is inconvenient as centroids cannot be represented in intrinsic space when RBFs are used. Instead, T RBFs should be adopted. Second, kernel mapping requires the missing values in feature space to be imputed beforehand .