Elsevier

Fuzzy Sets and Systems

Volume 343, 15 July 2018, Pages 126-140
Fuzzy Sets and Systems

Addition-min fuzzy relation inequalities with application in BitTorrent-like Peer-to-Peer file sharing system

https://doi.org/10.1016/j.fss.2017.04.002Get rights and content

Abstract

The data transmission mechanism in BitTorrent-like Peer-to-Peer (P2P) file sharing systems may be reduced to some addition-min fuzzy relation inequalities. The solution set of addition-min fuzzy relation inequalities plays an important role in the corresponding optimization problem. In this paper, we study some properties of the solutions to such system. Convexity of the solution set and number of minimal solutions are discussed, with comparison to those of the classical max-T fuzzy relation equations or inequalities. Besides, vertex solution and variable-ordering minimal solution are also investigated, with application in BitTorrent-like P2P file sharing system. Two numerical examples are given to illustrate the feasibility and efficiency of the algorithm for solving the variable-ordering solution.

Introduction

Fuzzy relation equation was investigated by E. Sanchez [3], [4] for the first time. After then, fuzzy relation equations or inequalities with all kinds of composition operators were introduced. Researchers studied the structure of their solution sets. In general, the solution set is completely determined by a unique maximum solution and a finite number of minimal solutions. Hence the minimal solutions play an important role in obtaining the solution set. Many novel algorithms were developed to find out all the minimal solutions [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19].

In Ref. [20], Fang and Li introduced linear programming problem subject to fuzzy relation equations with max–min composition. The main problem was decomposed into two subproblems according to the coefficients in objective function. In recent years, this method was widely applied and improved to solve the linear optimization problems with fuzzy relation equation or inequality constraints [21], [22], [23], [24], [25], [26], [27]. Fuzzy relation nonlinear optimization problems were also investigated, such as geometric programming [28], [29], [31], quadratic programming [30] and min–max programming [32].

The data transmission mechanism is technology basis of network communication. In [1], Li and Yang established mathematical model for the data transmission mechanism in BitTorrent-like Peer-to-Peer (P2P) file sharing systems. The corresponding mathematical model was reduced to a system of fuzzy relation inequalities with addition-min composition (addition-min fuzzy relation inequalities), which may be described as follows:{a11x1+a12x2++a1nxnb1,a21x1+a22x2++a2nxnb2,am1x1+am2x2++amnxnbm. In (1), aij,xj[0,1], bi>0, (i=1,2,,m,j=1,2,,n), and the operation ‘+’ represents the ordinary addition, aijxj=min{aij,xj}. In [1], the authors discussed some properties of the addition-min fuzzy relation inequalities. Considering the importance of the minimal solutions, they developed an algorithm to find one of the minimal solutions (the minimal solution is probably not unique).

Optimal management in BitTorrent-like P2P data transmission and file sharing systems was investigated in [2]. A minimization problem with positive coefficients in the linear objective function, i.e.minz(x)=c1x1+c2x2++cnxn, and addition-min fuzzy relation inequality constraints was set up to describe the optimal management model. It is obviously clear that one of the minimal solutions of the feasible domain is an optimal solution of the minimization problem. However, obtaining all the minimal solutions is very difficult. After finding all the pseudo-minimal indexes of addition-min fuzzy relation inequalities by a so-called PMI algorithm, the minimization problem was decomposed into t subproblems (if there are t pseudo-minimal indexes). An optimal solution of the minimization problem was selected from optimal solutions of the subproblems.

Different from the linear function adopted in [2], Yang, Zhou and Cao [32] introduced a min–max function, i.e.ming(x)=x1x2xn, to optimize the objective in an addition management. Without finding all the pseudo-minimal indexes or minimal solutions of the constraint, the main problem was decomposed into some subproblems according to the inequalities in constraint. Optimal solutions of the main problem were generated by those of the subproblems.

In this paper we aim to study the addition-min fuzzy relation inequalities, due to their important application in the BitTorrent-like P2P file sharing systems. The rest of the paper is organized as follows. Section 2 gives some basic notations and results on addition-min fuzzy relation inequalities. In Section 3 we investigate some properties and structure of the solution set of addition-min fuzzy relation inequalities. In particular, we have checked the convexity of the solution set and discussed the number of minimal solutions in this section. Moreover, we have introduced the concepts of vertex solution and variable-ordering (minimal) solution in Section 4. Relationship among vertex solution, variable-ordering solution and minimal solution is also discussed. At last, two application examples and simple conclusions are presented in Sections 5 and 6 respectively.

Section snippets

Preliminaries

Let I={1,2,,m} and J={1,2,,n} be two index sets, then (1) can be written asjJaijxjbi,iI, orAxTbT, where A=(aij)m×n, x=(x1,x2,,xn), b=(b1,b2,,bm), and (ai1,ai2,,ain)(x1,x2,,xn)T=ai1x1+ai2x2++ainx1n. Let X=[0,1]n.

Definition 1

See [1], [2]

Let x1=(x11,x21,,xn1), x2=(x12,x22,,xn2)X. We write x1x2 if and only if xj1xj2, for all jJ. x1<x2 if and only if x1x2 and there exists some jJ such that xj1<xj2. Obviously, the operator ‘≤’ forms a partial order relation on X and (X,) becomes a lattice. We

Structure of the solution set of (1)

In this section, some properties of the solution set of (1) are investigated. Especially, a structure theorem is given to describe the solution set of (1). Besides, the convexity of the solution set and number of the minimal solutions are also discussed.

Denote the set of all minimal solutions of (1) by Xˇ(A,b). Suppose x1=(x11,x21,,xn1), x2=(x12,x22,,xn2)X. We define x1x2 by x1x2=(x11x12,x21x22,,xn1xn2).

Proposition 2

If x1,x2X(A,b), then x1x2X(A,b).

Proof

Since x1,x2X, then x1x2X. Sincex1x2=(x11x12

Vertex solution

Since the solution of system (1), i.e. X(A,b), is a convex set, we can define its vertex solution as follows.

Definition 5

xvX(A,b) is said to be a vertex solution (or convex-vertex solution) of X(A,b) (or of (1)) if and only if λx1+(1λ)x2xv for any λ(0,1) and x1,x2X(A,b) with x1xv,x2xv. A vertex solution is said to be a vertex minimal solution, if it is also a minimal solution of (1).

The set of all vertex solutions of (1) is denoted by Xv(A,b). We also denote Xˇv(A,b)=Xv(A,b)Xˇ(A,b). In fact, a

Application in BitTorrent-like P2P file sharing system

In the BitTorrent-like P2P file sharing system, the constraint condition is satisfying the quality requirement of download traffic, i.e. b. Under this constraint condition, one of the objectives in optimization management is to minimize the data-transmission quality levels, i.e.min{x1,x2,,xn}. However, this is a multi-objective linear programming problem. Usually, there exist infinite Pareto-optimal solutions to problem (27). Hence it is difficult for the management operator to select an

Conclusions

Considering the remarkable application of addition-min fuzzy relation inequalities in the data transmission mechanism in BitTorrent-like Peer-to-Peer file sharing systems, we investigate some properties and two types of special solution sets in this paper. Similar to that of classical max-T fuzzy relation system, the solution set of addition-min fuzzy relation inequalities is fully determined by one maximum solution and a number of minimal solutions. But different from that of the system with

Acknowledgements

The authors are grateful to the responsible editor and the anonymous referees for their valuable comments and suggestions, which helps the authors to improve the earlier version of this paper. This work is supported by the Natural Science Foundation of Guangdong Province (2016A030307037, 2016A030313552) and the Innovation Capability of Independent Innovation to Enhance the Class of Building Strong School Projects of Colleges of Guangdong Province (2015KQNCX094, 2015KTSCX095) and the General

References (33)

Cited by (46)

  • Two-sided fuzzy relation inequalities with addition-min composition

    2023, Alexandria Engineering Journal
    Citation Excerpt :

    Moreover, the solution set could be written as a union of a number of closed intervals. From this perspective, the structure of the solution set to system (2) is similar to that to the one-sided fuzzy relation inequalities system with addition-min composition [12]. However, when consider the convexity of the solution set, we find some differences.

  • On the solvability of weakly linear systems of fuzzy relation equations<sup>☆</sup>

    2022, Information Sciences
    Citation Excerpt :

    For example, linear systems defined over: Addition-min structure describe the quantitative relation of a Peer-to-Peer file-sharing network when we impose the total quality demand of download traffic of peers [19,20,44,48–50], Max–min fuzzy structure describe the quantitative relation of the same fuzzy network when we impose the highest quality demand of download traffic of peers [47],

View all citing articles on Scopus
View full text