Abstract:
A reliability of multi-state information network evaluation method and system thereof are disclosed in the present invention. The system comprises a storage unit, a universal generation function process unit, a reliability calculating unit, and a judging unit. The feature of the invention is to develop a novel method for evaluation of the reliability based on the disconnectedness between nodes and targets. Therefore, a decision-maker can analyze the network according to the invention and apply the analysis result in lots of applications, such as computer communication system, electronic transmission system, transportation system, etc.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority from Taiwan Patent Application No. 102129063, filed on Aug. 13, 2013 in Taiwan Intellectual Property Office, the contents of which are hereby incorporated by reference in their entirety. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention is related to a network reliability evaluation system and method thereof, and particularly is related to an system capable of evaluating the reliability for a multi-state information network and method thereof. 
         [0004]    2. Description of the Related Art 
         [0005]    The network reliability theory is used broadly in many systems in the real world, such as communication systems, transportation systems, petroleum/gas transportation pipeline systems, computer network systems, and mobile-phone network systems. The network reliability plays an important role in the real world. 
         [0006]    A multi-state information network is a popular network mechanism. The multi-state information network has a starting node and whole information is transmitted from the starting node. A plurality of nodes are responsible for transmitting the information via a plurality of arcs in the multi-state information network. Finally, the information is transmitted to different target nodes. Above process of information transmission follows the flow conservation. Evaluating the probability of connecting the starting node to the plurality of target nodes is defined as the reliability evaluation of the multi-state information network. 
         [0007]    Generally, the reliability of the multi-state information network is evaluated via a universal generation function, a recursive technique and a simplify technique. However, when the status of the network is closed to a complete graph, the heavy complexity will be incurred if the universal generation function is employed. Therefore, based on a novel disconnectedness feature between the starting node and target nodes, a universal generation function for evaluating the reliability and the non-reliability for the multi-state information network is proposed by the present inventor. In other words, the reliability evaluation is accomplished by the manners of combination, replacement, and transformation. So the features of the novelty and the non-obviousness are available in the present invention. 
       SUMMARY OF THE INVENTION 
       [0008]    The embodiment of the present invention is directed to a system capable of evaluating the reliability of the multi-state information. network. The system bases the disconnectedness feature to calculate the reliability and non-reliability of the multi-state network so as to speed up the reliability evaluation of the multi-state information network. Furthermore, the novel evaluation method can be supplied to industries as well. 
         [0009]    The present invention provides a reliability of a multi-state information network evaluation method which is applicable to a network. The network comprises a plurality of nodes and a plurality of arcs to connect the plurality of nodes, and the plurality of nodes at least comprises a starting node and a target node. The evaluation method comprises the following steps. a. A counting value (i) is set as 2 and the starting node is set as [1] to calculate u([1]) and U([1]) by a universal generation function process unit. The first-stage node is represented by [1], the universal generation function of the first-stage node is represented by u([1]), the universal generation function of the first-stage sub-network is represented by U([1]), and U([1])=u([1]). b. A node v is set as [i] by the universal generation function. process unit and u([i]) is calculated by [i]. The i-stage node is represented by [i], the i-stage node universal generation function is represented by u([i]), the node v is connected to V [i−1]  and the node v does not belong to V [i−1] , and V [i−1] ={[1], [2], . . . [i−1]}. c. U([i−1]) and u([i]) are applied to the universal generation function process unit to calculate and simplify U([i]), and the i−1 stage and the i stage universal generation functions are represented by U([k−1]) and U([i]), respectively. d. A reliability coefficient R J  is obtained by applying U([i]) and a set J to a reliability calculating unit, and the reliability coefficient R J  is applied to perform a calculation of a network reliability. The set is contained in a set including at least a target node, and the reliability coefficient R J  is the probability of all target nodes not in J receiving information from the starting node in U([i]). e. A judging unit is used to judge if the counting value (i) is less than a threshold value, and the counting value is incremented by 1 and step b is performed if the counting value (i) is less than the threshold value. 
         [0010]    Preferably, the threshold value is equal to the number of nodes of the plurality of nodes excluding at least one of the target nodes. 
         [0011]    Preferably, u([i])=Σ I∈θj  p i:I Z I , Θ i  is a set of nodes which can be reached from [i], p i:I Z I  is a total probability of starting from [i] to reach nodes of the set I. 
         [0012]    Preferably, R J =Σ I π i:I , π i:I  is a probability of starting from [i] and unable to reach any node of the set I via a sub-network of the network. 
         [0013]    Preferably, the universal generation function process unit comprises a multiplication operator           to apply to the calculation of the universal generation function. 
         [0014]    A reliability of a multi-state information network evaluation system is applicable to a network. The network comprises a plurality of nodes and a plurality of arcs to connect the plurality of nodes, and the plurality of nodes at least comprises a starting node and a target node. The evaluation system comprises: a storage unit, adapted to save a counting value (i) and a network status of the network, wherein the counting value (1) is set as 1 initially; a universal generation function process unit, adapted to calculate u([i]) and U([i]) via applying the network status, the counting value (i), a node v, and U([i −1]), and simplify U(i) before storing U(i) into the storage unit, wherein i is a positive integer, [i] represents the i-stage node, U(i) represents universal generation function of the i-stage sub-network, and u([i]) represents universal generation function of the i-stage node; a reliability calculating unit, adapted to obtain a reliability coefficient R J  via applying the network status, U(i) and a set J, and apply the coefficient R J  to perform a calculation of a network reliability, wherein the set J is contained in a set including at least a target node, and the reliability coefficient R J  is the probability of all target nodes not in J receiving information from the starting node in U([i]); and a judging unit, adapted to judge if the counting value (i) is less than a threshold value, the counting value (i) being incremented by 1, the universal generation function process unit is enabled to continue the process, and the reliability calculating unit is enabled to continue the calculation; wherein the node v is the starting node if the counting value (i) is equal to 1; the node v is connected to V[i−1] and v is not belong to any node of V[i−1] if the counting value (i) is not equal to 1. 
         [0015]    Preferably, the threshold value is equal to the number of nodes of the plurality of nodes excluding at least one of the target nodes. 
         [0016]    Preferably, u([i])=Σ I∈θ     i    p i:I Z I , Θ i  is a set of nodes which can be reached from [i], p i:i Z I  is a total probability of starting from [i] to reach nodes of the set I. 
         [0017]    Preferably, the universal generation function process unit comprises a multiplication operator           to apply to the calculation of the universal generation function. 
         [0018]    Preferably, R J =Σ I π i:I , π i:I  is a probability of starting from [i] and unable to reach any node of the set I via a sub-network of the network. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0019]    Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art to which the present invention pertains can realize the present invention, wherein: 
           [0020]      FIG. 1  is a block diagram of an evaluation system of multi-state information network according to an embodiment of the present application; 
           [0021]      FIG. 2  is a schematic view of an evaluation system of multi-state information network according to another embodiment of the present application; and 
           [0022]      FIG. 3  is a flow chart of an evaluation method of multi-state information network according to the second embodiment of the present application. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0023]    As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items. Expressions such as “at least one of,” when preceding a list of elements, modify the entire list of elements and do not modify the individual elements of the list. 
         [0024]    Referring to  FIG. 1 ,  FIG. 1  is a block diagram of an evaluation system for multi-state information network according to an embodiment of the present application. As shown in  FIG. 1 , the reliability evaluation system of multi-state information network comprises a storage unit  10 , a universal generation function process unit  20 , a judging unit  30 , and a reliability calculating unit  40 . A network status  101  and a counting value  102  are stored in the storage unit  10 , and the counting value  102  is set as 1 initially. The multi-state information network is composed of a plurality of nodes and a plurality of arcs, and the plurality of nodes comprises a starting node and at least one target node. The information is transmitted from the starting node to at least one target node via a plurality of arcs. The evaluation system comprises a computer host, a server, a workstation, or a notebook. The storage unit  10  comprises a memory, a tap, or a hard-disk. The universal generation function process unit  20 , the judging unit  30 , and the reliability calculating unit  40  may be implemented by an application program. 
         [0025]    In detail, based on the network status  101 , the counting value  102 , a node v, and the universal generation function of the (i−1) stage sub-network Ur([i−1]), the universal generation function of the i-stage u([i]) and the universal generation function of the i stage sub-network U([i]) are calculated by the universal generation function process unit  20  first. After the universal generation function of the i stage sub-network is simplified, the simplified universal generation of the i stage sub-network is stored into the storage unit  10 . At the same time, the counting value  102  is equal to 1 and the node v is set as the starting node. 
         [0026]    Based on the network status  101 , the universal generation function of the i stage sub-network U([i]) and a set J, the reliability calculating unit  40  obtains a reliability coefficient R J . With the reliability coefficient R J , the reliability of the multi-state information network is calculated. The set J is contained in a set including at least a target node. In other words, the set J comprises {(2), (3), (5), (2, 3), (2, 5), (3, 5), (2, 3, 5)} when the at least one target node comprises the node 2, the node 3, and the node 5. The reliability coefficient R J  is the total probability of all target nodes not in J receiving information from the starting node of the i stage sub-network U([i]). For example, it is assumed that the node {2} is the starting node, the target node comprises the node {5}, and the set of nodes which can be reached from node {2} comprises the node {3}, the node {5} and the node {3, 5}, and then the reliability coefficient generated by the node {2} comprises π 2:{φ} , π 2:{3} , π 2:{3, 5} , and π 2:{5} . The R J  is equal to the sum of π 2:{φ}  and π 2:{3} . The π 2:{φ}  represents the reliability coefficient from the node {2} to the node {2} and the π 2:{3}  represents the reliability coefficient from the node {2} to the node {3}. 
         [0027]    When the judging unit  30  judges that the counting value  102  is less than a threshold value, the counting value  102  is incremented by 1, the universal generation function process unit  20  is enabled to continue the reliability evaluation process, and the reliability calculating unit  40  is enabled to continue the calculation. On the other hand, the reliability evaluation process is terminated if the counting value  102  is higher than the threshold value, where the threshold value represents the number of the plurality of nodes excluding all targets nodes. For example, when the number of all nodes is equal to ten and the target nodes comprise three nodes, the threshold value is equal to seven. Furthermore, after the counter value is set as 2 (including 2), a new node v is chosen from the nodes which are connected to V [i−1]  and not belong to any node of V [i−1] , where V [i−1] ={[1], [2], . . . [i−1]}. 
         [0028]    Referring to  FIG. 2 ,  FIG. 2  is a schematic view of an evaluation system of multi-state information network according to another embodiment of the present application. As shown in  FIG. 2 , the node {1} is a starting node in the multi-state information network, and the node {4} and the node {5} are the targets node in the multi-state information network. The arrow of the arc in  FIG. 2  displays the direction of the information flow. The reliability of the multi-state information network is the reliability calculated from the node {1} to the node {4} or the node {5}. First, the counting value (i) is set as 1 and the node v is set as the node {1}. The judging unit  30  sets the counting value (i) as 2, and enables the universal generation function process unit  20  and the reliability calculating unit  40  to do the further calculation. 
         [0029]    Preferably, when the counting value (i) is equal to 2, π 1:{φ} =p 1:{φ} , π 1:{2} =p 1:{2} , π 1:{3} =p 1:{3}, π   1:{2:3} =p 1:{2:3} , U([1])=u([1])=π 1:{φ}Z   φ +π 1:{2} Z 2 +π 1:{3} Z 3 +π 1:{2, 3} Z {2, 3} , u([2])=p 2: φ Z φ +p 2:{3} Z {3} +p 2:{5} Z {5} +p 2:{3, 5} Z {3, 5} , p m:n Z n  represents the probability transmitting the information from the node in to a set n. π v:J  represents the coefficient Z J  in the sub-network of the universal generation function from the existing universal generation function method and U([i])=Σ I∈θ     i    P i:I Z I , Θ i  represents a set of nodes that can be reached from the node {i}, p i:I Z I  represents a total probability of starting from the node {i} to reach nodes in the set I, u{[i]} represents the i stage universal generation function, and U([i]) represents the universal generation function of the i stage sub-network. 
         [0030]    Further, the U([2]) is computed as: U([2])=U([1])           u([2])=(π 1:{φ} Z φ +π 1:{2} Z 2 +π 1:{3} Z 3 +π 1:{2, 3} Z {2, 3} )         [p 2: φ    Z   φ +p 2:{3} Z {3} +p 2:{5} Z {5} +p 2:{3,5} Z {3,5} ]=π 1:{φ} Z φ +π 1:{3} Z 3 +(π 1:{2} Z 2 +π 1:{2, 3} Z {2, 3} )         [p 2:φ  Z φ +p 2:{3} Z {3} +p 2:{5} Z {5} +p 2:{3, 5} Z {3, 5} ]. And the           is a multiplying operator of the universal generation function. 
         [0031]    Preferably, the U([2]) can be simplified as U([2])=π 2:{φ} Z φ +π 2:{3} Z 3 +π 2:{5} Z 5 +π 2:{3, 5} Z {3, 5} , π 2:{φ} =p 1:φ +p 1:{2} p 2:φ , π 2:{3} =p 1:3 +p 1:{2} P 2:{3} +p 1:{2, 3} P 2:φ +p 1:{2, 3} p 2:{3} , π 2:{3 5} =p 1:{2} p 2:{3, 5} +p 1:{2, 3} p 2:{5} +p 1:{2, 3} p 2:{3, 5} , π 2:{5} =p 1:{2} p 2:{5}.    
         [0032]    At the moment, R 5 =π 2:{φ} +π 2:{3} =p 1:φ +p 1:{2} p 2:φ +p 1:3 +p 1:{2} p 2:{3} +p 1:{2, 3} p 2:φ +p 1:{2, 3} p 2:{3} , and R 5 =Σ I π i:I , i=2, I=5, π i:I  represents a total probability of starting from the node [I] to reach the set I via a sub-network of the multi-state information network. That is, the non-reliability of the sub-network is evaluated by the disconnectedness feature. 
         [0033]    The counting value is changed to 3 by incrementing 1. The u(3)=p 3: φ  Z φ +p 3:{4} Z {4} , U(3)=U2         u(3)=(π 2:{φ} Z φ +π 2:{3} Z 3 +π 2:{5} Z 5 +π 2:{3, 5} Z {3, 5} )         (p 3: φ  Z φ +p 3:{4} Z {4} ). U(3) can be simplified as : U(3)=π 3:φ Z φ +π 3:{4} Z 4 +π 3:{5} Z 5 +π 3:{4, 5} Z {4, 5} , π 3:φ =π 2:{φ} +π 2:{3} p 3:φ , π 3:{4} =π 2:{3} p 3:{4} , π 3:{5} =π 2:{5} +π 2:{3, 5} p 3:φ , π 3:{4, 5} =π 2:{3, 5} p 3:{4} . 
         [0034]    R {4}  and R {5}  can be computed as: R {4} =π 3:{φ} +π 3:{5} =π 2:{φ} +π 2:{3} p 3:φ +π 2:{5} +π 2:{3,5} p 3:φ =(p 1:φ +p 1:{2} p 2:φ )+(p 1:3 +p 1:{2} p 2:{3} +p 1:{2,3} p 2:φ +p 1:{2,3} p 2:{3} )p 3:φ +p 1:{2} p 2:{5} Z 5 +(p 1:3 +p 1:{2} p 2:{3} +p 1:{2,3} p 2:φ +p 1:{2, 3} p 2:{3} )p 3:φ , R {4,5} =π 3:φ +π 3:{4} +π 3:{5} =π 2:φ +π 2:{3} p 3:φ +π 2:{3} p 3:4 +π 2:5 +π 2:{3,5} p 3:φ =(p 1:φ +p 1:{2} p 2:φ )+(p 1:3 +p 1:{2} p 2:{3} +p 1:{2, 3} p 2:φ +p 1:{2, 3} p 2:{3} )p 3:φ +(p 1:3 +p 1:{2} p 2:{3} +p 1:{2, 3} p 2:φ +p 1:{2, 3} p 2:{3} ) p 3:4 +p 1:{2} p 2:{5} Z 5 +(p 1:{2} p 2:{3, 5} +p 1:{2, 3} p 2:{5} +p 1:{2, 3} p 2:{3, 5} )p 3:φ . 
         [0035]    The threshold value is 3(3−5−2) since two of five nodes are target nodes in  FIG. 2 . And, the calculation of the reliability is terminated because the counting value is incremented to 3. After R {4} , R {5}  and R {4, 5}  are obtained, each of them represents the probability of starting from the node {1} but unable to reach the node {4}, the probability of starting from the node {1} but unable to reach the node {5}, and the probability of starting from the node {1} but unable to reach the node {4} or the node {5}, that is, the non-reliability of the network is obtained. Therefore, the probability of reaching the node {4}, the node {5}, and the node {4} or the node {5} can be evaluated as  1 −R {4} , 1−R {5} , and 1−R {4, 5} , that is, the reliability of the network is obtained. 
         [0036]    Referring to  FIG. 3 ,  FIG. 3  is a flow chart of an evaluation method of multi-state information network according to the second embodiment of the present application. As shown in  FIG. 3 , the evaluation method is applied for a network which comprises a plurality of nodes and a plurality of arcs connected with the plurality of nodes. Each of nodes comprises a starting node and at least one target node. In step S 1 , a universal generation function process unit is used to set a counting value (i) as 2 and the starting node as [1] to calculate u([1]) and U([1]). The first-stage node is represented by [1], the universal generation function of the first-stage node is represented by u([1]), the universal generation function of the first-stage sub-network is represented by U([1]), and U([1])=u([1]). In step S 2 , the universal generation function process unit is used to set a node v as [i], and [i] is used for calculating u([i]). The i-stage node is represented by [i], the i-stage node universal generation function is represented by u([i]), the node v is connected to V [i−1]  and the node v does not belong to V [i] , and V [i−1] ={[1], [2], . . . , [i−1]}. In step S 3 , u([i]) and U([i−1]) are applied to calculate and simplify U([i]). The i−1 stage and the i stage universal generation functions are represented by U([i−1]) and U([i]), respectively. In step S 4 , U([i]) and a set J are applied to obtain a reliability coefficient R J  by a reliability calculating unit, and the reliability coefficient R J  is applied to perform a calculation of a network reliability. The set J is contained in a set including at least a target node, and the reliability coefficient R J  is the probability of all target nodes not in J receiving information from the starting node in U([i]). In step S 5 , a judging unit is used to judge that the counting value (i) will be incremented by 1 and step S 2  will be performed if the counting value (i) is less than a threshold value. The threshold value is equal to the number of nodes of the plurality of nodes excluding at least one of the target nodes. 
         [0037]    The aforementioned preferred embodiment is to explain the technical ideas and features of the present application. The purpose is to enable those who skilled in this technical area to understand the content of the present application and realize it. It will be understood that the present application is not limited to the details thereof. Various equivalent variations and modifications may still occur to those skilled in this art in view of the teachings of the present application. Thus, all such variations and equivalent modifications are also embraced with the scope of the present application as defined in the appended claim.