The semi-empirical Kozeny–Carman (KC) equation is the widely used equation for determining permeability of porous media. Recent studies have shown that KC coefficient (C KC) is a function of porous media parameters. In this study, the relation between parameters of randomly generated porous media is investigated to improve permeability prediction. In particular, site percolation theory is applied to construct random porous media. The static parameters of porous media, including porosity and specific surface area, are evaluated from porous media structure, and dynamic parameters, tortuosity and permeability, are derived from the results of Lattice Boltzmann fluid flow simulation. Nondimensionalized permeability using specific surface area or average grain radius has a correlation with porosity. These correlations give us a clue to propose new functional forms for relations between porous media parameters. The proposed functional forms improve permeability prediction for generated percolation-based porous media and lead to a decrease in average absolute relative error by a factor of 3 and root mean squared error by a factor of 2 compared to the conventional KC relation. In addition, the proposed relations are employed to predict permeability of 11 different real porous media, and the estimated values have significantly lower error than KC estimation.