Addition-min fuzzy relation inequalities with application in BitTorrent-like Peer-to-Peer file sharing system
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: In (1), , , (), and the operation ‘+’ represents the ordinary addition, . 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. 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. 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 and be two index sets, then (1) can be written as or where , , , and . Let .
Definition 1 Let , . We write if and only if , for all . if and only if and there exists some such that . Obviously, the operator ‘≤’ forms a partial order relation on X and becomes a lattice. WeSee [1], [2]
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 . Suppose , . We define by .
Proposition 2 If , then . Proof Since , then . Since
Vertex solution
Since the solution of system (1), i.e. , is a convex set, we can define its vertex solution as follows.
Definition 5 is said to be a vertex solution (or convex-vertex solution) of (or of (1)) if and only if for any and with . 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 . We also denote . 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. 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)
An algorithm for minimizing a linear objective function subject to the fuzzy relation inequalities with addition-min composition
Fuzzy Sets Syst.
(2014)Resolution of composite fuzzy relation equations
Inf. Control
(1976)Fuzzy relation equations and inequalities
Fuzzy Sets Syst.
(1984)Deriving minimal solutions for fuzzy relation equations with max-product composition
Inf. Sci.
(2008)Solutions of fuzzy relation equations based on continuous t-norms
Inf. Sci.
(2007)- et al.
An algorithm for solving fuzzy relation equations with max-T composition operator
Inf. Sci.
(2008) Method of solution to fuzzy relation equations in a complete Brouwerian lattice
Fuzzy Sets Syst.
(2001)Resolution of fuzzy relational equations – method, algorithm and software with applications
Inf. Sci.
(2013)- et al.
On fuzzy relational equations and the covering problem
Inf. Sci.
(2011) On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem
Fuzzy Sets Syst.
(2009)
Fuzzy relation equations on a finite set
Fuzzy Sets Syst.
Solving fuzzy relation equations with a linear objective function
Fuzzy Sets Syst.
Optimization of fuzzy relation equations with max-product composition
Fuzzy Sets Syst.
Minimizing a linear function under a fuzzy max–min relational equation constraint
Fuzzy Sets Syst.
An algorithm for solving optimization problems with fuzzy relational inequality constraints
Inf. Sci.
Linear optimization problem constrained by fuzzy max–min relation equations
Inf. Sci.
Cited by (46)
Solving minimal-optimal solutions for the generalized min-max programming problem with addition-min composition
2024, Fuzzy Sets and SystemsTwo-sided fuzzy relation inequalities with addition-min composition
2023, Alexandria Engineering JournalCitation 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.
Generalized min-max programming problems subject to addition-min fuzzy relational inequalities
2022, Fuzzy Sets and SystemsOn the solvability of weakly linear systems of fuzzy relation equations<sup>☆</sup>
2022, Information SciencesCitation 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],